第3章 栈和队列.ppt

第3章栈和队列
数据结构(C++描述)
3。1 栈
3。2 队列
退出
目录
栈
栈的定义
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom)。
根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。
也就是说,栈是一种后进先出(Last In First Out)的线性表,简称为LIFO表。

:INISTACK(&S)
将栈S置为一个空栈(不含任何元素)。
:PUSH(&S,X)
将元素X插入到栈S中,也称为“入栈”、“插入”、“压入”。
: POP(&S)
删除栈S中的栈顶元素,也称为”退栈”、“删除”、“弹出”。
: GETTOP(S)
取栈S中栈顶元素。
: EMPTY(S)
判断栈S是否为空,若为空,返回值为1,否则返回值为0。

ADT Stack is Data:
含有n个元素a1,a2,a3,…,an,按LIFO规则存放,每个元素的类型都为elemtype。
Operation:
Void inistack(&s) //将栈S置为一个空栈(不含任何元素)
Void Push(&s,x) //将元素X插入到栈S中,也称为“入栈”、“插入”、“压入”
Void Pop(&s) //删除栈S中的栈顶元素,也称为”退栈”、“删除”、“弹出”
Elemtype gettop(s) //取栈S中栈顶元素
Int empty(s) //判断栈S是否为空,若为空,返回值为1,否则返回值为0
End stack


CONST int maxsize=maxlen; //定义栈的最大容量为maxlen
Struct seqstack
{ elemtype stack[maxsize]; //将栈中元素定义为elemtype类型
int top; //:指向栈顶位置的指针
}

(1)初始化栈
void inistack(seqstack &s)
{
=0;
}
(2) 进栈
void push(seqstack &s, elemtype x)
{
if (==maxsize-1} cout<<”overflow”;
else
{
++;
[]=x;
}
}
(3) 退栈
void pop(seqstack &s)
{
if (= =0) cout<<”underflow”;
else
--;
}
(4) 取栈顶元素
elemtype gettop(seqstack s)
{
if (= =0) {cout<<”underflow”;return 0;}
else return [];
}