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

《数据结构：第3章 栈和队列》由会员分享，可在线阅读，更多相关《数据结构：第3章 栈和队列（81页珍藏版）》请在金锄头文库上搜索。

1、第3章栈和队列概述两种特殊的线性表。逻辑结构和线性表相同。比起线性表其运算受限制，故又称它们为运算受限的线性表。栈和队列应用在各种程序设计中尤其栈的应用更广1.栈1.1栈的定义1.2顺序栈1.3链栈1.1栈的定义栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。(1)通常称插入、删除的这一端为栈顶栈顶（Top），另一端称为栈底栈底（Bottom）。(2)当表中没有元素时称为空栈空栈。(3)栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。 每次进栈的元素都被放在原栈顶元素之上而成为每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中新的栈顶，而每次

2、出栈的总是当前栈中“最新最新”的元的元素，即最后进栈的元素。因此，栈又称为素，即最后进栈的元素。因此，栈又称为后进先出的后进先出的线性表线性表。简称为。简称为LIFOLIFO表。表。栈的示意图a1a2an栈顶（表尾）栈底bottomtop入栈入栈push出栈出栈pop栈的示意图S3bottomtopS1S2S5S6S3S4S3S3S3S3S3PUSHPUSHPUSHPOPPUSHPUSHPUSH 栈在计算机中主要有两种基本的存储栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。结构：顺序存储结构和链式存储结构。l 顺序存储的栈为顺序栈顺序存储的栈为顺序栈l 链式存储的栈为链栈链

3、式存储的栈为链栈栈的存储方式1.2顺序栈栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。顺序栈的类型定义#defineTRUE1#defineFALSE0#defineStack_Size50typedefstructStackElementTypeelemStack_Size;/*一维数组*/inttop;/*用来存放栈顶元素的下标*/SeqStack; top空栈toptoptoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈ctopc 退栈b 退栈abaa 退栈空空栈topab

4、dd 退栈ctopabctoptop注意顺序栈中元素用向量存放栈底位置是固定不变的，可设置在向量两端的任意一个端点栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置顺序栈的基本运算（1）置栈空（初始化）（2）判栈空（3）判栈满（4）进栈操作（5）退栈操作（6）取栈顶元素（1）置栈空（初始化）voidInitStack（SeqStack*S）/将顺序栈置空S-top=-1;(2)判栈空intStackEmpty（SeqStack*S）/*判栈S为空栈时返回值为真，反之为假*/returnS-top=-1;（3）判栈满intStackFull（Se

