第3章棧和隊列主要知識點棧棧應用隊列隊列應用優(yōu)先級隊列3.1

堆棧1、棧的基本概念(1)定義:限定只能在固定一端進行插入和刪除操作的線性表。特點：后進先出。(2)允許進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。作用：可以完成從輸入數(shù)據(jù)序列到某些輸出數(shù)據(jù)序列的轉換2、棧抽象數(shù)據(jù)類型數(shù)據(jù)集合:{a0,a1,…,an-1}ai的數(shù)據(jù)類型為DataType。操作集合：

(1)StackInitiate(S)：初始化棧S(2)StackNotEmpty(S)：棧S非空否

(3)

StackPush(S,x)：入棧

(4)

StackPop(S,d)：出棧

(5)

StackTop(S,d)：取棧頂數(shù)據(jù)元素3、順序棧

順序棧：順序存儲結構的棧。

順序棧的存儲結構：利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素.a0a1a2a3a4stack棧底棧頂MaxStackSize-1012345=toptypedefstruct{DataTypestack[MaxStackSize]; inttop;}SeqStack;順序棧的操作實現(xiàn)：

（1）初始化StackInitiate(S)voidStackInitiate(SeqStack*S) {S->top=0; }（2）非空否StackNotEmpty(S)intStackNotEmpty(SeqStackS){if(S.top<=0)return0;elsereturn1;}（3）入棧StackPush(S,x)intStackPush(SeqStack*S,DataTypex){if(S->top>=MaxStackSize){printf("棧已滿無法插入!\n"); return0;}else{S->stack[S->top]=x; S->top++;return1;}}（4）出棧StackPop(S,d)intStackPop(SeqStack*S,DataType*d){if(S->top<=0){printf("棧已空無數(shù)據(jù)元素出棧!\n"); return0;}else{S->top--;*d=S->stack[S->top];

return1;}}（5）取棧頂數(shù)據(jù)元素StackTop(SeqStackS,DataType*d)intStackTop(SeqStackS,DataType*d){if(S.top<=0){printf("棧已空!\n"); return0;}else{*d=S.stack[S.top-1]; return1;}}

測試主程序：任務：建立一個順序棧，首先依次輸入數(shù)據(jù)元素1,2,3,......,10，然后依次出棧數(shù)據(jù)元素并顯示。假設該順序棧的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個。

#include<stdio.h>#include<stdlib.h> #defineMaxStackSize100 typedefintDataType; #include"SeqStack.h"

voidmain(void){SeqStackmyStack;inti,x;StackInitiate(&myStack);for(i=0;i<10;i++)StackPush(&myStack,i+1)StackTop(myStack,&x)printf("當前棧頂數(shù)據(jù)元素為：%d\n",x);printf("依次出棧的數(shù)據(jù)元素序列如下：\n");while(StackNotEmpty(myStack)){StackPop(&myStack,&x); printf("%d",x);} }程序運行輸出結果如下：當前棧頂數(shù)據(jù)元素為：10依次出棧的數(shù)據(jù)元素序列如下：109876543214、鏈式棧1)鏈式棧

鏈式存儲結構的棧。2)鏈式棧的存儲結構它是以頭指針為棧頂，在頭指針處插入或刪除，帶頭結點的鏈式棧結構：頭結點an-1an-2a0∧…h(huán)棧底棧頂鏈棧中每個結點由兩個域構成：data域和next域結點結構體定義如下：typedefstructsnode{DataTypedata;structsnode*next;}LSNode;3)鏈式棧的操作實現(xiàn)

