《三章节栈和队列.ppt》由会员分享，可在线阅读，更多相关《三章节栈和队列.ppt（116页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、三章节栈和队列 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望引言v栈和队列是一类特殊的线性表。其特殊性表现在其删除和插入操作受限制。对于栈，用户只能在一个端点进行插入和删除操作。对于队列，允许在一个端点进行插入操作，在另一个端进行删除操作。栈的最重要特性是先进后出，或者后进先出。这在程序设计中非常有用。队列的重要特性是先到先服务。栈和队列广泛应用于程序设计中。特别是栈，在表达式处理、函数调用等方面有广泛的应用。3.1栈v栈的定义v顺序栈v链栈v栈的应用举例3.1
2、.1栈的定义v只允许在某一端进行插入或删除操作的线性表称为栈。允许插入和删除的一端被称为栈顶。另一端为栈底。v大家不妨去思考一下，只允许一端插入和删除操作，会有什么好处，也会带来哪些问题？栈的图示a5a4a3a2a1栈底栈顶栈的性质v(1)通常称插入、删除的这一端为栈顶栈顶（Top），另一端称为栈底栈底（Bottom）。(2)当表中没有元素时称为空栈空栈。(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表表,先进后出先进后出(FILO)栈的示意图v元素是以a1，a2，an的顺序进栈，退栈的次序却是an，an-1，a1。栈的基本运算栈的基本运算（1）InitStack（
3、S）构造一个空栈S。（2）ClearStack（S）（3）IsEmpty（S）判栈空。若S为空栈，则返回TRUE，否则返回FALSE。（4）IsFull（S）判栈满。若S为满栈，则返回TRUE，否则返回FALSE。注意：该运算只适用于栈的顺序存储结构。栈的基本操作（续）（5）Push（S，x）进栈。若栈S不满，则将元素x插入S的栈顶。（6）Pop（S,x）退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。（7）GetTop（S）取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。3.1.2栈的表示和实现v顺序栈v栈链顺序栈v顺序栈的定义v存储类型定义v上溢与下溢v基本操作顺序栈顺序栈
4、v栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。顺序栈的类型定义顺序栈的类型定义v#defineStack_Size100/假定预分配的栈空间最多为100个元素typedefcharDataType;/假定栈元素的数据类型为字符vtypedefstructStackElementTypeelemStack_Size;inttop;SeqStack;进栈的基本操作v进栈时，需要将S-top加1，并把元素保存到栈顶位置。v注意：S-top=StackSize-1表示栈满上溢上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。退栈操作v退栈时，需将S-top减1
5、，并把栈顶元素取出。注意：S-toptop=-1;判栈空vintIsEmpty（SeqStack*S）returnS-top=-1;（3）判栈满vintIsFull（SeqStack*S）returnS-top=StackSize-1;（4）进栈vvoidPush（SeqStack*S，StackElementTypex）if(IsFull(S)Error(Stackoverflow);/上溢，退出运行S-elem+S-top=x;/栈顶指针加1后将x入栈退栈操作intPop(SeqStack*s,StackElementType*x)if(IsEmpty(S)Error(“Stackunde
6、rflow”);/下溢，退出运行*x=S-dataS-top-;returntrue;（6）取栈顶元素intStackTop(SeqStack*S,StackElementType*x）if(IsEmpty(S)Error(Stackisempty);else*x=S-dataS-top;returntrue;4.两个栈共享同一存储空两个栈共享同一存储空v当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。只有当整个向量空间被两个栈占满（即两个栈顶相遇）
7、时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为m/2和m/2的向量空间比较，前者发生上溢的概率比后者要小得多。二个栈共享空间的示意图思考题v如何判断栈空？v如何判断栈满？v存储结构？二个栈共享存储空间的存储结构defineM100typedefstructStackElementTypeStackM;inttop2;DqStack;练习vvoidInitStack(DqStack*s);vintPush(DqStack*s,StackElementTypex,inti);链栈链栈 栈的链式存储结构称为链栈。链栈的存储结构typedefstructnodeSt
8、ackElementTypedatastructnode*nextLinkStackNode;typedefLinkStackNode*LinkStack;进栈操作intPush(LinkStacktop,StackElementtypex)temp=(LinkStackNode*)malloc(sizeof(LinkstackNode);if(temp=NULL)returnFALSE;temp-data=x;temp-next=top-next;top-next=temp;returnTRUE;退栈操作IntPop(LinkStacktop,StackElementType*x)LinkS
9、tackNode*temp;temp=top-next;if(temp=NULL)returnFALSE;top-next=temp-next;*x=temp-data;free(temp);returnTRUE;栈的应用1.括号匹配2.中缀表达式，后缀表达，前缀表达式相互转换。3.老鼠闯迷宫4.栈与函数递归调用括号匹配intBrackMatch(char*str)Stacks;intI;charch;InitStack(&s)for(i=0;stri!=0;i+)switch(stri)case(:case:case:Push(&s,stri);break;case):case:case:i
10、f(IsEmpty(&s)return1;elseGetTop(&S,&ch);if(Match(ch,stri)Pop(&S,&ch);elsereturn2;if(IsEmpty(&S)return0;/正确匹配;elsereturn3;栈的应用数制转换数制转换将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过“除B取余法”来解决【例】将十进制数13转化为二进制数。解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。typedef
11、intDataType;/应将顺序栈的DataType定义改为voidMultiBaseOutput(intN,intB)/假设N是非负的十进制整数，输出等值的B进制数inti;SeqStackS;InitStack(&S);while(N)/从右向左产生B进制的各位数字，并将其进栈push(&S,N%B);/将bi进栈0=i=jN=N/B;while(!StackEmpty(&S)/栈非空时退栈输出i=Pop(&S);printf(%d,i);例：数制的转换v数制转换数制转换将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过“除B取余法”来解决。例v【例】将十进制数
12、13转化为二进制数。解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。分析：由于最先得到的余数是转化结果的最低位，最后得到的余数是转化结果的最高位，因此很容易用栈来解决。转换算法如下vtypedefintDataType;/应将顺序栈的DataType定义改为整型voidMultiBaseOutput(intN,intB)/假设N是非负的十进制整数，输出等值的B进制数inti;SeqStackS;InitStack(&S);while(N)/从右向左产生B进制的各位数字，并将其进栈push(&S,N%B);/将bi进栈0=ifront=Q-rear=0;判
13、队空判队空intIsEmpty(SeqQueue*Q)returnQ-rear=Q-front;判队满判队满intIsFull(SeqQueue*Q)return(Q-rear+1)%MAXSIZE=Q-front;入队入队intEnterQueue(SeqQueue*Q,QueueElementTypex)if(IsFull(Q)returnfalseQ-dataQ-rear=x;/新元素插入队尾Q-rear=(Q-rear+1)%MAXSIZE;/循环意义下将尾指针加returntrue;出队出队intDeleteQueue(SeqQueue*Q,QueueElementType*x)if
14、(IsEmpty(Q)returnfalse;*x=Q-dataQ-front;Q-front=(Q-front+1)%MAXSIZE;returntrue;写一个函数求队列的元素的个数intQueueNumber（CirQueue*Q)return(Q-rear-Q-front+MAXSIZE)%MAXSIZE;/某一年的考试题目3.2.3链队列d1d2d4删除（出队）插入（入队）1、链队列的定义链队列的定义v队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。2、链队列的结构类型说明链队列的结构类型说明注意v增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作注意
15、：和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算定义链队列的存储结构vtypedefcharDataType;vtypedefstructqueuenodevDataTypedata;vstructqueuenode*next;QueueNode;typedefstructQueueNode*front;QueueNode*re
16、ar;LinkQueue;（1）置空队voidInitQueue(LinkQueue*Q)Q-front=Q-rear=NULL;（2）判队空vintQueueEmpty(LinkQueue*Q)returnQ-front=NULL&Q-rear=NULL;/实际上只须判断队头指针是否为空即可（3）入队voidEnQueue(LinkQueue*Q,DataTypex)/将元素x插入链队列尾部QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);/申请新结点p-data=x;p-next=NULL;if(QueueEmpty(Q)Q-front=Q-
17、rear=p;/将x插入空队列else/x插入非空队列的尾Q-rear-next=p;/*p链到原队尾结点后Q-rear=p;/队尾指针指向新的尾（4）出队vDataTypeDeQueue(LinkQueue*Q)DataTypex;QueueNode*p;if(QueueEmpty(Q)Error(“Queueunderflow”);/下溢p=Q-front;/指向对头结点x=p-data;/保存对头结点的数据Q-front=p-next;/将对头结点从链上摘下if(Q-rear=p)/原队中只有一个结点，删去后队列变空，此时队头指针已为空Q-rear=NULL;free(p);/释放被删队
18、头结点returnx;/返回原队头数据（5）取队头元素DataTypeQueueFront(LinkQueue*Q)if(QueueEmpty(Q)Error(Queueifempty.);returnQ-front-data;（1）置空队voidInitQueue(LinkQueue*Q)（2）判队空intQueueEmpty(LinkQueue*Q)（3）入队voidEnQueue(LinkQueue*Q,DataTypex)/将元素x插入链队列尾部（4）出队DataTypeDeQueue(LinkQueue*Q)（5）取队头元素DataTypeQueueFront(LinkQueue*Q
19、)（1）置空队voidInitQueue(LinkQueue*Q)Q-front=Q-rear=NULL;（2）判队空vintQueueEmpty(LinkQueue*Q)returnQ-front=NULL&Q-rear=NULL;/实际上只须判断队头指针是否为空即可（3）入队voidEnQueue(LinkQueue*Q,DataTypex)/将元素x插入链队列尾部QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode);/申请新结点p-data=x;p-next=NULL;if(QueueEmpty(Q)Q-front=Q-rear=p;/将x插入
20、空队列else/x插入非空队列的尾Q-rear-next=p;/*p链到原队尾结点后Q-rear=p;/队尾指针指向新的尾（4）出队vDataTypeDeQueue(LinkQueue*Q)DataTypex;QueueNode*p;if(QueueEmpty(Q)Error(“Queueunderflow”);/下溢p=Q-front;/指向对头结点x=p-data;/保存对头结点的数据Q-front=p-next;/将对头结点从链上摘下if(Q-rear=p)/原队中只有一个结点，删去后队列变空，此时队头指针已为空Q-rear=NULL;free(p);/释放被删队头结点returnx;/返回原队头数据（5）取队头元素DataTypeQueueFront(LinkQueue*Q)if(QueueEmpty(Q)Error(Queueifempty.);returnQ-front-data;