數據結構-棧和隊列

大家好數據結構-棧和隊列全文共64頁，當前為第1頁。2023/6/152

第3章棧和隊列本章主題：棧和隊列的應用

教學目的：掌握棧和隊列的應用方法,理解棧的重要作用

教學重點：利用棧實現行編輯,利用棧實現表達式求值

教學難點：利用棧實現表達式求值

棧，也叫堆棧，是最常用也是最重要的數據結構之一。比如編譯器中的語法識別、數學表達式的處理、程序運行中的函數及過程的調用等，都要用到棧的有關特性。它們是棧應用于實際問題的典型。3.1棧

數據結構-棧和隊列全文共64頁，當前為第2頁。2023/6/153【課前思考】

1.什么是線性結構？簡單地說，線性結構是一個數據元素的序列。

2.你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,…,n的次序往上疊的,那么使用時候的次序應是什么樣的？必然是依從上往下的次序，即n,…,2,1。它們遵循的是"后進先出"的規(guī)律，這正是本章要討論的"棧"的結構特點。

3.在日常生活中，為了維持正常的社會秩序而出現的常見現象是什么？

是"排隊"。在計算機程序中，模擬排隊的數據結構是"隊列"。數據結構-棧和隊列全文共64頁，當前為第3頁。2023/6/1541．棧的定義

棧是一種特殊的線性表，插入或刪除棧元素的運算只能在表的一端進行，稱運算的一端為棧頂，另一端稱為棧底。

特點：后進先出棧又稱為“后進先出”的線性表，簡稱LIFO表。3.1.1棧的定義和運算

ana1a2……...棧底棧頂...出棧進棧棧s=(a1,a2,……,an)數據結構-棧和隊列全文共64頁，當前為第4頁。2023/6/1552．棧的基本運算初始化棧InitStack(S)設置一個空棧S。壓棧Push(S,x)將元素x插入棧S中，使x成為棧S的棧頂元素。出棧Pop(S,x)當棧S不空時，由x返回棧頂元素，并從棧中刪除棧頂元素取棧頂元素GetTop(S,x)

若棧S不空，則由x返回棧頂元素。判?？誆mpty(S)

若棧S為空棧，結果為1，否則結果為0。

數據結構-棧和隊列全文共64頁，當前為第5頁。2023/6/156例1：對于一個棧，給出輸入項A、B、C，如果輸入項序列由ABC組成，試給出所有可能的輸出序列。A進A出B進B出C進C出ABCA進A出B進C進C出B出ACBA進B進B出A出C進C出BACA進B進B出C進C出A出BCAA進B進C進C出B出A出CBA不可能產生輸出序列CAB數據結構-棧和隊列全文共64頁，當前為第6頁。2023/6/157例2：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現嗎？12345的輸出呢？

43512不可能實現，主要是其中的12順序不能實現；

12345的輸出可以實現，只需壓入一個立即彈出一個即可。

435612中到了12順序不能實現；

135426可以實現。例3：如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：數據結構-棧和隊列全文共64頁，當前為第7頁。2023/6/158例4：計算機系2001年考研題（程序設計基礎）設依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。答：數據結構-棧和隊列全文共64頁，當前為第8頁。2023/6/159

3.1.2棧的順序存儲結構及其基本運算的實現

棧有兩種存儲表示方法:順序存儲和鏈式存儲1.棧的順序存儲結構

棧的順序存儲結構簡稱為順序棧。通常由一個一維數組和一個記錄棧頂元素位置的變量組成。數據結構-棧和隊列全文共64頁，當前為第9頁。2023/6/1510ElemType為棧中元素的數據類型，可以根據需要而指定為某種具體的類型。

data域:為一個一維數組，用于存儲棧中元素。

top域:棧頂指針。取值范圍為0～MaxSize-1。top=-1表示?？?，top=MaxSize-1表示棧滿。#defineMaxSize<存儲數據元素的最大個數>typedefstruct{ElemTypedata[MaxSize];inttop;}STACK;順序棧的C++語言描述如下：數據結構-棧和隊列全文共64頁，當前為第10頁。2023/6/1511。

順序棧的幾種狀態(tài)（最大長度MaxSize為4）（a）當棧中沒有數據元素時，表示為?？?。棧頂元素所對應的下標值top=-1。（b）表示在（a）基礎上執(zhí)行Push(S,‘A’)后得到這種狀態(tài)。（c）又有三個元素B、C、D先后入棧，此時棧頂元素的下標值top=3。棧已滿。（d）表示在（c）狀態(tài)下，執(zhí)行一次Pop(S，x)運算得到。（e）表示在（d）狀態(tài)下，執(zhí)行三次Pop(S，x)運算得到。此時棧頂下標值top=-l，又變成?？諣顟B(tài)