（1）初始化StackInitiate(head)voidStackInitiate(LSNode**head){*head=(LSNode*)malloc(sizeof(LSNode)); (*head)->next=NULL;}（2）非空否StackNotEmpty(head)intStackNotEmpty(LSNode*head){if(head->next==NULL)return0;elsereturn1;}（3）入棧StackPush(head,x)intStackPush(LSNode*head,DataTypex){LSNode*p;

p=(LSNode*)malloc(sizeof(LSNode));

p->data=x;p->next=head->next;head->next=p;

return1;}（4）出棧StackPop(head,*d)intStackPop(LSNode*head,DataType*d){LSNode*p=head->next;if(p==NULL){printf("棧已空出錯！"); return0;}

head->next=p->next;*d=p->data; free(p);return1;}（5）取棧頂數(shù)據(jù)元素StackTop(head,d)intStackTop(LSNode*head,DataType*d){LSNode*p=head->next; if(p==NULL) { printf("棧已空出錯！"); return0; }

*d=p->data; return1;}（6）撤消鏈式棧內存空間Destroy(*head)voidDestroy(LSNode*head){LSNode*p,*p1;

p=head; while(p!=NULL) {p1=p; p=p->next; free(p1); }}

說明：1)鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。

2)一般不會出現(xiàn)棧滿情況；除非沒有空間導致malloc分配失敗。3)采用鏈棧存儲方式的優(yōu)點是，當棧中元素個數(shù)變化較大，準確數(shù)字難以確定時，鏈棧較順序棧方便。3.2

棧應用1、括號匹配問題例：假設一個算術表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個判別表達式中括號是否正確配對的函數(shù)，并設計一個測試主函數(shù)。解題：這是一個輸入元素序列到特定輸出元素序列轉換問題。算法思想：算術表達式中右括號和左括號匹配的次序正好符合后到的括號要最先被匹配的“后進先出”棧操作特點，因此可以借助一個棧來進行判斷。括號匹配共有四種情況：（1）左右括號配對次序不正確；（2）右括號多于左括號；（3）左括號多于右括號；（4）左右括號匹配正確。具體方法：順序掃描算術表達式（表現(xiàn)為一個字符串），當遇到三種類型的左括號時讓該括號進棧；當掃描到某一種類型的右括號時，比較當前棧頂括號是否與之匹配，若匹配則退棧繼續(xù)進行判斷；若當前棧頂括號與當前掃描的括號不相同，則左右括號配對次序不正確；若字符串當前為某種類型左括號而棧已空，則右括號多于左括號；字符串循環(huán)掃描結束時，若棧非空（即棧中尚有某種類型左括號），則說明左括號多于右括號；否則，左右括號匹配正確。括號匹配共有四種情況：（1）左右括號配對次序不正確： "(())abc{[]()]"（2）右括號多于左括號： "(()))abc{[]}"（3）左括號多于右括號： "(()()abc{[]}"（4）左右括號匹配正確： "(())abc{[]}"voidExpIsCorrect(charexp[],intn){SeqStackmyStack;inti;charc;

StackInitiate(&myStack);for(i=0;i<n;i++){if((exp[i]=='(')||(exp[i]=='[')||(exp[i]=='{'))StackPush(&myStack,exp[i]);

elseif(exp[i]==')'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='(')StackPop(&myStack,&c); elseif(exp[i]==')'&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c!='(') {printf("左右括號配對次序不正確！\n"); return; }

elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='['] StackPop(&myStack,&c);

elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='[') {printf("左右括號配對次序不正確！\n"); return; }

elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='{'} StackPop(&myStack,&c);

elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='{') {printf("左右括號配對次序不正確！\n"); return; } elseif(((exp[i]==')')||(exp[i]==']')||(exp[i]=='}')) &&!StackNotEmpty(myStack)) { printf("右括號多于左括號！\n"); return; } }

if(StackNotEmpty(myStack)) printf("左括號多于右括號！\n"); else printf("左右括號匹配正確！\n");}2、表達式計算問題

表達式計算是編譯系統(tǒng)中的基本問題，其實現(xiàn)方法是棧的一個典型應用。在編譯系統(tǒng)中，要把便于人理解的表達式翻譯成能正確求值的機器指令序列，通常需要先把表達式變換成機器便于理解的形式，這就要變換表達式的表示序列。假設計算機高級語言中的一個算術表達式為

