数据结构-栈与队列课件

栈、队列、串是常用数据结构。其中栈与队列不仅可直接用于描述问题，而且大量用于算法的实现中。串多用于直接描述非数值的简单信息。 从数据元素间的逻辑关系看，栈、队列与串是线性表，但从操作方式与种类看，它们与线性表有许多不同。因此，若把数据间逻辑关系与相应的操作作为整体看待（即作为抽象数据类型），它们应为新的数据结构。事实上，栈与队列是操作受限的线性表，串是元素受限的线性表。尽管它们与线性表有许多共同点，但也有不少特殊性。本章重点介绍这些特殊性，并给出一些典型的应用实例。第三章栈和队列 栈、队列、串是常用数据结构。其中栈与队列不仅可直接用于描述1通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性23.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.5离散事件模拟(本节内容不作要求)第三章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现33￡3.1.1栈的定义￡3.1栈栈（stack）：是限定仅在表尾进行插入和删除操作的线性表。又称为后进先出（lastinfirstout）的线性表（简称LIFO结构）。

栈顶（top）：栈表尾端。 栈底（bottom）：栈表头端。例：假设栈，则称为栈底元素，为栈顶元素。栈中元素按的次序进栈，退栈的第一个元素应为栈顶元素。如图3.1所示。

出栈进栈

栈顶an . . .

a2栈底 a1

图3.1栈的示意图￡3.1.1栈的定义￡3.1栈栈（sta4在现实世界中，有许多符合栈模型的例子。例如，火车扳道站、进入单车道死胡同的汽车等，都是栈的例子。在计算机系统中，栈的例子更是多见。例如，记录中断返回地址（断点）的结构就是栈。在中断发生时，为了处理完中断事件后恢复被中断事件的继续执行，需记下断点。在允许多级中断的情况下，中断处理过程仍可能被其它中断所中断，因此，系统可能同时要保存多个断点。由于中断恢复是先恢复最近被打断的过程，所以断点的保存次序与取出次序正好相反，这正好满足栈的特性。栈中元素除具有线性关系外，还具有先进后出的特性。所以在应用时，应根据这两点决定是否使用栈。在现实世界中，有许多符合栈模型的例子。5￡3.1.2栈的顺序存储结构