數據結構-棧和隊列全文共64頁，當前為第11頁。2023/6/15122．基本運算在順序存儲結構的實現初始化棧InitStack(S)

voidInitStack(STACK*S){S->top=-1;}

壓棧Push(S,x)

intPush(STACK*S,ElemTypex){if(S->top==MaxSize-1){Cout<<“Stackisfull!”;return0;}S->top++;S->data[S->top]=x;return1;}數據結構-棧和隊列全文共64頁，當前為第12頁。2023/6/1513出棧Pop(S,x)intPop(STACK*S,ElemType*x){if(Empty(S)){cout<<“Stackisfree!”;return0;}*x=S->data[S->top];S->top--;return1;}數據結構-棧和隊列全文共64頁，當前為第13頁。2023/6/1514

取棧頂元素GetTop(S,x)

intGetTop(STACK*S,ElemType*x){

if(Empty(S)){cout<<“Stackisfree!”;retrn0;}*x=S->data[S->top];return}

判?？誆mpty(S)

intEmpty(STACK*S){return(S->top==-1?1:0);}順序棧的操作演示數據結構-棧和隊列全文共64頁，當前為第14頁。2023/6/15153．棧的共享存儲單元

兩個棧共享大小為m的內存空間時，分配方法的示意圖如下兩個棧的共享存儲單元可用C++語言描述如下：#defineMaxSize<共享存儲單元的最大長度>typedefstruct{ElemTypedata[MaxSize];inttop[2];}STACK;兩個共享存儲單元順序棧的操作演示數據結構-棧和隊列全文共64頁，當前為第15頁。2023/6/1516（1）兩個棧共享存儲單元的壓棧算法intPush(STACK*S,ElemTypex,intk){if(S->top[0]+1==S->top[1]){cout<<“stackisfull!”;return0;}if(k==0){S->top[0]++;S->data[S->top[0]]=x;}else{S->top[1]--;S->data[S->top[1]]=x;}return1;}數據結構-棧和隊列全文共64頁，當前為第16頁。2023/6/1517（2）兩個棧共享存儲單元的出棧算法intPop(STACK*S,intk,ElemType*x){if((k==0)&&(S->top[0]==-1)){cout<<“stackisfree!”;return0;}if((k==1)&&(S->top[1]==MaxSize)){cout<<“nstackisfree!”;return0;}if(k==0){*x=S->data[S->top[0]];S->top[0]--;}else{*x=S->data[S->top[1]];S->top[1]++;}return1;}數據結構-棧和隊列全文共64頁，當前為第17頁。2023/6/15183.1.3棧的鏈式存儲結構及其基本運算的實現1.棧的鏈式存儲結構

棧的鏈式實現是以鏈表作為棧的存儲結構，并在這種存儲結構上實現棧的基本運算。棧的鏈式實現稱為鏈棧鏈棧的C++語言描述如下：typedefstructsnode{//定義鏈棧結點類型

ElemTypedata;structsnode*next;}LinkSTACK;LinkSTACK*top;鏈棧結構示意圖數據結構-棧和隊列全文共64頁，當前為第18頁。2023/6/1519鏈棧的幾種狀態(tài):數據結構-棧和隊列全文共64頁，當前為第19頁。2023/6/15202．基本運算在鏈式存儲結構的實現棧初始化

voidInitStack(LinkSTACK**top){*top=(LinkSTACK*)malloc(sizeof(LinkSTACK));(*top)->next=NULL;}數據結構-棧和隊列全文共64頁，當前為第20頁。2023/6/1521壓棧運算

intPush(LinkSTACK**top,ElemTypex){LinkSTACK*s;s=(LinkSTACK*)malloc(sizeof(LinkSTACK));s->data=x;s->next=(*top)->next;(*top)->next=s;return1;}判斷棧空

intEmpty(LinkSTACK**top){return((*top)->next==NULL?1:0);}數據結構-棧和隊列全文共64頁，當前為第21頁。2023/6/1522出棧運算

intPop(LinkSTACK**top,ElemType*x)

{LinkSTACK*s;if(Empty(top)){cout<<“stackisfree!”;return0;}s=(*top)->next;*x=s->data;(*top)->next=s->next;free(s);return1;}數據結構-棧和隊列全文共64頁，當前為第22頁。2023/6/1523取棧頂元素

