文档介绍：第3章栈和队列
本章要点:
栈和队列两种抽象数据类型的特点。
栈用两种存储结构表示时的基本操作算法的实现。
栈和队列的应用。
线性表的操作允计在表的任何位置进行。
本章介绍的两种特殊的线性表,是操作受限制的特殊线性表——栈(Stack)和队列(Queue),其特殊性在于限制了插入和删除等运算的位置。
栈
栈是用来保存一些尚未处理而又等待处理的数据项这些数据项的处理是依据后进先出的规则。因此,经常把栈叫做后进先出线性表。
栈在日常生活中几乎到处可见,如火车进库时,库的一端是堵死的,那么最后入库的火车必须先出来,否则前面的列车都被堵住,无法倒出。栈是这种事务的一种抽象。
栈的意义及抽象数据类型
栈是将线性表的插入和删除运算限制为仅在表的一端进行的线性表。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)。栈顶的当前位置是动态变化的,表的另一端称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈,删除操作称为出栈或退栈。不含元素的栈称为空栈。
假设栈s=(a1,a2…,an),a1元素所在的位子称为栈底,an元素所在的位子称为栈顶,。
进栈顺序是a1,a2…an,退栈的第一个元素是an,最后一个元素是a1是按“后进先出”的原则进行的,因此栈又称为后进先出(Last In First Out),缩写为(LIFO)的线性表。
栈
bottom
top
┇
an
┇
a3
a2
a1
栈的意义及抽象数据类型(续)
进栈
出栈
。在日常生活中还有一些类似栈的例子。例如:往箱子里放衣物,这相当于进栈最先放的衣服在箱底(栈底),最后放的在箱顶(栈顶),取时应先从箱顶开始拿,这相当于出栈操作。
栈的意义及抽象数据类型(续)
栈的意义及抽象数据类型(续)
栈的基本操作除了在栈顶进行插入或删除外,还有栈的初始化、清空及取栈顶元素等,下面给出栈的抽象数据类型定义:
ADT stack {
数据元素:可以是任意类型的数据,但必须属于同一个数据对象。
数据关系:栈中数据元素之间是线性关系。
基本操作:
⑴ InitStack(S):将S初始化为空栈。
⑵ ClearStack(S):栈S已经存在,将栈S置成空栈。
⑶ EmptyStack(S):栈S已经存在,判断若S为空,函数值返回TRUE,否则返FALSE。
⑷ DestroyStack(S):栈S已经存在,销毁栈并释放空间。
⑸ Push(S,x):栈S已经存在,若S栈未满,将x插入S栈的栈顶位置,函数返回TRUE;若S栈已满,则返回FALSE,表示操作失败。
⑹ Pop(S, x):栈S已经存在,在栈S的顶部弹出栈顶元素,并用x带回该值;若栈为空,返回值为FALSE,表示操作失败,否则返回TRUE。
⑺ GetTop(S, x):栈S已经存在,取栈S的栈顶元素,其余不变。
(8)Stacklenth(S)栈S已经存在,返回栈中元素个数。
}ADT stack
栈的意义及抽象数据类型(续)
栈操作的实现
与线性表一样,栈的存储方式也有两种:顺序存储和链表存储方式。
栈的顺序存储结构
栈的顺序存储结构即顺序栈是分配一块连续的存储区域依次存放自栈底到栈顶的数据元素,同时设指针top来动态地指示栈顶元素的当前位置。空栈top=0或 top=-1表示。下面的顺序栈,采用的是top指向栈顶元素的后一个元素位置的方式来描述,当空栈时top=0。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下:
#define Stack-Size 50
typedef struct
{
elemtype elem[Stack-Size]; /*存放栈元素的一维数组*/
int top; /*存放栈顶元素的下标*/
}SeqStack;
若s为SeqStack类型变量,[0]存放栈中第一个元素,[-1]为最后一个元素(栈顶元素)。= Stack-Size时为栈满,此时若再有元素入栈则将产生越界的错误,称为栈上溢(overflow),反之,top=0 时为栈空,这时若执行出栈操作则产生下溢的错误(underflow)。。
栈操作的实现(续)