（1）定义顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。（2）C语言描述 typedefstruct{ SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //栈当前可使用的最大容量。 }SqStack;（3）图形表示

topbasetopbasetopbaseAABCDE图3.2 栈的顺序存储结构示意图

￡3.1.2栈的顺序存储结构（1）定义（2）C语言描述（6（4）ADTStack的表示和实现 #define STACK_INIT_SIZE 100; //存储空间初始分配量 #define STACKINCREMENT 10; //存储空间分配增量 typedefstruct{ SElemType *base; //在构造之前和销毁之后， //base的值为NULL SElemType *top; //栈顶指针 int stacksize; //栈当前可使用的最大容量。 }SqStack;//-----------------基本操作的函数原型说明------------------ StatusInitStack(SqStack&S); //构造一个空栈S StatusDestroyStack(SqStack&S); //销毁栈S，栈S不再存在 StatusClearStack(SqStack&S); //把S置为空栈 StatusStackEmpty(SqStackS); //若S为空栈，则返回TRUE，否则返回FALSE StatusStackLength(SqStackS); //返回S的元素个数，即栈的长度（4）ADTStack的表示和实现//----------7StatusGetTop(SqStackS,SElemType&e);//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORStatusPush(SqStack&S,SElemTypee);//插入元素e为新的栈顶元素StatusPop(SqStack&S,SElemType&e);//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORStatusStackTraverse(SqStackS,Status(*visit)());//从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败StatusGetTop(SqStackS,SEl8

GetTop(S,&e)

初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……GetTop(S,&e)

初始条件：栈S已存在且9Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。a1a2ane……Push(&S,e)

初始条件：栈S已存在。

10Pop(&S,&e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1

……Pop(&S,&e)

初始条件：栈S已存在且非空。11 //-----------------基本操作的算法描述（部分）------------------ StatusInitStack(SqStack&S){ //构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S=S.base; S.stacksize=STACK_INIT_SIZE; returnOK; }//InitStack //-----------------基本12 StatusGetTop(SqStackS,SElemType&e){ //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S==S.base) returnERROR; e=*(S－1); returnOK; }//GetTop StatusGetTop(SqStackS,SE13 StatusPush(SqStack&S,SElemTypee){ //插入元素e为新的栈顶元素 if(S－S.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; returnOK; }//Push StatusPush(SqStack14StatusPop(SqStack&S,SElemType&e){ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK； //否则返回ERROR if(S==S.base) returnERROR; e=*――S; returnOK;}//PopStatusPop(SqStack&15栈顶指针链栈∧a1an注意:链栈中指针的方向an-1栈底元素链栈的定义：Typedefstructnode{intdata;structnode*link;}JD栈顶指针链栈∧a1an注意:链栈中指针的方向an-1栈底16链栈的特点---（1）插入和删除（进栈/退栈）仅能在表头位置上（栈顶）进行。（2）链栈中的结点是动态产生的，可不考虑上溢问题。（3）不需附加头结点，栈顶指针就是链表（即链栈）的头指针。链栈的特点---17 栈、队列、串是常用数据结构。其中栈与队列不仅可直接用于描述问题，而且大量用于算法的实现中。串多用于直接描述非数值的简单信息。 从数据元素间的逻辑关系看，栈、队列与串是线性表，但从操作方式与种类看，它们与线性表有许多不同。因此，若把数据间逻辑关系与相应的操作作为整体看待（即作为抽象数据类型），它们应为新的数据结构。事实上，栈与队列是操作受限的线性表，串是元素受限的线性表。尽管它们与线性表有许多共同点，但也有不少特殊性。本章重点介绍这些特殊性，并给出一些典型的应用实例。第三章栈和队列 栈、队列、串是常用数据结构。其中栈与队列不仅可直接用于描述18通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性193.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.5离散事件模拟(本节内容不作要求)第三章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现320￡3.1.1栈的定义￡3.1栈栈（stack）：是限定仅在表尾进行插入和删除操作的线性表。又称为后进先出（lastinfirstout）的线性表（简称LIFO结构）。

栈顶（top）：栈表尾端。 栈底（bottom）：栈表头端。例：假设栈，则称为栈底元素，为栈顶元素。栈中元素按的次序进栈，退栈的第一个元素应为栈顶元素。如图3.1所示。

出栈进栈

栈顶an . . .

a2栈底 a1

图3.1栈的示意图￡3.1.1栈的定义￡3.1栈栈（sta21在现实世界中，有许多符合栈模型的例子。例如，火车扳道站、进入单车道死胡同的汽车等，都是栈的例子。在计算机系统中，栈的例子更是多见。例如，记录中断返回地址（断点）的结构就是栈。在中断发生时，为了处理完中断事件后恢复被中断事件的继续执行，需记下断点。在允许多级中断的情况下，中断处理过程仍可能被其它中断所中断，因此，系统可能同时要保存多个断点。由于中断恢复是先恢复最近被打断的过程，所以断点的保存次序与取出次序正好相反，这正好满足栈的特性。栈中元素除具有线性关系外，还具有先进后出的特性。所以在应用时，应根据这两点决定是否使用栈。在现实世界中，有许多符合栈模型的例子。22￡3.1.2栈的顺序存储结构

（1）定义顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。（2）C语言描述 typedefstruct{ SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //栈当前可使用的最大容量。 }SqStack;（3）图形表示

topbasetopbasetopbaseAABCDE图3.2 栈的顺序存储结构示意图

￡3.1.2栈的顺序存储结构（1）定义（2）C语言描述（23（4）ADTStack的表示和实现 #define STACK_INIT_SIZE 100; //存储空间初始分配量 #define STACKINCREMENT 10; //存储空间分配增量 typedefstruct{ SElemType *base; //在构造之前和销毁之后， //base的值为NULL SElemType *top; //栈顶指针 int stacksize; //栈当前可使用的最大容量。 }SqStack;//-----------------基本操作的函数原型说明------------------ StatusInitStack(SqStack&S); //构造一个空栈S StatusDestroyStack(SqStack&S); //销毁栈S，栈S不再存在 StatusClearStack(SqStack&S); //把S置为空栈 StatusStackEmpty(SqStackS); //若S为空栈，则返回TRUE，否则返回FALSE StatusStackLength(SqStackS); //返回S的元素个数，即栈的长度（4）ADTStack的表示和实现//----------24StatusGetTop(SqStackS,SElemType&e);//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORStatusPush(SqStack&S,SElemTypee);//插入元素e为新的栈顶元素StatusPop(SqStack&S,SElemType&e);//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORStatusStackTraverse(SqStackS,Status(*visit)());//从栈底到栈顶依次对栈中每个元素调用函数visit()。一旦visit()失败，则操作失败StatusGetTop(SqStackS,SEl25

GetTop(S,&e)

初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……GetTop(S,&e)

初始条件：栈S已存在且26Push(&S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。a1a2ane……Push(&S,e)

初始条件：栈S已存在。

27Pop(&S,&e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1

……Pop(&S,&e)

初始条件：栈S已存在且非空。28 //-----------------基本操作的算法描述（部分）------------------ StatusInitStack(SqStack&S){ //构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S=S.base; S.stacksize=STACK_INIT_SIZE; returnOK; }//InitStack //-----------------基本29 StatusGetTop(SqStackS,SElemType&e){ //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S==S.base) returnERROR; e=*(S－1); retu