intGetTop(LinkSTACK**top,ElemType*x){if(Empty(top)){cout<<“stackisfree!”;return0;}*x=(*top)->next->data;return1;}數據結構-棧和隊列全文共64頁，當前為第23頁。2023/6/1524遞歸是一種非常重要的數學概念和解決問題的方法，在計算機科學和數學等領域有著廣泛的應用。在計算機科學中，許多數據結構，如廣義表、樹和二叉樹等，由于其自身固有的遞歸性質，都可通過遞歸方式加以定義并實現許多問題的算法設計。在計算機內部，通過棧來實現遞歸算法。所以遞歸是棧的一個實際應用。

3.3棧與遞歸數據結構-棧和隊列全文共64頁，當前為第24頁。2023/6/1525采用遞歸算法求解正整數n的階乘n!數學定義求n的階乘的遞歸函數算法如下:longfact(intn){longf;if(n==0)f=1;elsef=n*fact(n-1);returnf;}數據結構-棧和隊列全文共64頁，當前為第25頁。2023/6/1526進行fact(4)調用的系統(tǒng)棧的變化情況

數據結構-棧和隊列全文共64頁，當前為第26頁。2023/6/1527函數fact(4)的遞歸調用過程的執(zhí)行流程數據結構-棧和隊列全文共64頁，當前為第27頁。2023/6/1528

3.4.1隊列的定義和運算

1．隊列的定義

隊列也是一種運算受限的線性表。在這種線性表上，插入限定在表的某一端進行，刪除限定在表的另一端進行。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。

特點：隊列中數據元素的入隊和出隊過程是按照“先進先出”的原則進行的。因此，隊列又稱為“先進先出”的線性表，簡稱FIFO表。3.4隊列數據結構-棧和隊列全文共64頁，當前為第28頁。2023/6/1529

2．隊列的基本運算隊列初始化InitQueue(SQ)

設置一個空隊列SQ。入隊列EnQueue(SQ，x)

將x插入到隊列SQ的隊尾。出隊OutQueue(SQ，x)

將隊頭元素賦給x，并刪除隊頭元素。取隊頭元素GetHead(SQ，x)

由x返回隊頭結點的值。

判隊列空Empty(SQ)隊列SQ是否為空。若為空返回1，否則返回0。數據結構-棧和隊列全文共64頁，當前為第29頁。2023/6/1530

3.4.2隊列的順序存儲結構及其基本運算的實現隊列有兩種存儲表示方法:順序存儲和鏈式存儲1．隊列的順序存儲結構隊列的順序存儲結構簡稱順序隊。順序隊是用一維數組依次存放隊列中的元素和分別指示隊列的首端和隊列的尾端的兩個變量組成。這兩個變量分別稱為“隊頭指針”和“隊尾指針”。順序隊列的數據類型定義如下#defineMaxSize<隊列的最大容量>typedefstruct{ElemTypedata[MaxSize];intfront,rear;}SQUEUE;數據結構-棧和隊列全文共64頁，當前為第30頁。2023/6/1531順序隊列（MaxSize=5）的幾種狀態(tài)

（a）表示空隊列，

rear=front=0。（b）元素A入隊后，

rear=1，front=0。（c）B，C依次入隊后，

rear=3，front=0。（d）A，B，C依此出隊后,rear=front=3。（e）D入隊后,rear=4,front=3。（f）D出隊后，rear=front=4。順序隊列的操作演示數據結構-棧和隊列全文共64頁，當前為第31頁。2023/6/1532如圖所示是具有五個存儲單元的循環(huán)隊列（a）表示空隊列，

rear=front=0。（b）元素A入隊后，

rear=1，front=0。（c）B，C，D依次入隊后，

rear=4，front=0。（d）A出隊后,front=1,rear=4。（e）B，C，D出隊后,rear=front=4。

循環(huán)隊列的操作演示數據結構-棧和隊列全文共64頁，當前為第32頁。2023/6/15332．基本運算順序隊列的實現隊列初始化

voidInitQueue(SQUEUE*SQ){SQ->rear=SQ->front=0;}

入隊列intEnQueue(SQUEUE*SQ,ElemTypex){if((SQ->rear+1)%MaxSize==SQ->front){cout<<“Queueisfull!”;return0;}SQ->rear=(SQ->rear+1)%MaxSize;SQ->data[SQ->rear]=x;return1;}數據結構-棧和隊列全文共64頁，當前為第33頁。2023/6/1534出隊intOutQueue(SQUEUE*SQ,ElemType*x){if(Empty(SQ)){cout<<“Queueisfree”;return0;}SQ->front=(SQ->front+1)%MaxSize;*x=SQ->data[SQ->front];return1;}判隊列空intEmpty(SQUEUE*SQ){return(SQ->rear==SQ->front)?1:0;}