A+(B-C/D)*E這種表達式稱為中綴表達式，寫成滿足四則運算規(guī)則的相應的后綴表達式即為

ABCD/-E*+

優(yōu)點：可以直接計算中綴表達式的值。

編譯系統(tǒng)中表達式的計算分為兩個步驟：（1）把中綴表達式變換成相應的后綴表達式；（2）根據(jù)后綴表達式計算表達式的值。其中，步驟（1）這種數(shù)據(jù)序列的特定變換可以利用棧來實現(xiàn)；步驟（2）的算法也可借助棧來實現(xiàn)。

中綴表達式變換為后綴表達式的算法步驟可以總結為：

(1)設置一個棧，初始時將棧頂元素置為“＃”。

(2)順序讀入中綴表達式，當讀到的單詞為操作數(shù)時就將其輸出，并接著讀下一個單詞。

(3)令x1為當前棧頂運算符的變量，x2為當前掃描讀到運算符的變量，當順序從中綴表達式中讀入的單詞為運算符時就賦予x2，然后比較x1的優(yōu)先級與x2的優(yōu)先級，若x1的優(yōu)先級高于x2的優(yōu)先級，將x1退棧并作為后綴表達式的一個單詞輸出，然后接著比較新的棧頂運算符x1的優(yōu)先級與x2的優(yōu)先級；若x1的優(yōu)先級低于x2的優(yōu)先級，將x2進棧然后讀下一個字符；若x1的優(yōu)先級等于x2的優(yōu)先級，特別處理。 如：中綴表達式A+(B-C/D)*E＃ 后綴表達式ABCD/-E*+運算符優(yōu)先級關系表

把中綴表達式A+(B-C/D)*E變換成后綴表達式的過程

計算后綴表達式的值的過程仍是一個棧應用問題算法思想是：設置一個棧存放操作數(shù)，從左到右依次掃描后綴表達式，每讀到一個操作數(shù)就將其進棧；每讀到一個運算符就從棧頂取出兩個操作數(shù)施以該運算符所代表的運算操作，并把該運算結果作為一個新的操作數(shù)入棧；此過程一直進行到后綴表達式讀完，最后棧頂?shù)牟僮鲾?shù)就是該后綴表達式的運算結果。后綴表達式ABCD/-E*+求值過程:3.3

隊列1、隊列的基本概念(1)定義:只能在表的一端進行插入操作，在表的另一端進行刪除操作的線性表。一個隊列的示意圖如下：隊尾插入隊頭刪除a0a1a2…an-1隊頭隊尾數(shù)據(jù)集合:{a0,a1,…,an-1}，ai的數(shù)據(jù)類型為DataType。操作集合：（1）初始化QueueInitiate(Q)（2）非空否QueueNotEmpty(Q)（3）入隊列QueueAppend(Q,x)（4）出隊列QueueDelete(Q,d)（5）取隊頭數(shù)據(jù)元素QueueGet(Q,d)

3、順序隊列(1)順序隊列：順序存儲結構的隊列。2、隊列抽象數(shù)據(jù)類型(2)順序隊列的存儲結構有6個存儲空間的順序隊列動態(tài)示意圖(a)空隊列frontrear=012345CBA(b)入隊列A、B、C后front=012345C(c)出隊列A、B后front=012345rear=EDC(d)入隊列D、E后front=012345rear=(3)順序隊列的“假溢出”問題①假溢出順序隊列因多次入隊列和出隊列操作后出現(xiàn)的雖有存儲空間但不能進行入隊列操作的情況。

可采取四種方法：

1)采用順序循環(huán)隊列；（教材中的方法）

2)按最大可能的進隊操作次數(shù)設置順序隊列的最大元素個數(shù)；（最差的方法）