5、qStack*S）/*判栈S为满时返回真，否则返回假*/returnS-top=StackSize-1;（4）进栈进栈时，需要将S-top加1注意：S-top=StackSize-1表示栈满上溢上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。voidPush（SeqStack*S，DataTypex）if(StackFull(S)Error(“Stackoverflow”);/上溢，退出运行S-data+S-top=x;/栈顶指针加1后将x入栈（5）退栈退栈时，需将S-top减1注意：S-topdataS-top-;/栈顶元素返回后将栈顶指针减1（6）取栈顶

6、元素DataTypeStackTop（S）if(StackEmpty(S)Error(Stackisempty);returnS-dataS-top;1.4链栈 链栈链栈是采用是采用链表链表作为存储结构实现的栈作为存储结构实现的栈，是线性，是线性链表的特例链表的特例。因为栈的插入和删除操作仅限制在表头。因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。位置进行，所以链表的表头指针就作为栈顶指针。 toptop为栈顶指针，始终指向当前栈顶元素结点。为栈顶指针，始终指向当前栈顶元素结点。若若top=NULLtop=NULL，则代表空栈。，则代表空栈。注意：注意：链栈在使

7、用完毕时，应该释放其空间。链栈在使用完毕时，应该释放其空间。注意注意: 链栈中指针的方向是从栈顶指向栈底方向链栈中指针的方向是从栈顶指向栈底方向栈顶指针栈顶指针topa1 an-1 an typedefstructstacknodeDataTypedatastructstacknode*nextStackNode;StackNode*head=NULL;typedefstructStackNode*top;/栈顶指针LinkStack;链栈的基本运算(1)置栈空(2)判栈空(3)进栈(4)退栈(5)取栈顶元素（1）置栈空voidInitStack(LinkStack*S)S-top=NULL;

8、(2)判栈空intStackEmpty(LinkStack*S)returnS-top=NULL;（3）进栈voidPush(LinkStack*S,DataTypex)/将元素x插入链栈头部StackNode*p=(StackNode*)malloc(sizeof(StackNode);if(p=NULL)printf(“内存空间不够分配”);exit(0);/return/健壮p-data=x;p-next=S-top;/将新结点*p插入链栈头部S-top=p;（4）退栈DataTypePop(LinkStack*S)DataTypex;StackNode*p=S-top;/保存栈顶指针i

9、f(StackEmpty(S)Error(Stackunderflow.);/下溢x=p-data;/保存栈顶结点数据S-top=p-next;/将栈顶结点从链上摘下free(p);returnx;将将x x入栈，修改栈顶入栈，修改栈顶指针指针:top=p:top=pa an n出栈，修改栈顶指出栈，修改栈顶指针针:top=top-next:top=top-next链栈的入栈操作和出栈操作（5）取栈顶元素DataTypeStackTop(LinkStack*S)if(StackEmpty(S)Error(Stackisempty.)returnS-top-data;注意链栈中的结点是动态分配的

10、，所以可以不考虑上溢，无须定义StackFull运算。2.队列2.1队列的定义2.2顺序队列2.3链队列 队列队列是一种特殊的线性表，限定插入和删除操作分别在表的两端进行。a1 a2 ai an队头 f队尾 r出队出队入队入队2.1队列的定义和基本运算队列的性质（1）允许删除的一端称为队头（队头（Front）。（2）允许插入的一端称为队尾（队尾（Rear）。（3）当队列中没有元素时称为空队列空队列。（4）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表表队列的进队和出队 front rear空队列front rearA进队Afront rearB进队A Bfron

11、t rearC, D进队A B C Dfront rearA退队B C Dfront rearB退队C Dfront rearE,F,G进进队C D E F GC D E F Gfront rearH进进队,溢出队列的进队和出队原则n 进队时队尾指针先进一进队时队尾指针先进一 rear = rear + 1， 再将新元素按再将新元素按 rear 指示位置加入。指示位置加入。n 出队时队头指针先进一出队时队头指针先进一 front = front + 1， 再将下标为再将下标为 front 的元素取出的元素取出。n 队满时再进队将队满时再进队将溢出出错溢出出错；n 队空时再出队将队空时再出队将队

12、空处理队空处理。n 解决办法之一：将队列元素存放数组首尾解决办法之一：将队列元素存放数组首尾 相接，形成相接，形成循环循环(环形环形)队列队列。 队列在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。l顺序存储的队列为顺序队列l链式存储的队列为链队列队列的存储方式队列的基本运算(1)初始化队列(2)判队空(3)判队满(4)入队(5)出队(6)取队首元素2.2顺序队列2.2.1顺序队列的定义2.2.2顺序队列的基本运算2.2.3循环队列2.2.1顺序队列的定义队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表 frontreara b c da b c d d e f

13、 d e f rear front rear顺序队列的表示和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，设置两个“指针”front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。2.2.2顺序队列的基本运算入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并返回被删元素。注意：当头尾指针相等时，队列为空。在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。 当Q-front= Q-rear 时,队列空。 当Q-rea

14、r+1MaxSize 时,队列满(即上溢出),但此时头指针指示的元素之前可能还有空单元,此现象称为假溢出;若把这样的顺序结构设想为一个循环表, 插入时就可以利用这些空单元, 这样就构成循环队列。假上溢2.2.3循环队列为充分利用向量空间，克服“假上溢”现象的方法：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。012345ENQUEUE1ENQUEUE2ENQUEUE3DEQUEUE1ENQUEUE4DEQUEUE2ENQUEUE5ENQUEUE6ENQUEUE7ENQUEUE8q1q2q3 q4 q5q6q7q8循环队列 （circular queue）满满空空?FRFRFRRR

15、RRRR 入队操作时的尾指针运算入队操作时的尾指针运算: rear=(rear+1)%Maxsize出队操作时的头指针运算出队操作时的头指针运算: front=(front+1)%Maxaize问题：问题：在循环队列中，由于队空时有在循环队列中，由于队空时有front=rear；队满时也有队满时也有front=rear；因因此我们无法通过此我们无法通过front=rear来判断队列是来判断队列是“空空”还是还是“满满”。循环队列示意图循环队列的几种状态循环队列的几种状态frontrear循环队列循环队列队满和队空队满和队空的描述方法的描述方法frontrear队空队空:队满队满:frontfr

16、ontrearrear rear=front（?）rear=front判断循环队列满和空的三种方法判断循环队列满和空的三种方法如何判断是“空”还是“满”。解决这个问题的方法至少有三种：设一布尔变量以区别队列的空和满，设置标志flag-flag=0表示空，flag=1表示满，front追上rear则flag=0，rear追上front则flag=1；留下一个单元不使用。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满，则rear永远也追不上front；使用一个计数器记录队列中元素的总数（即队列长度）。顺序循环队列的类型定义#defineQueueSize100/应根据具体

17、情况定义该值typedefcharDataType;/DataType的类型依赖于具体的应用typedefstructintfront;/头指针，队非空时指向队头元素intrear;/尾指针，队非空时指向队尾元素的下一位置intcount;/计数器，记录队中元素总数DataTypedataQueueSizeCirQueue;顺序循环队列的基本运算1.置队空置队空2.判队空判队空3.判队满判队满4.入队入队5.出队出队6.取队头元素取队头元素 置队空置队空voidInitQueue(CirQueue*Q)Q-front=Q-rear=0;Q-count=0;/计数器置0 判队空判队空intQue

18、ueEmpty(CirQueue*Q)/队列无元素为空，属第三种方法returnQ-count=0;intQueueEmpty(CirQueue*Q)/属第二种方法returnQ-rear=Q-front; 判队满判队满intQueueFull(CirQueue*Q)returnQ-count=QueueSize;/队中元素个数等于QueueSize时队满，属第三种方法intQueueFull(CirQueue*Q)return(Q-rear+1)%QueueSize=Q-front;/队中元素个数等于QueueSize时队满，属第二种方法 入队入队voidEnQueue(CirQueue*Q

19、,DataTypex)if(QueueFull(Q)Error(Queueoverflow);/队满上溢Q-count+;/队列元素个数加1Q-dataQ-rear=x;/新元素插入队尾Q-rear=(Q-rear+1)%QueueSize;/循环意义下将尾指针加1 出队出队DataTypeDeQueue(CirQueue*Q)DataTypetemp;if(QueueEmpty(Q)Error(Queueunderflow);/队空下溢temp=Q-dataQ-front;Q-count-;/队列元素个数减1Q-front=(Q-front+1)%QueueSize;/*循环意义下的头指针加

20、1*/returntemp;取队头元素取队头元素DataTypeQueueFront(CirQueue*Q)if(QueueEmpty(Q)Error(Queueifempty.);returnQ-dataQ-front;2.3链队列2.3.1链队列的定义2.3.2链队列的基本运算2.3.1链队列的定义队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。 队头在链头，队尾在链尾。队头在链头，队尾在链尾。a1anq.frontq.rearq.frontq.rear空队列空队列链队列的几种状态示意图此时，front=rear修改rear指针修改头结点的指针域链队列为空的特征：链

21、队列为空的特征：front=rearfront=rear 链队列会满吗链队列会满吗？一般不会，因为删除时有一般不会，因为删除时有freefree动作，除非内存不足！动作，除非内存不足！修改rear指针注意增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算定义链队列的存储结构t

22、ypedefcharDataType;typedefstructqueuenodeDataTypedata;structqueuenode*next;QueueNode;typedefstructQueueNode*front;QueueNode*rear;LinkQueue;2.3.2链队列的基本运算1.置空队2.判队空3.入队4.出队5.取队头元素（1）置空队int InitQueue( LinkQueue *Q )int InitQueue( LinkQueue *Q ) /构造一个空队列构造一个空队列 * *Q Q Q-front = (LQnode *)malloc(sizeof(L

23、Qnode); Q-front = (LQnode *)malloc(sizeof(LQnode); if( Q-front = NULL ) if( Q-front = NULL ) return FALSE; return FALSE; /申请内存失败返回申请内存失败返回 Q-rear = Q-front;Q-rear = Q-front; Q-front Q-front- next = NULL;next = NULL; return TRUE; return TRUE; /申请内存成功返回申请内存成功返回 （2）判队空intQueueEmpty(LinkQueue*Q)returnQ-

24、front-next=NULL&Q-rear-next=NULL;/*实际上只须判断队头指针是否为空即可*/（3）入队voidEnQueue(LinkQueue*Q,DataTypex)/将元素x插入链队列尾部QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);/申请新结点p-data=x;p-next=NULL;if(QueueEmpty(Q)Q-front-next=p;Q-rear=p;/将x插入空队列else/x插入非空队列的尾Q-rear-next=p;/*p链到原队尾结点后Q-rear=p;/队尾指针指向新的尾（4）出队DataType

25、DeQueue(LinkQueue*Q)DataTypex;QueueNode*p;if(QueueEmpty(Q)Error(“Queueunderflow”);/下溢p=Q-front-next;/指向队头结点x=p-data;/保存队头结点的数据Q-front-next=p-next;/将队头结点从链上摘下if(Q-rear=p)/原队中只有一个结点，删去后队列变空，此时队头指针已为空Q-rear=Q-front;free(p);/释放被删队头结点returnx;/返回原队头数据（5）取队头元素DataTypeQueueFront(LinkQueue*Q)if(QueueEmpty(Q)

26、Error(Queueifempty.);returnQ-front-next-data;3.栈的应用3.1函数调用3.2递归、非递归 当在一个函数的运行期间当在一个函数的运行期间调用另一个函数调用另一个函数时时, 在在运行该被调用函数之前运行该被调用函数之前, 需先完成三项任务：需先完成三项任务： 保存现场保存现场, 保存本函数参数、返回地址等保存本函数参数、返回地址等信息信息; 为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区传递参数传递参数; 将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。3.1 函数调用 从被调用函数从被调用函数返回返回调用函数调用函数之前

27、之前, 应该完成下列应该完成下列三项任务：三项任务：保存保存返回的返回的计算结果计算结果(用函数名用函数名,引用参数引用参数) ；释放释放被调函数的被调函数的数据区数据区, 恢复调用函数现场恢复调用函数现场 ;依照被保存的返回地址将依照被保存的返回地址将控制转移控制转移到调用函数。到调用函数。多个函数嵌套调用的规则多个函数嵌套调用的规则此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！例如：例如：main( ) void a( ) void b( ) a( ); b( ); /main / a / bmain的数据区函数a的数据区函数b的数据区 栈在函数调用中

28、的作用过程一过程二过程三过程四断点三断点一断点二断点一断点二断点三stack调用子程序返回断点程序执行 数据结构-第3章 栈和队列723.2递归、非递归递归的含义递归的含义函数、过程或者数据结构的内部又直接或者间接地由自身定义。适合于应用递归的场合适合于应用递归的场合规模较大的问题可以化解为规模较小的问题，且二者处理(或定义)的方式一致；当问题规模降低到一定程度时是可以直接求解的(终止条件)例1.阶乘n!=1n=0n(n-1)!n0数据结构-第3章 栈和队列73写递归算法应注意的问题写递归算法应注意的问题递归算法本身不可以作为独立的程序运行，需在其它的程序中设置调用初值，进行调用；递归算法应有

29、出口(终止条件)例1.求n！int Factorial(int n) if (n=0) return(1); return n*Factorial(n-1);/Factorial数据结构-第3章 栈和队列74递归算法的实现原理递归算法的实现原理123s123- 利用栈，栈中每个元素称为工作记录，分成三个部分： 返回地址 实际参数表(变参和值参) 局部变量- 发生调用时，保护现场，即当前的工作记录入栈，然后 转入被调用的过程- 一个调用结束时，恢复现场，即若栈不空，则退栈，从 退出的返回地址处继续执行下去75递归时系统工作原理示例递归时系统工作原理示例intFactorial(intn)L1:i

30、f(n=0)L2:return1;L3:elsereturnn*Factorial(n-1);L4:/Factorialvoidmain(void)L0:N=Factorial(3);/main返回地址nFactorialNL0 3 / / L3 3 /L3 2 /L3 1 / 1126数据结构-第3章 栈和队列76递归算法的用途递归算法的用途求解递归定义的数学函数在以递归方式定义的数据结构上的运算/操作可用递归方式描述的解决过程递归算法的特点递归算法的特点递归算法简单明了，直观易懂时间效率低，空间开销大，算法不易优化数据结构-第3章 栈和队列77递归转换为非递归的方法递归转换为非递归的方法1

31、）采用迭代算法）采用迭代算法递归从顶到底迭代从底到顶例：求n！intfact(intn)m=1;for(i=1;idata);linklist_output(p-next)/linklist_output使用跳转语句：void linklist_output1(LNode *p) 1: if ( p ) printf(p-data); p=p-next; goto 1 /linklist_output1使用循环语句：void linklist_output2(LNode *p) while ( p ) printf(p-data); p=p-next; /linklist_output2pan

32、a 2a1数据结构-第3章 栈和队列793)对递归算法改写对递归算法改写通用方法（利用栈模拟递归）通用方法（利用栈模拟递归）如果是递归函数，需改写为递归过程如果是递归函数，需改写为递归过程例：求n!void fact(intn,int&f)0:if(n=0)f=1;else1:fact(n-1,f);2:f=n*f/fact InitStack(S);Push( S, (2, n, f );n=n-1; goto 0; if ( !StackEmpty(S) ) (S.top-1)-f=f; /还原本层变参值 Pop(S, (rd, n, f) ); goto rd ; 80自设栈模拟系统工作

33、栈自设栈模拟系统工作栈 例例：typedefstructintrd;intn;intf;SElemType;改写算法改写算法在程序开头增加栈的初始化语句改写递归调用语句入栈处理；确定调用的参数值；转至调用的开始语句改写所有递归出口退栈还原参数；转至返回地址处Srd n ftopvoid fact(int n; int &f) InitStack(S);0: if (n=0) f=1; else 1: Push( S, (2, n, f ); n=n-1; goto 0; 2: f:=n*f; if ( !StackEmpty(S) ) (S.top-1)-f=f; Pop(S, (rd, n, f) ); goto rd ; /factvoid fact(int n; int &f ) InitStack(S); while (n!=0) Push (S, n); n=n-1; f=1; while ( !StackEmpty(S) ) Pop (S, n); f=n*f; /fact注：此时可确定栈中只 存放n值即可。typedef int SElemType;