數據結構-棧和隊列全文共64頁，當前為第34頁。2023/6/1535隊空：Q.front=Q.rear隊滿：Q.rear=maxsize（假溢出）求隊長：Q.rear-Q.front

入隊：新元素按

rear

指示位置加入，再將隊尾指針加一，即rear=rear+1

出隊：將front指示的元素取出，再將隊頭指針加一，即front=front+1，非循環(huán)隊列數據結構-棧和隊列全文共64頁，當前為第35頁。2023/6/1536隊空：Q.front=Q.rear隊滿：Q.front=(Q.rear+1)%maxSize入隊:Q.rear=(Q.rear+1)%maxSize出隊:Q.front=(front+1)%maxSize;求隊長:(Q.rear-Q.front+maxSize)%maxSize循環(huán)隊列數據結構-棧和隊列全文共64頁，當前為第36頁。2023/6/15373.4.3隊列的鏈式存儲結構及其基本運算的實現

1.隊列的鏈式存儲結構

隊列的鏈式存儲結構簡稱為鏈隊。它實際上是一個同時帶有首指針和尾指針的單鏈表。頭指針指向表頭結點，而尾指針則指向隊尾元素。鏈隊結構示意圖數據結構-棧和隊列全文共64頁，當前為第37頁。2023/6/1538鏈隊的數據類型定義如下：typedefstructqnode{//鏈隊結點的類型

ElemTypedata;structqnode*next;}QTYPE;typedefstructqptr{//鏈隊指針類型

QTYPE*front,*rear;}SQUEUE;SQUEUELQ;

數據結構-棧和隊列全文共64頁，當前為第38頁。2023/6/1539鏈隊運算指針變化情況數據結構-棧和隊列全文共64頁，當前為第39頁。2023/6/15402．基本運算鏈隊的實現隊列初始化

voidInitQueue(SQUEUE*LQ){QTYPE*p;p=(QTYPE*)malloc(sizeof(QTYPE));p->next=NULL;LQ->front=LQ->rear=p;}數據結構-棧和隊列全文共64頁，當前為第40頁。2023/6/1541入隊列

intEnQueue(SQUEUE*LQ,ElemTypex){QTYPE*s;s=(QTYPE*)malloc(sizeof(QTYPE));s->data=x;s->next=LQ->rear->next;LQ->rear->next=s;LQ->rear=s;return1;}判隊空intEmpty(SQUEUE*LQ){return(LQ->front==LQ->rear?1:0);}數據結構-棧和隊列全文共64頁，當前為第41頁。2023/6/1542出隊列intOutQueue(SQUEUE*LQ,ElemType*x){QTYPE*p;if(Empty(LQ)){cout<<“Queueisfree”;return0;}p=LQ->front->next;*x=p->data;LQ->front->next=p->next;if(LQ->front->next==NULL)LQ->rear=LQ->front;free(p);return1;}數據結構-棧和隊列全文共64頁，當前為第42頁。2023/6/1543取隊頭元素

