数据结构第3章栈和队列ppt

1栈2算术表达式求值3队列第三章栈和队列本章学习导读从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作;而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。通过本章的学习，读者应能掌握栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算和算法的实现。4学时3.1栈在各种程序设计语言中都有子程序（或称函数、过程）调用功能。而子程序也可以调用其它的子程序。甚至可以直接或间接地调用自身，这种调用关系就是递归。下面以求阶乘的递归方法为例，来分析计算机系统是如何处理这种递归调用关系的。求n！的递归方法的思路是：相应的C语言函数是：floatfact(intn){floats;if(n==0||n==1)s=1;elses=n*fact(n-1);return(s);}在该函数中可以理解为求n！用fact(n)来表示，则求(n-1)！就用fact(n-1)来表示。若求5!，则有main(){printf(“5!=%f\n”,fact(5));})1()1,0()!1(*1!=-=nnnnn图3-1给出了递归调用执行过程。从图中可看到fact函数共被调用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)为主函数调用，其它则为在fact函数内的调用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact才有结果为1，然后再一一返回计算，最终得到结果。主函数mani()printf(“fact(5)”)第一层调用n=5s=5*fact(4)第二层调用n=4s=4*fact(3)第三层调用n=3S=3*fact(2)第四层调用n=2S=2*fact(1)第五层调用n=1S=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24fact(5)=120输出s=120.00图3-1递归调用过程示意图计算机系统处理上述过程时，其关键是要正确处理执行过程中的递归调用层次和返回路径，也就是要记住每一次递归调用时的返回地址。在系统中是用一个线性表(栈)动态记忆调用过程中的路径，其处理原则为：（1）在开始执行程序前，建立一个线性表，其初始状态为空。（2）当发生递归调用时，将当前的调用的返回点地址插入到线性表的末尾；（3）当递归调用返回时，其返回地址从线性表的末尾取出。根据以上的原则，可以给出线性表中的元素变化状态如图3-2所示（以递归调用时n值的变化为例）：545453453245321图3-2递归调用时线性表状态入栈出栈3.1.1栈的定义及其运算1．栈的定义栈（stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照后进先出（LIFO，lastinfirstout）的原则组织数据的，因此，栈也被称为“后进先出”的线性表。a1a2an入栈出栈栈顶top栈底bottom图3-3栈的示意图．．．图3-3是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。2．栈的基本运算（1）initStack(s)初始化：初始化一个新的栈。（2）IsEmpty(s)栈空判断：若栈s空，则返回TRUE；否则，返回FALSE。（3）push(s,x)入栈：在栈s的顶部插入元素x，若栈满，则返回FALSE；否则，返回TRUE。（4）pop(s,x)出栈：若栈s不空，则返回栈顶元素，并从栈顶中删除该元素；否则，返回空元素NULL。（5）getTop(s,x)取栈元素：若栈s不空，则返回栈顶元素；否则返回空元素NULL。（6）ClearEmpty(s)置栈空操作：置栈s为空栈。栈是一种特殊的线性表，因此栈可采用顺序存储结构存储，也可以使用链式存储结构存储。（7）stacklenth(s)返回栈中元素的个数.3.1.2栈的顺序存储结构1．顺序栈的数组表示与第二章讨论的一般的顺序存储结构的线性表一样，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈也称为顺序栈。因此，我们可以使用一维数组来作为栈的顺序存储空间。设指针top指向栈顶元素的下一个位置，以数组小下标的一端作为栈底，通常以top=0时为空栈，在元素进栈时指针top不断地加1，当top等于数组的最大下标值时则栈满。top=0top=1Atop=5top=3图3-4栈的存储结构（a）空栈（b）插入元素A后（c）插入元素B、C、D、E后d）删除元素E、D后（a）（b）（c）（d）图3-4展示了顺序栈中数据元素与栈顶指针的变化。ABABCCDEbasebasebasebase43210432104321043210用C语言定义的顺序存储结构的栈如下：#defineTRUE1#defineFALSE0#defineSTACK_SIZE50;//存储空间分配增量typedefstruct{StackElementTypeelem[STACK_SIZE];inttop;}SqStack;2．顺序栈的基本运算算法（1）初始化栈【算法3.1栈的初始化】StatusInitStack(SqStack*S){//创建一个空栈由指针S指出S-TOP=0;}//InitStack（2）入栈操作【算法3.2入栈操作】StatusPush(SqStack&S,SElemTypee){//将元素e插入到栈S中，作为S的新栈顶if(S-top==Stacksize)returnFALSE;S-elem[top]=e;S-top++;returnTRUE;}//Push（3）出栈操作【算法3.3出栈操作】StatusPop(SqStack*S,SElemType*e){//若栈s不为空，则删除栈顶元素,有e返回其值，并返回TRUE；否则返回ERRORif(S-top==0)returnERROR;//栈空elseS-top--;*e=S-elem[S-top];returnTRUE;}//Pop（4）取栈顶元素操作【算法3.4取栈顶元素】StatusGetTop(SqStackS,SElemType*e){//若栈S不为空，则用e返回栈顶元素，并返回OK；否则返回ERRORif(S-top==0)returnERROR;//栈空else{*e=S-elem[S-top–1];returnOK;}}//GetTop取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针top的位置，而取栈顶元素操作不改变栈的栈顶指针。（5）判断栈空intIsEmpty(SeqStack*s){return(S-top==0?TRUE:FALSE);}（6）求栈顶元素个数intIsFull(SeqStack*S){return(S-top);}3.1.3多栈共享邻接空间在计算机系统软件中，各种高级语言的编译系统都离不开栈的使用。常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间，但实际中很难准确地估计。另一面方面，若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使它们的存储空间互补。这就是栈的共享邻接空间。1．双向栈在一维数组中的实现栈的共享中最常见的是两栈的共享。假设两个栈共享一维数组stack[MAXNUM]，则可以利用栈的“栈底位置不变，栈顶位置动态变化”的特性，两个栈底分别为-1和MAXNUM，而它们的栈顶都往中间方向延伸。因此，只要整个数组stack[MAXNUM]未被占满，无论哪个栈的入栈都不会发生上溢。C语言定义的这种两栈共享邻接空间的结构如下：Typedefstruct{Elemtypestack[MAXNUM];intlefttop;/*左栈栈顶位置指示器*/intrighttop;/*右栈栈顶位置指示器*/}dupsqstack;两个栈共享邻接空间的示意图如图3-5所示。左栈入栈时，栈顶指针加1，右栈入栈时，栈顶指针减1。自由区lefttoprightto0MAXNUM-1图3-5两个栈共享邻接空间charstatus;status=’L’;/*左栈*/status=’R’;/*右栈*/在进行栈操作时，需指定栈号：status=’L’为左栈，status=’R’为右栈；判断栈满的条件为：s-lefttop+1==s-rigthtop;为了识别左右栈，必须另外设定标志：2．共享栈的基本操作（1）初始化操作【算法3.7共享栈的初始化】intinitDupStack(dupsqstack*s){/*创建两个共享邻接空间的空栈由指针S指出*/if((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL)returnFALSE;s-lefttop=-1;s-righttop=MAXNUM;returnTRUE;}（2）入栈操作【算法3.8共享栈的入栈操作】intpushDupStack(dupsqstack*s,charstatus,Elemtypex){*把数据元素x压入左栈（status=’L’）或右栈（status=’R’）*/if(s-lefttop+1==s-righttop)returnFALSE;/*栈满*/if(status=’L’)s-stack[++s-lefttop]=x;/*左栈进栈*/elseif(status=’R’)s-stack[--s-lefttop]=x;/*右栈进栈*/elsereturnFALSE;/*参数错误*/returnTRUE;}（3）出栈操作【算法3.9共享栈的出栈操作】ElemtypepopDupStack(dupsqstack*s,charstatus){/*从左栈（status=’L’）或右栈（status=’R’）退出栈顶元素*/if(status==’L’){if(s-lefttop0)returnNULL;/*左栈为空*/elsereturn(s-stack[s-lefttop--]);/*左栈出栈*/}elseif(status==’R’){if(s-righttopMAXNUM-1)returnNULL;/*右栈为空*/elsereturn(s-stack[s-righttop++]);/*右栈出栈*/}elsereturnNULL;/*参数错误*/3.1.4栈的链式存储结构栈也可以采用链式存储结构表示，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。因此，新入栈的元素即为链表新的第一个结点，只要系统还有存储空间，就不会有栈满的情况发生。一个链栈可由栈顶指针top-next唯一确定，当top-next为NULL时，是一个空栈。图3-6给出了链栈中数据元素与栈顶指针top的关系。链栈的C语言定义为：typedefstructStacknode{Elemtypedata;StructStacknode*next;}slStacktype;BA∧Top-nextCA∧Top-next（a）含有两个元素A、B、C的栈（b）删除元素C、B后的栈图3-6链栈的存储结构图（a）（b）（1）入栈操作【算法3.10单个链栈的入栈操作】intpushLstack(slStacktype*top,Elemtype*x){//将元素x压入链栈top中slStacktype*p;if((p=(slStacktype*)malloc(sizeo