3)修改出隊列算法，使每次出隊列后都把隊列中剩余數(shù)據(jù)元素向隊頭方向移動一個位置；４)修改入隊列算法，增加判斷條件，當假溢出時，把隊列中的數(shù)據(jù)元素向隊頭移動，然后完成入隊列操作。②如何解決順序隊列的假溢出問題？(4)順序循環(huán)隊列的基本原理把順序隊列所使用的存儲空間構造成一個邏輯上首尾相連的循環(huán)隊列。當rear和front達到MaxQueueSize-1后，再前進一個位置就自動到０。順序隊列a3a2a1frontrear0123..N-1a3a2a10123N-1rearfront循環(huán)隊列(5)順序循環(huán)隊列的隊空和隊滿判斷問題新問題：在順序循環(huán)隊列中，隊空特征是front=rear；隊滿時也會是front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；（教材中的方法）判隊滿：count>0&&rear==front

判隊空：count==0②設標志位，出隊時置０,入隊時置１,則可識別當前front=rear屬于何種情況判隊滿：tag==1&&rear==front

判隊空：tag==0&&rear==front③少用一個存儲單元判隊滿：front=＝(rear+1)%MaxQueueSize

判隊空：rear==front4、順序循環(huán)隊列順序循環(huán)隊列的結構體定義如下：typedefstruct{DataTypequeue[MaxQueueSize];intrear;intfront;intcount;}SeqCQueue;（1）初始化QueueInitiate(Q)voidQueueInitiate(SeqCQueue*Q){Q->rear=0; Q->front=0;Q->count=0;}（2）非空否QueueNotEmpty(Q)intQueueNotEmpty(SeqCQueueQ){if(Q.count!=0) return1;elsereturn0;}（3）入隊列QueueAppend(Q,x)intQueueAppend(SeqCQueue*Q,DataTypex){if(Q->count>0&&Q->rear==Q->front){printf("隊列已滿無法插入!\n"); return0;}else{

Q->queue[Q->rear]=x; Q->rear=(Q->rear+1)%MaxQueueSize; Q->count++; return1;}}（4）出隊列QueueDelete(Q,d)intQueueDelete(SeqCQueue*Q,DataType*d){if(Q->count==0){printf("隊列已空無數(shù)據(jù)元素出隊列!\n"); return0;}else{

*d=Q->queue[Q->front]; Q->front=(Q->front+1)%MaxQueueSize; Q->count--; return1;}}（5）取隊頭數(shù)據(jù)元素QueueGet(Q,d)intQueueGet(SeqCQueueQ,DataType*d){if(Q.count==0){printf("隊列已空無數(shù)據(jù)元素可取!\n"); return0;}else{*d=Q.queue[Q.front]; return1;}}5、鏈式隊列1)鏈式隊列鏈式存儲結構的隊列。2)鏈式隊列的存儲結構

鏈式隊列的隊頭指針指向隊列的當前隊頭結點;隊尾指針指在隊列的當前隊尾結點.

一個不帶頭結點的鏈式隊列的結構：a0a1an-1an-1∧…frontrear結點的結構體可定義如下：typedefstructqnode{DataTypedata;structqnode*next;}LQNode;

隊頭指針front和隊尾指針rear的結構體類型：typedefstruct{LQNode*front; LQNode*rear; }LQueue;3)鏈式隊列操作的實現(xiàn)

（1）初始化QueueInitiate(Q)voidQueueInitiate(LQueue*Q){Q->rear=NULL; Q->front=NULL; }

（2）非空否QueueNotEmpty(Q)intQueueNotEmpty(LQueueQ){if(Q.front==NULL)return0; elsereturn1;}

