數(shù)據(jù)結(jié)構(gòu)ppt-棧和隊列

2023/2/11

第3章棧和隊列本章主題：棧和隊列的應(yīng)用

教學(xué)目的：掌握棧和隊列的應(yīng)用方法,理解棧的重要作用

教學(xué)重點：利用棧實現(xiàn)行編輯,利用棧實現(xiàn)表達式求值

教學(xué)難點：利用棧實現(xiàn)表達式求值

棧，也叫堆棧，是最常用也是最重要的數(shù)據(jù)結(jié)構(gòu)之一。比如編譯器中的語法識別、數(shù)學(xué)表達式的處理、程序運行中的函數(shù)及過程的調(diào)用等，都要用到棧的有關(guān)特性。它們是棧應(yīng)用于實際問題的典型。3.1棧

【課前思考】

1.什么是線性結(jié)構(gòu)？簡單地說，線性結(jié)構(gòu)是一個數(shù)據(jù)元素的序列。

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

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

是"排隊"。在計算機程序中，模擬排隊的數(shù)據(jù)結(jié)構(gòu)是"隊列"。2023/2/122023/2/131．棧的定義

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

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

ana1a2……...棧底棧頂...出棧進棧棧s=(a1,a2,……,an)2023/2/142．棧的基本運算初始化棧InitStack(S)設(shè)置一個空棧S。壓棧Push(S,x)將元素x插入棧S中，使x成為棧S的棧頂元素。出棧Pop(S,x)當(dāng)棧S不空時，由x返回棧頂元素，并從棧中刪除棧頂元素取棧頂元素GetTop(S,x)

若棧S不空，則由x返回棧頂元素。判棧空Empty(S)

若棧S為空棧，結(jié)果為1，否則結(jié)果為0。

2023/2/15例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不可能產(chǎn)生輸出序列CAB2023/2/16例2：一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現(xiàn)嗎？12345的輸出呢？

43512不可能實現(xiàn)，主要是其中的12順序不能實現(xiàn)；

12345的輸出可以實現(xiàn)，只需壓入一個立即彈出一個即可。

435612中到了12順序不能實現(xiàn)；

135426可以實現(xiàn)。例3：如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：2023/2/17例4：計算機系2001年考研題（程序設(shè)計基礎(chǔ)）設(shè)依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。答：2023/2/18

3.1.2棧的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn)

棧有兩種存儲表示方法:順序存儲和鏈?zhǔn)酱鎯?.棧的順序存儲結(jié)構(gòu)

棧的順序存儲結(jié)構(gòu)簡稱為順序棧。通常由一個一維數(shù)組和一個記錄棧頂元素位置的變量組成。2023/2/19ElemType為棧中元素的數(shù)據(jù)類型，可以根據(jù)需要而指定為某種具體的類型。

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

top域:棧頂指針。取值范圍為0～MaxSize-1。top=-1表示?？?，top=MaxSize-1表示棧滿。#defineMaxSize<存儲數(shù)據(jù)元素的最大個數(shù)>typedefstruct{ElemTypedata[MaxSize];inttop;}STACK;順序棧的C++語言描述如下：2023/2/110。

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

2023/2/1112．基本運算在順序存儲結(jié)構(gòu)的實現(xiàn)初始化棧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;}2023/2/112出棧Pop(S,x)intPop(STACK*S,ElemType*x){if(Empty(S)){cout<<“Stackisfree!”;return0;}*x=S->data[S->top];S->top--;return1;}2023/2/113

取棧頂元素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);}順序棧的操作演示2023/2/1143．棧的共享存儲單元

兩個棧共享大小為m的內(nèi)存空間時，分配方法的示意圖如下兩個棧的共享存儲單元可用C++語言描述如下：#defineMaxSize<共享存儲單元的最大長度>typedefstruct{ElemTypedata[MaxSize];inttop[2];}STACK;兩個共享存儲單元順序棧的操作演示2023/2/115（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;}2023/2/116（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;}2023/2/1173.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)1.棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)

