1、栈、队列、串是常用数据结构。其中栈与队列不仅可直接用于描述问题，而且大量用于算法的实现中。串多用于直接描述非数值的简单信息。从数据元素间的逻辑关系看，栈、队列与串是线性表，但从操作方式与种类看，它们与线性表有许多不同。因此，若把数据间逻辑关系与相应的操作作为整体看待（即作为抽象数据类型），它们应为新的数据结构。事实上，栈与队列是操作受限的线性表，串是元素受限的线性表。尽管它们与线性表有许多共同点，但也有不少特殊性。本章重点介绍这些特殊性，并给出一些典型的应用实例。第三章第三章 栈和队列栈和队列通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。线性表线性表 栈栈
2、队列队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Delete(Q,1)1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型3.1 栈栈3.2 栈的应用举例栈的应用举例3.3 栈与递归的实现栈与递归的实现3.4 队列队列3.5 离散事件模拟离散事件模拟(本节内容不作要求本节内容不作要求)第三章第三章 栈和队列栈和队列3.1.1 栈的定义栈的定义3.1 栈栈 栈（栈（stack）：是限定仅在表尾进行插入和删除操作的线性表。又称为后）：是限定仅在表尾进行插入和删除操作的线性表。又称为后进先
3、出（进先出（last in first out）的线性表（简称）的线性表（简称LIFO结构）。结构）。栈顶（栈顶（top）：栈表尾端。）：栈表尾端。栈底（栈底（bottom）：栈表头端。）：栈表头端。),(21naaaSnaaa,211ana 例：假设栈例：假设栈 ，则，则 称为栈底元素，称为栈底元素，为栈顶元素。栈中为栈顶元素。栈中元元素按素按 的次序进栈，退栈的第一个元素应为栈顶元素。如图的次序进栈，退栈的第一个元素应为栈顶元素。如图3.1所示。所示。出栈出栈 进栈进栈 栈顶栈顶 an .a2 栈底栈底 a1 图图3.1 栈的示意图栈的示意图 在现实世界中，有许多符合栈模型的例子。例如，火
4、车扳道站、进入单车道死胡同的汽车等，都是栈的例子。在计算机系统中，栈的例子更是多见。例如，记录中断返回地址（断点）的结构就是栈。在中断发生时，为了处理完中断事件后恢复被中断事件的继续执行，需记下断点。在允许多级中断的情况下，中断处理过程仍可能被其它中断所中断，因此，系统可能同时要保存多个断点。由于中断恢复是先恢复最近被打断的过程，所以断点的保存次序与取出次序正好相反，这正好满足栈的特性。栈中元素除具有线性关系外，还具有先进后出的特性。所以在应用时，应根据这两点决定是否使用栈。3.1.2 栈的顺序存储结构栈的顺序存储结构（1）定义）定义 顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元
5、依次存放顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。指示栈顶元素在顺序栈中的位置。（2）C语言描述语言描述typedef struct SElemType*base;/栈底指针栈底指针SElemType*top;/栈顶指针栈顶指针int stacksize;/栈当前可使用的最大容量。栈当前可使用的最大容量。SqStack;（3）图形表示）图形表示 topbasetopbasetopbaseAABCDE图图3.2栈的顺序存储结构示意图栈的顺序存储结构示意图（4）ADT
6、 Stack的表示和实现的表示和实现#defineSTACK_INIT_SIZE100;/存储空间初始分配量存储空间初始分配量#defineSTACKINCREMENT10;/存储空间分配增量存储空间分配增量typedef struct SElemType*base;/在构造之前和销毁之后，在构造之前和销毁之后，/base的值为的值为NULLSElemType*top;/栈顶指针栈顶指针int stacksize;/栈当前可使用的最大容量。栈当前可使用的最大容量。SqStack;/-基本操作的函数原型说明基本操作的函数原型说明-Status InitStack(SqStack&S);/构造一个
7、空栈构造一个空栈SStatus DestroyStack(SqStack&S);/销毁栈销毁栈S，栈，栈S不再存在不再存在Status ClearStack(SqStack&S);/把把S置为空栈置为空栈Status StackEmpty(SqStack S);/若若S为空栈，则返回为空栈，则返回TRUE，否则返回，否则返回FALSEStatus StackLength(SqStack S);/返回返回S的元素个数，即栈的长度的元素个数，即栈的长度Status GetTop(SqStack S,SElemType&e);/若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并
8、返回OK；否则返回；否则返回ERRORStatus Push(SqStack&S,SElemType e);/插入元素插入元素e为新的栈顶元素为新的栈顶元素Status Pop(SqStack&S,SElemType&e);/若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e返回其值，并返回返回其值，并返回OK；否则返回；否则返回ERRORStatus StackTraverse(SqStack S,Status(*visit)();/从栈底到栈顶依次对栈中每个元素调用函数从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦。一旦visit()失败，则操作失败失败，则操作失
9、败 GetTop(S,&e)初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an Push(&S,e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。a1a2ane Pop(&S,&e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 /-基本操作的算法描述（部分）基本操作的算法描述（部分）-Status InitStack(SqStack&S)/构造一个空栈构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(ElemType)
10、;if(!S.base)exit(OVERFLOW);/存储分配失败存储分配失败S=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus GetTop(SqStack S,SElemType&e)/若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并返回OK；否则返回；否则返回ERRORif(S=S.base)return ERROR;e=*(S1);return OK;/GetTop Status Push(SqStack&S,SElemType e)/插入元素插入元素e为新的栈顶元素为新的栈顶元素if
11、(SS.base=S.stacksize)/栈满，追加存储空间栈满，追加存储空间 S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败存储分配失败 S=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S+=e;return OK;/Push Status Pop(SqStack&S,SElemType&e)/若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e返回其值，并返回返回其值，并返回OK；/否则返回否则返回ERRORif(S=S.base)return ERROR;e=*S;return OK;/Pop栈顶指针链栈链栈a1an注意注意:链栈中链栈中指针的方向指针的方向an-1栈底元素栈底元素链栈的定义：链栈的定义：Typedef struct node int data;struct node*link;JD&链栈的特点链栈的特点-（1）插入和删除（进栈/退栈）仅能在表头位置上（栈顶）进行。（2）链栈中的结点是动态产生的，可不考虑上溢问题。（3）不需附加头结点，栈顶指针就是链表（即链栈）的头指针。
