文档介绍：第3章栈和队列
本章学****线性表中两种特殊的线性表:栈和队列,其逻辑结构与前一章所学的线性表一样,均为线性结构,但它们是操作受限的线性表。当插入、删除操作只能在表的一端进行时称为栈。当插入从表的一端进行,删除从表的另一端进行时称为队列。
栈和队列在递归、模拟现实过程中都有重要的作用,掌握它们的相关概念及运算是十分必要的。本章除了讨论栈和队列的定义、表示方法和实现外,还将给出一些应用的例子。
栈的基本概念
栈的自然语言定义
栈(stack)是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端为变化的一端,称为栈顶(top),不允许插入和删除的一端称为栈底(bottom)。如图3-1所示:
图3-1 栈结构的示意图
向一个栈插入新元素的操作称为进栈或入栈(Push),它是把该元素放到栈顶元素的上面,使之成为新的栈顶元素。从一个栈删除一个元素的操作称为出栈或退栈(Pop),它是把栈顶元素删除掉,使其下面的相邻元素成为新的栈顶元素。当栈中无数据元素时,称为空栈。
由栈的定义可知,后入栈的元素先于先入栈的元素出栈,因此,栈的运算特性是后进先出(Last In First Out——LIFO)或先进后出(First In Last Out——FILO)。
在日常生活中,有许多类似栈的例子,如刷洗盘子时,把洗净的盘子一个接一个地向上放(相当于进栈),取用盘子时,则从上面一个接一个地向下拿(相当于出栈);又如向自动步枪的弹夹装子弹,子弹被一个接一个地压入(相当于进栈),射击时总是后压入的先射出(相当于出栈)。
栈的ADT定义
ADT Stack{
数据对象:D={ai|ai∈ElemSet,i=1,2, …,n,n≥1}
数据关系:R1={<ai-1,ai>| ai-1,ai∈D,i=2,3, …,n}
基本操作:
InitStack(S):初始化操作,设定一个空栈S;
EmptyStack(S):判断栈S是否为空,若S为空栈,则函数返回1,否则返回0;
Push(S,e):入栈操作,在栈S顶部插入元素e;若栈满返回0,否则将e入栈,并返回1;
Pop(S):出栈操作,若S不空,则返回栈顶元素,并删除栈顶元素;否则返回0;
GetTop(S):取栈顶元素操作,返回栈顶元素;
StackLength(S):返回栈S中当前元素的个数;
ClearStack(S):将S置为空栈;
……
}ADT Stack
栈的顺序存储结构及其运算
栈的顺序存储结构
顺序存储结构的栈又称顺序栈,与第二章讨论的顺序表类似,可利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。因此,我们可以使用预设的足够长度的一维数组来实现。由于栈顶的位置经常变动,通常设一个指示器top指向栈顶元素所在的位置。当有新元素进栈时,栈顶指针向上移动,top加1。当有元素出栈时,栈顶指针向下移动,top减1。
注意,在顺序栈中,top是整型变量,相当于数组的下标,top总是指向栈顶元素在栈中的位置。
用C语言描述顺序栈的数据类型如下:
#define MAXSIZE 100 //栈允许存放元素个数的最大值
typedef struct
{ ElemType datas[MAXSIZE];//栈的存储空间
int top;//栈顶指示器
}SqStack;
在这个描述中,用数组datas[MAXSIZE]作为栈的存储空间,datas[top]为栈顶元素,鉴于C语言中数组下标是从0开始的,我们约定当top=-1时栈为空;当top=0时,栈中有一个元素;当top=MAXSIZE-1时,表示栈满。
图3-2说明了顺序栈中数据元素与栈顶指针的变化,(a)表示空栈状态;(b)表示有二个元素A,B相继入栈后的状态;(c)表示栈满;(d)是在图(c)之后,元素相继出栈,此时栈中还有3个元素。也许最近出栈的元素仍在原先的单元中存储着,但top已经指向了新的栈顶,我们认为出栈的元素已经不在栈中了。
图3-2 栈的状态及栈顶指针示意图
当top=-1,即栈为空时,从空栈中再删除一个元素,栈将溢出,称为“下溢”。当top=MAXSIZE-1,即栈满时,向栈中再插入一个元素,栈也将溢出,称为“上溢”。
顺序栈的基本操作
void InitStack(SqStack *S)
{ S->top=-1;
}//InitStack
int EmptyStack(SqStack *S) //若栈空返回1;否则返回0
{ if(S->top==-1) return 1;
else return 0;
}//Empty