文档介绍：第3章栈(Stack)和队列(Queue)
栈(Stack)
栈的应用举例
(The examples of stack)
队列(Queue)
第3章栈(Stack)和队列(Queue)
栈(Stack)
栈和队列是两种特殊的线性表,由于它们在计算机科学中有着极其重要的作用,所以本章进行专门的讨论。
一、栈的定义
栈是线性表,通常记为:
S=(a1,…,ai,…,an)
它只允许在表尾进行插入和删除操作,因此栈是操作受限的线性表。
⑷由于栈具有后进先出的特点,所以栈又被称为后进先出的线性表或者LIFO结构。
⑴表尾位置被称为栈顶,处于栈顶位置的元素an称为栈顶元素。相应地,表头位置称为栈底,处于栈底位置的元素a1称为栈底元素。
⑵如果想向栈S中插入一新的元素b,只能插在栈顶元素即an之后,插入后b成为新的栈顶元素,向栈中插入元素的操作称为入栈(push)。还可以把元素c入栈,此时c成为新的栈顶元素。
⑸当S为空表时称为空栈。
⑶如果想从栈中删除一个数据元素,只能删除栈顶元素即c,删除后b成为新的栈顶元素,删除栈中元素的操作称为出栈(pop)。还可以再做出栈操作,这次出栈的是数据元素b,此时an成为新的栈顶元素。
一、栈的定义
栈在日常生活中十分常见。例如,
⑴刷盘子时,依次把每个洗净的盘子放到洗好的盘子上相当于入栈;用盘子时,从上到下依次取走每个盘子相当于出栈。
⑵向***弹夹里压入一粒粒子弹相当于入栈;射击时子弹总是从顶部被一个接一个地射出,此为子弹出栈。
⑶火车掉头时,也有入栈和出栈动作。
1
2
1
2
1
2
二、栈的抽象数据类型
P44用抽象数据类型 Stack 描述了栈及其基本操作。
ADT Stack {
数据对象:D={ai |ai∈ElemSet,i=1, …,n,n≥0}
数据关系:R1={<ai-1,ai> |ai-1,ai∈D,i=2, …,n}
基本操作:
InitStack(&S)
操作结果:构造一个空栈S。
DestroyStack(&S)
初始条件:栈S已经存在。
操作结果:销毁栈S 。
…………
}ADT Stack
栈的基本操作
InitStack(&S)
操作结果:构造一个空的栈S。
DestroyStack(&S)
初始条件:栈S 已存在。
操作结果:销毁栈S。
StackEmpty(S)
初始条件:栈S 已存在。
操作结果:若S为空栈,则返回TRUE,否则FALSE。
栈的基本操作
StackLength(S)
初始条件:栈S 已存在。
操作结果:返回S中元素个数。
GetTop(S,&e)
初始条件:栈S已存在且非空。
操作结果:用 e 返回S的栈顶元素。
Push(&S,e)
初始条件:栈S已存在。
操作结果:插入元素e作为新的栈顶元素。
栈的基本操作
Pop(&S,&e)
初始条件:栈S 已存在且非空。
操作结果:删除S的栈顶元素,并用e返回其值。
StackTraverse(S,visit( ))
初始条件:栈S已存在,visit() 为某个访问函数。
操作结果:依次对S的每个元素调用函数visit( )。
现在再来理解一下栈是特殊的线性表的含义:
栈的基本操作是线性表操作的子集;
对栈的修改总是在栈顶进行的。
三、栈的基本操作举例
例一、在对栈S经过以下运算后,其栈顶元素为( )。
InitStack(S);
Push(S,a);
GetTop(S,b);
Push(S,c);
Pop(S,x);
例二、假设A、B、C三个元素进S栈的顺序是A、B、C,且在进栈操作时,允许退栈操作,写出所有可能的出栈序列。
① ABC
② ACB
③ BAC
④ BCA
⑤ CBA
a
四、栈的顺序表示和实现
与线性表类似,栈也有顺序和链式两种存储方案。
(一)、栈的顺序表示
对于栈 S=(a1,…,ai,…,an),其顺序表示就是用一组地址连续的存储单元来依次存放自栈底到栈顶的元素,并附设一个指针 top 来指示栈顶元素的位置。
这样得到的存储结构简称顺序栈。
top→
an
…
a2
base→
a1
为了描述这种存储结构,我们给出如下定义:
#define STACK_INIT_SIZE 100 //基本容量
#define STACKINCREMENT 10 //增量
typedef struct{
ElemType *base; //栈底指针,始终指向栈底。