intGetHead(SQUEUE*LQ,ElemType*x){if(Empty(LQ)){cout<<“Queueisfree”;return0;}*x=LQ->front->next->data;return1;}數據結構-棧和隊列全文共64頁，當前為第43頁。2023/6/1544典型題解1、利用棧的基本操作，寫一個返回棧S中結點個數的算法intStackSize(SeqStackS),并說明S為何不作為指針參數?數據結構-棧和隊列全文共64頁，當前為第44頁。2023/6/1545intStackSize(SeqStackS){ //計算棧中結點個數

intn=0; if(!EmptyStack(&S)) { Pop(&S); n++; } returnn;}數據結構-棧和隊列全文共64頁，當前為第45頁。2023/6/1546我們要計算棧中元素個數就要彈出元素才能"數"得出來，那如果用指針做參數的話，就會把原來的棧中元素"彈"光，要恢復還得用別的辦法給它裝回去，而不用指針做參數，則可以避免對原來的棧中元素進行任何操作，系統(tǒng)會把原來的棧按值傳遞給形參，函數只對形參進行操作，最后返回元素個數就可以了。數據結構-棧和隊列全文共64頁，當前為第46頁。2023/6/15472、回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)數據結構-棧和隊列全文共64頁，當前為第47頁。2023/6/1548intIsHuiwen(char*S){ SeqStackT; inti,l; chart; InitStack(&T); l=strlen(S); //求向量長度

for(i=0;i<l/2;i++) //將一半字符入棧

Push(&T,S[i]); while(!EmptyStack(&T)) { //每彈出一個字符與相應字符比較

t=Pop(&T); if(t!=S[l-i]){return0;}//不等則返回0 i--; } return-1; //比較完畢均相等則返回-1}數據結構-棧和隊列全文共64頁，當前為第48頁。2023/6/1549//以下程序用于驗證上面的算法//以下是棧定義(存為stack.h)//出錯控制函數#include<stdlib.h>#include<stdio.h>voidError(char*message){ fprintf(stderr,"Error:%s\n",message); exit(1);}//定義棧類型#defineStackSize100typedefcharDatatype;typedefstruct{ Datatypedata[StackSize]; intTop;}SeqStack;數據結構-棧和隊列全文共64頁，當前為第49頁。2023/6/1550voidInitStack(SeqStack*S){ //初始化(置空棧) S->Top=-1;}intEmptyStack(SeqStack*S){ //判?？?/p>

returnS->Top==-1; }intFullStack(SeqStack*S){ //判棧滿returnS->Top==StackSize-1;}voidPush(SeqStack*S,Datatypex){ //進棧

if(FullStack(S)) Error("Stackoverflow"); S->data[++S->Top]=x;}DatatypePop(SeqStack*S){ //出棧(退棧) if(EmptyStack(S)) Error("Stackunderflow"); returnS->data[S->Top--];}數據結構-棧和隊列全文共64頁，當前為第50頁。2023/6/1551//以下是主程序#include<string.h>#include<malloc.h>#include"stack.h>#include"ishuiwen.h"voidmain(){ charStr[100]=""; printf("輸入一個字符串:\n"); scanf("%s",Str); if(IsHuiwen(Str)) printf("\n這個字符串是回文。"); elseprintf("\n這個字符串不是回文。");}數據結構-棧和隊列全文共64頁，當前為第51頁。2023/6/15523、用第二種方法，即少用一上元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試為其設計置空隊，判隊空，判隊滿、出隊、入隊及取隊頭元素等六個基本操作的算法。數據結構-棧和隊列全文共64頁，當前為第52頁。2023/6/1553intEmptyQueue(CirQueue*Q){ //判隊空

returnQ->front==Q->rear;}intFullQueue(CirQueue*Q){ //判隊滿//如果尾指針加1后等于頭指針，則認為滿

return(Q->rear+1)%QueueSize==Q->front;}數據結構-棧和隊列全文共64頁，當前為第53頁。2023/6/1554DatatypeDeQueue(CirQueue*Q){ //出隊

if(EmptyQueue(Q)) Error("隊已空，無元素可以出隊"); Datatypetemp; temp=Q->Data[Q->front];//保存元素值

Q->front=(Q->front+1)%QueueSize;//循環(huán)意義上的加1 returntemp; //返回元素值}數據結構-棧和隊列全文共64頁，當前為第54頁。2023/6/1555voidEnQueue(CirQueue*Q,Datatypex){ //入隊

if(FullQueue(Q)) Error("隊已滿，不可以入隊"); Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize;//rear指向下一個空元素位置}數據結構-棧和隊列全文共64頁，當前為第55頁。2023/6/1556DatatypeFrontQueue(CirQueue*Q){ //取隊頭元素

if(EmptyQueue(Q)) Error("隊空，無元素可取"); returnQ->Data[Q->front];}數據結構-棧和隊列全文共64頁，當前為第56頁。2023/6/1557//為了驗證上述算法是否正確，設計了以下程序//循環(huán)隊列的定義存入StructQ.h文件中#defineQueueSize10//為便與驗證，這里假設為10個元素的空間typedefcharDatatype;//設元素的類型為char型typedefstruct{ intfront; intrear; DatatypeData[QueueSize];}CirQueue;數據結構-棧和隊列全文共64頁，當前為第57頁。2023/6/1558//以下是主程序,用來驗證算法#include<stdio.h>#include<string.h>#include"StrctQ.h" //包含隊列結構#include"Queue2.h"http://包含算法頭文件數據結構-棧和隊列全文共64頁，當前為第58頁。2023/6/1559//------------------------主函數-----voidmain() { inti; CirQueueQ;//定義一個循環(huán)隊列

InitQueue(&Q);//初始化隊列

printf("pleaseentercharacters:\n"); for(i=0;i<QueueSize-1;i++) EnQueue(&Q,getchar()); printf("\n"); if(!EmptyQueue(&Q)) //先輸出一個頭元素

printf("frontDatais%c",