棧的鏈?zhǔn)綄崿F(xiàn)是以鏈表作為棧的存儲結(jié)構(gòu)，并在這種存儲結(jié)構(gòu)上實現(xiàn)棧的基本運算。棧的鏈?zhǔn)綄崿F(xiàn)稱為鏈棧鏈棧的C++語言描述如下：typedefstructsnode{//定義鏈棧結(jié)點類型

ElemTypedata;structsnode*next;}LinkSTACK;LinkSTACK*top;鏈棧結(jié)構(gòu)示意圖2023/2/118鏈棧的幾種狀態(tài):2023/2/1192．基本運算在鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)棧初始化

voidInitStack(LinkSTACK**top){*top=(LinkSTACK*)malloc(sizeof(LinkSTACK));(*top)->next=NULL;}2023/2/120壓棧運算

intPush(LinkSTACK**top,ElemTypex){LinkSTACK*s;s=(LinkSTACK*)malloc(sizeof(LinkSTACK));s->data=x;s->next=(*top)->next;(*top)->next=s;return1;}判斷?？?/p>

intEmpty(LinkSTACK**top){return((*top)->next==NULL?1:0);}2023/2/121出棧運算

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;}2023/2/122取棧頂元素

intGetTop(LinkSTACK**top,ElemType*x){if(Empty(top)){cout<<“stackisfree!”;return0;}*x=(*top)->next->data;return1;}2023/2/123遞歸是一種非常重要的數(shù)學(xué)概念和解決問題的方法，在計算機科學(xué)和數(shù)學(xué)等領(lǐng)域有著廣泛的應(yīng)用。在計算機科學(xué)中，許多數(shù)據(jù)結(jié)構(gòu)，如廣義表、樹和二叉樹等，由于其自身固有的遞歸性質(zhì)，都可通過遞歸方式加以定義并實現(xiàn)許多問題的算法設(shè)計。在計算機內(nèi)部，通過棧來實現(xiàn)遞歸算法。所以遞歸是棧的一個實際應(yīng)用。

3.3棧與遞歸2023/2/124采用遞歸算法求解正整數(shù)n的階乘n!數(shù)學(xué)定義求n的階乘的遞歸函數(shù)算法如下:longfact(intn){longf;if(n==0)f=1;elsef=n*fact(n-1);returnf;}2023/2/125進行fact(4)調(diào)用的系統(tǒng)棧的變化情況

2023/2/126函數(shù)fact(4)的遞歸調(diào)用過程的執(zhí)行流程2023/2/127

3.4.1隊列的定義和運算

1．隊列的定義

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

特點：隊列中數(shù)據(jù)元素的入隊和出隊過程是按照“先進先出”的原則進行的。因此，隊列又稱為“先進先出”的線性表，簡稱FIFO表。3.4隊列2023/2/128

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

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

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

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

由x返回隊頭結(jié)點的值。

判隊列空Empty(SQ)隊列SQ是否為空。若為空返回1，否則返回0。2023/2/129

3.4.2隊列的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn)隊列有兩種存儲表示方法:順序存儲和鏈?zhǔn)酱鎯?．隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)簡稱順序隊。順序隊是用一維數(shù)組依次存放隊列中的元素和分別指示隊列的首端和隊列的尾端的兩個變量組成。這兩個變量分別稱為“隊頭指針”和“隊尾指針”。順序隊列的數(shù)據(jù)類型定義如下#defineMaxSize<隊列的最大容量>typedefstruct{ElemTypedata[MaxSize];intfront,rear;}SQUEUE;2023/2/130順序隊列（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。順序隊列的操作演示2023/2/131如圖所示是具有五個存儲單元的循環(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)隊列的操作演示2023/2/1322．基本運算順序隊列的實現(xiàn)隊列初始化

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;}2023/2/133出隊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;}

2023/2/134隊空：Q.front=Q.rear隊滿：Q.rear=maxsize（假溢出）求隊長：Q.rear-Q.front

入隊：新元素按

rear

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

出隊：將front指示的元素取出，再將隊頭指針加一，即front=front+1，非循環(huán)隊列2023/2/135隊空：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)隊列2023/2/1363.4.3隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運算的實現(xiàn)

1.隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)

隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊。它實際上是一個同時帶有首指針和尾指針的單鏈表。頭指針指向表頭結(jié)點，而尾指針則指向隊尾元素。鏈隊結(jié)構(gòu)示意圖2023/2/137鏈隊的數(shù)據(jù)類型定義如下：typedefstructqnode{//鏈隊結(jié)點的類型

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

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

2023/2/138鏈隊運算指針變化情況2023/2/1392．基本運算鏈隊的實現(xiàn)隊列初始化

voidInitQueue(SQUEUE*LQ){QTYPE*p;p=(QTYPE*)malloc(sizeof(QTYPE));p->next=NULL;LQ->front=LQ->rear=p;}2023/2/140入隊列

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);}2023/2/141出隊列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;}2023/2/142取隊頭元素

intGetHead(SQUEUE*LQ,ElemType*x){if(Empty(LQ)){cout<<“Queueisfree”;return0;}*x=LQ->front->next->data;return1;}2023/2/143典型題解1、利用棧的基本操作，寫一個返回棧S中結(jié)點個數(shù)的算法intStackSize(SeqStackS),并說明S為何不作為指針參數(shù)?2023/2/144intStackSize(SeqStackS){ //計算棧中結(jié)點個數(shù)

intn=0; if(!EmptyStack(&S)) { Pop(&S); n++; } returnn;}2023/2/145我們要計算棧中元素個數(shù)就要彈出元素才能"數(shù)"得出來，那如果用指針做參數(shù)的話，就會把原來的棧中元素"彈"光，要恢復(fù)還得用別的辦法給它裝回去，而不用指針做參數(shù)，則可以避免對原來的棧中元素進行任何操作，系統(tǒng)會把原來的棧按值傳遞給形參，函數(shù)只對形參進行操作，最后返回元素個數(shù)就可以了。2023/2/1462、回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)2023/2/147intIsHuiwen(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)) { //每彈出一個字符與相應(yīng)字符比較

t=Pop(&T); if(t!=S[l-i]){return0;}//不等則返回0 i--; } return-1; //比較完畢均相等則返回-1}2023/2/148//以下程序用于驗證上面的算法//以下是棧定義(存為stack.h)//出錯控制函數(shù)#include<stdlib.h>#include<stdio.h>voidError(char*message){ fprintf(stderr,"Error:%s\n",message); exit(1);}//定義棧類型#defineStackSize100typedefcharDatatype;typedefstruct{ Datatypedata[StackSize]; intTop;}SeqStack;2023/2/149voidInitStack(SeqStack*S){ //初始化(置空棧) S->Top=-1;}intEmptyStack(SeqStack*S){ //判棧空

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--];}2023/2/150//以下是主程序#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這個字符串不是回文。");}2023/2/1513、用第二種方法，即少用一上元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試為其設(shè)計置空隊，判隊空，判隊滿、出隊、入隊及取隊頭元素等六個基本操作的算法。2023/2/152intEmptyQueue(CirQueue*Q){ //判隊空

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

return(Q->rear+1)%QueueSize==Q->front;}2023/2/153DatatypeDeQueue(CirQueue*Q){ //出隊

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

Q->front=(Q->front+1)%QueueSize;//循環(huán)意義上的加1 returntemp; //返回元素值}2023/2/154voidEnQueue(CirQueue*Q,Datatypex){ //入隊

if(FullQueue(Q)) Error("隊已滿，不可以入隊"); Q->Data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize;//rear指向下一個空元素位置}2023/2/155DatatypeFrontQueue(CirQueue*Q){ //取隊頭元素

if(EmptyQueue(Q)) Error("隊空，無元素可取"); returnQ->Data[Q->front];}2023/2/156//為了驗證上述算法是否正確，設(shè)計了以下程序//循環(huán)隊列的定義存入StructQ.h文件中#defineQueueSize10//為便與驗證，這里假設(shè)為10個元素的空間typedefcharDatatype;//設(shè)元素的類型為char型typedefstruct{ intfront; intrear; DatatypeData[QueueSize];}CirQueue;2023/2/157//以下是主程序,用來驗證算法#include<stdio.h>#include<string.h>#include"StrctQ.h" //包含隊列結(jié)構(gòu)#include"Queue2.h"http://包含算法頭文件2023/2/158//------------------------主函數(shù)-----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",FrontQueue(&Q