第3章棧和隊列

數(shù)據(jù)結構第3章棧和隊列-2-棧和隊列的邏輯結構棧和隊列的順序存儲及運算實現(xiàn)棧和隊列的鏈式存儲及運算實現(xiàn)棧和隊列的應用掌握棧的邏輯結構、存儲結構及運算的實現(xiàn)方法掌握隊列的邏輯結構、存儲結構及運算的實現(xiàn)方法棧和隊列的運算實現(xiàn)第3章棧和隊列內容要求重點第3章棧和隊列——棧棧的定義棧是一種只能在一端進行插入或刪除操作的線性表。棧頂與棧底：表中允許進行插入、刪除操作的一端稱為棧頂，另一端稱為棧底。進棧：插入操作出棧：刪除操作棧也稱為后進先出表-3-棧頂棧底出棧進棧棧示意圖…第3章棧和隊列——棧棧的定義棧的抽象數(shù)據(jù)類型定義ADTStack {數(shù)據(jù)對象：D={ai|1≤i≤n,n≥0}

數(shù)據(jù)關系：r={<ai,ai+1>|ai,ai+1∈D,1≤i≤n-1}

基本運算：InitStack(&s)：初始化棧。 DestroyStack(&s)：銷毀棧。 StackEmpty(s)：判斷棧是否為空。 Push(&S,e)：進棧。 Pop(&s,&e)：出棧。 GetTop(s,&e)：取棧頂元素。 }-4-第3章棧和隊列——棧例3.1設有4個元素a、b、c、d進棧，給出它們所有可能的出棧次序。解：所有可能的出棧次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba

-5-dcba第3章棧和隊列——棧棧的順序存儲結構順序棧類型SqStack-6-typedefstruct{ElemTypedata[MaxSize]；

inttop； //棧頂指針}SqStack；第3章棧和隊列——棧棧的順序存儲結構順序棧運算-7-順序棧4要素：

?？諚l件：top=-1

棧滿條件：top=MaxSize-1

進棧e操作：top++;將e放在top處退棧操作：從top處取出元素e;top--;第3章棧和隊列——棧棧的順序存儲結構順序棧運算初始化棧initStack(&s)撤銷棧ClearStack(&s)-8-voidInitStack(SqStack*&s){s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;}voidDestroyStack(SqStack*&s){

free(s);}第3章棧和隊列——棧棧的順序存儲結構順序棧運算判斷棧是否為空StackEmpty(s)進棧Push(&s,e)-9-boolStackEmpty(SqStack*s){

return(s->top==-1);}boolPush(SqStack*&s,ElemTypee){

if(s->top==MaxSize-1)//棧滿的情況，即棧上溢出

returnfalse;s->top++; //棧頂指針增1s->data[s->top]=e; //元素e放在棧頂指針處

returntrue;}第3章棧和隊列——棧棧的順序存儲結構順序棧運算出棧Pop(&s,&e)-10-boolPop(SqStack*&s,ElemType&e){if(s->top==-1) //棧為空的情況，即棧下溢出

returnfalse;e=s->data[s->top]; //取棧頂指針元素的元素

s->top--; //棧頂指針減1returntrue;}第3章棧和隊列——棧棧的順序存儲結構順序棧運算取棧頂元素GetTop(s)-11-boolGetTop(SqStack*s,ElemType&e){

if(s->top==-1) //棧為空的情況，即棧下溢出

returnfalse;e=s->data[s->top]; //取棧頂指針元素的元素

returntrue;}第3章棧和隊列——棧例3.4編寫一個算法利用順序棧判斷一個字符串是否是對稱串。-12-boolsymmetry(ElemTypestr[]){inti;ElemTypee;SqStack*st;InitStack(st); //初始化棧

for(i=0;str[i]!='\0';i++) //將串所有元素進棧

Push(st,str[i]); //元素進棧

for(i=0;str[i]!='\0';i++){ Pop(st,e); //退棧元素e if(str[i]!=e) //若e與當前串元素不同則不是對稱串

{DestroyStack(st); //銷毀棧

returnfalse; }}DestroyStack(st); //銷毀棧

returntrue;}第3章棧和隊列——棧棧的鏈式存儲鏈棧類型LiStack：-13-typedefstructlinknode{ElemTypedata; //數(shù)據(jù)域

structlinknode*next; //指針域}LiStack;第3章棧和隊列——棧棧的鏈式存儲鏈棧四要素：鏈棧操作初始化棧initStack(&s)-14-

?？諚l件：s->next=NULL

棧滿條件：不考慮進棧e操作：將包含e的節(jié)點插入到頭節(jié)點之后退棧操作：取出頭節(jié)點之后節(jié)點的元素并刪除之voidInitStack(LiStack*&s){s=(LiStack*)malloc(sizeof(LiStack));s->next=NULL;}第3章棧和隊列——棧棧的鏈式存儲鏈棧操作撤銷棧DestroyStack(&s)-15-voidDestroyStack(LiStack*&s){

LiStack*p=s,*q=s->next;while(q!=NULL){ free(p); p=q; q=p->next;}free(p); //此時p指向尾節(jié)點,釋放其空間}第3章棧和隊列——棧棧的鏈式存儲鏈棧操作判斷棧是否為空StackEmpty(s)進棧Push(&s,e)-16-boolStackEmpty(LiStack*s){return(s->next==NULL);}voidPush(LiStack*&s,ElemTypee){LiStack*p;p=(LiStack*)malloc(sizeof(LiStack));p->data=e; //新建元素e對應的節(jié)點*pp->next=s->next; //插入*p節(jié)點作為開始節(jié)點

s->next=p;}第3章棧和隊列——棧棧的鏈式存儲鏈棧操作出棧Pop(&s,&e)-17-boolPop(LiStack*&s,ElemType&e){LiStack*p;if(s->next==NULL) //?？盏那闆r

returnfalse;p=s->next; //p指向開始節(jié)點

e=p->data;s->next=p->next; //刪除*p節(jié)點

free(p); //釋放*p節(jié)點

returntrue;}第3章棧和隊列——棧棧的鏈式存儲鏈棧操作取棧頂元素GetTop(s,e)-18-boolGetTop(LiStack*s,ElemType&e){if(s->next==NULL) //棧空的情況

returnfalse;e=s->next->data;returntrue;}第3章棧和隊列——棧棧的鏈式存儲例3.5編寫一個算法判斷輸入的表達式中括號是否配對（假設只含有左、右圓括號）。解題思路在表達式括號配對時返回true，否則返回false設置一個順序棧St，掃描表達式exp，遇到左括號時進棧遇到右括號時：若棧頂為左括號，則出棧，否則返回false當表達式掃描完畢，棧為空時返回true；否則返回false-19-第3章棧和隊列——棧boolMatch(charexp[],intn){inti=0;chare;boolmatch=true;SqStack*st;InitStack(st); //初始化棧

while(i<n&&match) //掃描exp中所有字符

{ if(exp[i]=='(') //當前字符為左括號,將其進棧

Push(st,exp[i]); elseif(exp[i]==')') //當前字符為右括號

{if(GetTop(st,e)==true) { if(e!='(') //棧頂元素不為'('時表示不匹配

match=false; else Pop(st,e);//將棧頂元素出棧

} elsematch=false;//無法取棧頂元素時表示不匹配

} i++; //繼續(xù)處理其他字符

}if(!StackEmpty(st)) //棧不空時表示不匹配

match=false;DestroyStack(st); //銷毀棧

returnmatch;}-20-第3章棧和隊列——隊列隊列的定義隊列是一種僅允許在表的一端進行插入，而在另一端進行刪除的線性表隊尾（rear）：允許插入的一端隊頭（front）：允許刪除的一端入隊：向隊列中插入新元素，新元素進隊后就成為新的隊尾元素出隊：從隊列中刪除元素元素，其后繼元素就成為隊首元素隊列又稱為先進先出表-21-第3章棧和隊列——隊列隊列的定義隊列的抽象數(shù)據(jù)類型定義ADTStack {數(shù)據(jù)對象：D={ai|1≤i≤n,n≥0}

數(shù)據(jù)關系：r={<ai,ai+1>|ai,ai+1∈D,1≤i≤n-1}

基本運算：InitQueue(&q):初始化隊列。 DestroyQueue(&q):撤銷隊列。 QueueEmpty(q):判斷隊列是否為空。 enQueue(&q,e):進隊列。 deQueue(&q,&e):出隊列。 }-22-第3章棧和隊列——隊列隊列的順序存儲順序隊列類型SqQueue定義-23-typedefstruct{ ElemTypedata[MaxSize]；

intfront,rear；//隊首和隊尾指針

}SqQueue;第3章棧和隊列——隊列隊列的順序存儲順序隊列運算順序隊的四要素（初始時front=rear=-1）隊空條件：front=rear隊滿條件：rear＝MaxSize－1元素e進隊：rear++;data[rear]=e;元素e出隊：front++;e=data[front];-24-第3章棧和隊列——隊列隊列的順序存儲順序隊列運算初始化隊列InitQueue(q)銷毀隊列DestroyQueue(q)-25-voidInitQueue(SqQueue*&q){

q=(SqQueue*)malloc(sizeof(SqQueue));

q->front=q->rear=-1;}voidDestroyQueue(SqQueue*&q){free(q);}第3章棧和隊列——隊列隊列的順序存儲順序隊列運算判斷隊列是否為空QueueEmpty(q)進隊列enQueue(q,e)-26-boolQueueEmpty(SqQueue*q){return(q->front==q->rear);}boolenQueue(SqQueue*&q,ElemTypee){if(q->rear==MaxSize-1) //隊滿上溢出

returnfalse; q->rear++; q->data[q->rear]=e; returntrue;}第3章棧和隊列——隊列隊列的順序存儲順序隊列運算出隊列deQueue(q,e)-27-booldeQueue(SqQueue*&q,ElemType&e){if(q->front==q->rear) //隊空下溢出

returnfalse;q->front++;e=q->data[q->front];returntrue;}第3章棧和隊列——隊列隊列的順序存儲循環(huán)隊列運算把存儲隊列元素的表從邏輯上看成一個環(huán)，稱為循環(huán)隊列-28-循環(huán)隊列的四要素：隊空條件：front=rear隊滿條件：(rear+1)%MaxSize=front進隊操作：rear=(rear+1)%MaxSize;出隊操作：ront=(front+1)%MaxSize;第3章棧和隊列——隊列隊列的順序存儲循環(huán)隊列運算初始化隊列InitQueue(q)銷毀隊列ClearQueue(&q)-29-voidInitQueue(SqQueue*&q){q=(SqQueue*)malloc(sizeof(SqQueue));q->front=q->rear=0;}voidDestroyQueue(SqQueue*&q){

free(q);}第3章棧和隊列——隊列隊列的順序存儲循環(huán)隊列運算判斷隊列是否為空QueueEmpty(q)進隊列enQueue(q,e)-30-boolQueueEmpty(SqQueue*q){return(q->front==q->rear);}boolenQueue(SqQueue*&q,ElemTypee){if((q->rear+1)%MaxSize==q->front)//隊滿上溢出

returnfalse;q->rear=(q->rear+1)%MaxSize;q->data[q->rear]=e;returntrue;}第3章棧和隊列——隊列隊列的順序存儲循環(huán)隊列運算出隊列deQueue(q,e)-31-booldeQueue(SqQueue*&q,ElemType&e){if(q->front==q->rear) //隊空下溢出

returnfalse;q->front=(q->front+1)%MaxSize;e=q->data[q->front];returntrue;}第3章棧和隊列——隊列隊列的鏈式存儲鏈隊列類型-32-單鏈表中數(shù)據(jù)節(jié)點類型QNode:typedefstructqnode{ElemTypedata;

structqnode*next;}QNode;鏈隊中頭節(jié)點類型LiQueue:typedefstruct{QNode*front;//指向鏈隊頭節(jié)點

QNode*rear;//指向鏈隊尾節(jié)點}LiQueue;第3章棧和隊列——隊列隊列的鏈式存儲鏈隊列運算-33-鏈隊的4要素：隊空條件：front=rear=NULL隊滿條件：不考慮進隊操作：將包含e的節(jié)點插入到單鏈表表尾出隊操作：刪除單鏈表首數(shù)據(jù)節(jié)點第3章棧和隊列——隊列隊列的鏈式存儲鏈隊列運算初始化隊列InitQueue(q)判斷隊列是否為空QueueEmpty(q)-34-voidInitQueue(LiQueue*&q){q=(LiQueue*)malloc(sizeof(LiQueue));q->front=q->rear=NULL;}boolQueueEmpty(LiQueue*q){

return(q->rear==NULL);}第3章棧和隊列——隊列隊列的鏈式存儲鏈隊列運算撤銷隊列DestroyQueue(q)-35-voidDestroyQueue(LiQueue*&q){QNode*p=q->front,*r;//p指向隊頭數(shù)據(jù)節(jié)點

if(p!=NULL) //釋放數(shù)據(jù)節(jié)點占用空間

{r=p->next; while(r!=NULL) {free(p); p=r;r=p->next; }}free(p);free(q); //釋放鏈隊節(jié)點占用空間}第3章棧和隊列——隊列隊列的鏈式存儲鏈隊列運算入隊enQueue(q,e)-36-voidenQueue(LiQueue*&q,ElemTypee){QNode*p;p=(QNode*)malloc(sizeof(QNode));p->data=e;p->next=NULL;if(q->rear==NULL)//若鏈隊為空,新節(jié)點是隊首節(jié)點又是隊尾節(jié)點

q->front=q->rear=p;else{q->rear->next=p;//將*p節(jié)點鏈到隊尾,并將rear指向它

q->rear=p;}}第3章棧和隊列——隊列隊列的鏈式存儲鏈隊列運算出隊deQueue(q,e)-37-booldeQueue(LiQueue*&q,ElemType&e){QNode*t;if(q->rear==NULL)returnfalse; //隊列為空

t=q->front; //t指向第一個數(shù)據(jù)節(jié)點

if(q->front==q->rear)//隊列中只有一個節(jié)點時

q->front=q->rear=NULL;else //隊列中有多個節(jié)點時

q->front=q->front->next;e=t->data;free(t);returntrue;}第3章棧和隊列——應用求解迷宮問題求出從入口到出口的路徑-38-01234567890123456789(i-1,j)方位0(i+1,j)方位2(i,j+1)方位1(i,j-1)方位3(i，j)入口出口采用“窮舉求解”的方法為了保證在任何位置上都能沿原路退回（稱為回溯），需要用一個后進先出的棧來保存從入口到當前位置的路徑。

第3章棧和隊列——應用求解迷宮問題為了表示迷宮,設置一個數(shù)組mg,其中每個元素表示一個方塊的狀態(tài),為0時表示對應方塊是通道,為1時表示對應方塊為墻,如圖3.6所示的迷宮,對應的迷宮數(shù)組mg如下:-39-intmg[M+2][N+2]={ //M=8,N=8 {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}};-40-111122222321331340240

141151162263253012345678901234567892-125-1第3章棧和隊列——應用第3章棧和隊列——應用為了便于回溯，對于可走的方塊都要進棧，并試探它的下一可走的方位，將這個可走的方位保存到棧中，為此將棧定義為:-41-typedefstruct{inti; //當前方塊的行號

intj; //當前方塊的列號

intdi; //di是下一可走相鄰方位的方位號}Box; //定義方塊類型typedefstruct{Boxdata[MaxSize];inttop; //棧頂指針}StType; //順序棧類型第3章棧和隊列——應用-42-01234567890123456789

迷宮路徑如下: (1,1)(1,2)(2,2)(3,2)(3,1) (4,1)(5,1)(5,2)(5,3