文档介绍：2017/12/27
1/40
第3章栈和队列
栈
队列
本章小结
2017/12/27
2/40
栈的定义
栈的顺序存储结构及其基本运算的实现
栈的链式存储结构及其基本运算的实现
栈的应用
栈(Stack)
a1
a2
a3
a4
a5
a6
插入 x
i
删除 x
j
插入
删除
2017/12/27
3/40
栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。
栈顶的当前位置是动态的,由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。
当栈中没有数据元素时,称为空栈。
栈的插入操作通常称为压栈或进栈,栈的删除操作通常称为退栈或出栈。
栈的主要特点是“后进先出”。也称为后进先出表。
栈的定义
2017/12/27
4/40
a1
a2
a3
入栈
栈底
栈顶
插入:入栈、进栈、压栈
栈顶
栈顶
栈的操作示意图
2017/12/27
5/40
后进先出
a1
a3
入栈
出栈
栈底
栈顶
删除:出栈、退栈、弹栈
栈顶
栈的操作示意图
a2
栈顶
2017/12/27
6/40
【】设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是。
(A) A,B,C,D (B) D,C,B,A
(C) A,C,D,B (D) D,A,B,C
答案:D
【】若元素进栈顺序为1-2-3-4,能否得到3142的出栈顺序?
答案:否
【】用S表示进栈操作,X表示出栈操作,若元素进栈顺序为1234,为了得到1342的出栈顺序,给出相应的S和X操作串。
答案:SXSSXSXX
2017/12/27
7/40
抽象数据类型栈的定义:《教材P65》
基本运算:
InitStack(&s):初始化栈,构造一个空栈s。
DestroyStack(&s):销毁栈,释放栈s占用的存储空间。
StackEmpty(s):判断栈是否为空:为空,则返回真;否则返回假。
Push(&s,e):进栈,将元素e插入到栈s中作为栈顶元素。
Pop(&s,&e):出栈,从栈s中退出栈顶元素,将其值赋给e。
GetTop(s,&e):取栈顶元素,返回当前的栈顶元素,并将其值赋给e。
2017/12/27
8/40
栈的顺序存储结构及其基本运算的实现
假设栈的元素个数最大不超过正整数MaxSize,所有元素都具有同一数据类型ElemType,则可用下列方式来定义顺序栈类型SqStack:
typedef struct{
ElemType data[MaxSize];
int top; //栈顶指针
} SqStack;
2017/12/27
9/40
栈空条件:top==-1
栈满条件:top==MaxSize-1
进栈操作:top++; 再将元素放在top处
退栈操作:从top处取出元素,再将top--;
例如:
2017/12/27
10/40
在顺序栈中实现栈的基本运算算法:
(1) 初始化栈InitStack(s) : s->top=-1;
(2) 销毁栈DestroyStack(s) : free(s);
(3) 判断栈是否为空StackEmpty(s): s->top==-1
(4) 进栈Push(s,e): s->top++; s->data[s->top]=e;
(5) 出栈Pop(s,e): e=s->data[s->top]; s->top--;
(6) 取栈顶元素GetTop(s,e): e=s->data[s->top];
注意栈空、栈满的条件!