（3）入隊列QueueAppend(Q,x)intQueueAppend(LQueue*Q,DataTypex){LSNode*p;

p=(LQNode*)malloc(sizeof(LQNode)); p->data=x; p->next=NULL;if(Q->rear!=NULL)Q->rear->next=p; Q->rear=p; if(Q->front==NULL)Q->front=p;

return1;}（4）出隊列QueueDelete(Q,d)intQueueDelete(LQueue*Q,DataType*d){LQNode*p; if(Q->front==NULL) {printf("隊列已空無數(shù)據(jù)元素出隊列!\n"); return0;} else {*d=Q->front->data;

p=Q->front; Q->front=Q->front->next; if(Q->front==NULL)Q->rear=NULL; free(p); return1; }}（5）取隊頭數(shù)據(jù)元素QueueGet(Q,d)intQueueGet(LQueueQ,DataType*d){if(Q.front==NULL) {printf("隊列已空無數(shù)據(jù)元素出隊列!\n"); return0; } else {*d=Q.front->data; return1; }}6、隊列的應用任務描述：一個計算機局域網(wǎng)系統(tǒng)中有若干臺計算機，為了節(jié)約資源，只安裝了一臺打印機，要求設計一個對打印機的打印任務進行管理的打印任務管理器，打印機的打印任務按照先來先打印的方式進行管理。任務分析：打印任務管理器可設計成一個鏈式隊列。打印任務管理器應包含的操作有：（1）初始化。（2）入隊列。把新的打印任務加入到隊尾。（3）出隊列。（4）輸出。（5）清空。任務說明：每一個打印任務應包含打印任務標識號和要打印的內容。數(shù)據(jù)結構設計：鏈式隊列的結點結構體定義如下：typedefstructnode{intid; //打印任務標識號

char*text; //要打印的內容

structnode*next; //指向下一個結點的指針}Task; //結點結構體Task鏈式隊列的頭指針、尾指針結構體定義如下：typedefstruct{Task*front; //頭指針

Task*rear; //尾指針}Queue; //鏈式隊列結構體}Queue（2）入隊列。把新的打印任務加入到隊尾。voidAppendPrintTask(Queue*taskmanager,inttid,char*text)//打印任務包括打印任務標識號tid和要打印的內容text{Task*p;p=(Task*)malloc(sizeof(Task));p->text=(char*)malloc(strlen(text)*sizeof(Task)+1);strcpy(p->text,text);p->id=tid; p->next=NULL;if(taskmanager->rear!=NULL)taskmanager->rear->next=p; taskmanager->rear=p;if(taskmanager->front==NULL)taskmanager->front=p; }

（3）出隊列。intPrintFirstTask(Queue*taskmanager)//取出隊列taskmanager中的第一個打印任務進行打印，并把該打印任務從隊頭刪除{Task*p=taskmanager->front;if(p==NULL)return0;else{printf("Taskid:%d\n",p->id);printf("Taskcontext:%s\n",p->text);}taskmanager->front=taskmanager->front->next; if(taskmanager->front==NULL)taskmanager->rear=NULL;free(p->text); free(p); return1;}3.4優(yōu)先級隊列１、優(yōu)先級隊列帶有優(yōu)先級的隊列。２、順序優(yōu)先級隊列用順序存儲結構存儲的優(yōu)先級隊列。３、優(yōu)先級隊列和一般隊列的主要區(qū)別優(yōu)先級隊列的出隊列操作不是把隊頭元素出隊列，而是把隊列中優(yōu)先級最高的元素出隊列。它的數(shù)據(jù)元素定義為如下結構體：

structDataType{

ElemTypeelem;//數(shù)據(jù)元素

intpriority;//優(yōu)先級

};

注：順序優(yōu)先級隊列除出隊列操作外的其他操作的實現(xiàn)方法與前邊討論的順序隊列操作的實現(xiàn)方法相同。出隊列操作(把優(yōu)先級最高的元素出隊列并由函數(shù)返回,優(yōu)先級相同時按先進先出的原則出隊列。取順序優(yōu)先隊列中優(yōu)先級最高的元素算法類同)出隊列算法如下：intQueueDelete(SeqPQueue*Q,DataType*d){DataTypemin;intminIndex,i;

if(Q->size<=0){printf("隊列已空無數(shù)據(jù)元素出隊列!\n"); return0;}

els