第3章棧和隊列

3.1棧

3.2隊列

本章小結2023/2/11/403.1.1棧的定義3.1.2棧的順序存儲結構及其基本運算的實現3.1.3棧的鏈式存儲結構及其基本運算的實現3.1.4棧的應用3.1棧（Stack）

a1a2a3a4a5a6插入xi刪除xj插入刪除2023/2/12/40棧是一種只能在一端進行插入或刪除操作的線性表。表中允許進行插入、刪除操作的一端稱為棧頂。棧頂的當前位置是動態的，由一個稱為棧頂指針的位置指示器指示。表的另一端稱為棧底。當棧中沒有數據元素時，稱為空棧。棧的插入操作通常稱為壓棧或進棧，棧的刪除操作通常稱為退棧或出棧。棧的主要特點是“后進先出”。也稱為后進先出表。3.1.1棧的定義

2023/2/13/40a1a2a3入棧棧底棧頂插入：入棧、進棧、壓棧棧頂棧頂棧的操作示意圖2023/2/14/40后進先出a1a3入棧出棧棧底棧頂刪除：出棧、退棧、彈棧棧頂棧的操作示意圖a2棧頂2023/2/15/40【例3.3】設一個棧的輸入序列為A,B,C,D，則借助一個棧所得到的輸出序列不可能是

。

(A)A,B,C,D(B)D,C,B,A(C)A,C,D,B(D)D,A,B,C

答案：D【例3.1】若元素進棧順序為1-2-3-4，能否得到3142的出棧順序？答案：否【例3.2】用S表示進棧操作，X表示出棧操作，若元素進棧順序為1234，為了得到1342的出棧順序，給出相應的S和X操作串。答案：SXSSXSXX2023/2/16/40抽象數據類型棧的定義：《教材P65》基本運算：InitStack(&s)：初始化棧，構造一個空棧s。DestroyStack(&s)：銷毀棧，釋放棧s占用的存儲空間。StackEmpty(s)：判斷棧是否為空：為空，則返回真；否則返回假。Push(&s,e)：進棧，將元素e插入到棧s中作為棧頂元素。Pop(&s,&e)：出棧，從棧s中退出棧頂元素，將其值賦給e。GetTop(s,&e)：取棧頂元素，返回當前的棧頂元素，并將其值賦給e。2023/2/17/403.1.2棧的順序存儲結構及其基本運算的實現

假設棧的元素個數最大不超過正整數MaxSize，所有元素都具有同一數據類型ElemType，則可用下列方式來定義順序棧類型SqStack:

typedef

struct{

ElemType

data[MaxSize]；

inttop；//棧頂指針

}SqStack；2023/2/18/40棧空條件：top==-1

棧滿條件：top==MaxSize-1

進棧操作：top++;再將元素放在top處退棧操作：從top處取出元素，再將top--;例如：2023/2/19/40在順序棧中實現棧的基本運算算法:(1)初始化棧InitStack(s)：s->top=-1;(2)銷毀棧DestroyStack(s)：

free(s);(3)判斷棧是否為空StackEmpty(s)：

s->top==-1(4)進棧Push(s,e)：s->top++;s->data[s->top]=e;(5)出棧Pop(s,e)：e=s->data[s->top];s->top--;(6)取棧頂元素GetTop(s,e)：e=s->data[s->top];注意棧空、棧滿的條件！2023/2/110/40【例3.4】編寫一個算法利用順序棧判斷一個字符串是否是對稱串。所謂對稱串是指從左向右讀和從右向左讀的序列相同。串1：abcba串2：abcdabool

symmetry(ElemType

str[]){………}for(i=0;str[i]!=‘\0’;i++)

Push(st,str[i]);for(i=0;str[i]!=‘\0’;i++){

Pop(st,e);if()……}2023/2/111/403.1.3棧的鏈式存儲結構及其基本運算的實現鏈棧的優點是不存在棧滿的情況。鏈式棧的棧頂在鏈表的表頭，規定棧的所有操作都是在單鏈表的表頭進行的。

鏈棧中數據結點的類型LiStack定義如下:

typedef

struct

linknode{

ElemTypedata;

struct

linknode*next;}LiStack;

棧空條件：s->next==NULL

棧滿條件：不考慮進棧操作：在頭結點之后插入退棧操作：刪除頭結點之后的數據結點2023/2/112/40在鏈棧中的基本運算算法:^ssa1a2an…(1)初始化棧InitStack(s)(2)銷毀棧DestoryStack(s)(3)判斷棧是否為空StackEmpty(s)(4)進棧Push(s,e)

(5)出棧Pop(s,e)

(6)取棧頂元素GetTop(s,e)pe2023/2/113/40【例3.5】編寫一個算法判斷輸入的表達式中的括號是否正確配對。（假設只含有左、右圓括號）算法思路：

設置一個括號棧，掃描表達式：遇到左括號進棧，遇到右括號，若棧頂是左括號，則出棧。否則返回false。當表達式掃描完畢，棧為空時返回true——表示括號正確匹配，否則返回false。①((3+5)*2-3)/2②((3+5)*2-3/2③(3+5)*2-3)/22023/2/114/403.1.4棧的應用回文驗證括號匹配檢驗表達式求值迷宮問題遞歸（ch5）數制轉換行編輯程序2023/2/115/401.表達式求值【問題描述】用戶輸入一個包含“+”、“-”、“*”、“/”、正整數和圓括號的合法數學表達式，計算該表達式的運算結果。一個表達式由操作數（亦稱運算對象）、操作符（亦稱運算符）和分界符組成。算術表達式有三種表示：中綴(infix)表示

<操作數><操作符><操作數>，如A+B；前綴(prefix)表示

<操作符><操作數><操作數>，如+AB；后綴(postfix)表示

<操作數><操作數><操作符>，如AB+；2023/2/116/40中綴表達式

a+b*(c-d)-e/f后綴表達式abcd-*+ef/-前綴表達式

-+a*b–cd/ef編譯程序一般使用后綴表示求解表達式的值！問題：中綴表示如何轉換為后綴表示？把每個運算符都移到它的兩個運算對象的后面，然后刪除掉所有的括號即可。中綴表達式

(A+B)*D-E/(F+A*D)+C后綴表達式

AB+D*EFAD*+/-C+2023/2/117/40假設用exp字符數組存儲算術表達式，其對應后綴表達式存放在字符數組postexp中。在將算術表達式轉換成后綴表達式的過程中用一個字符數組op作為運算符棧。具體步驟如下:初始化運算符棧op，將“=”進棧作為棧底元素。while(從exp讀取字符ch，ch!='\0'){

若ch為數字，將后續所有數字依次存放到postexp中，并以字符“#”標志數值串結束。

若ch為左括號“(”，則將此括號進棧到運算符棧op中。

若ch為右括號“)”，則將運算符棧op中左括號“(”以前的運算符依次出棧并存放到postexp中，然后將左括號“(”刪除。

若ch運算符優先級小于op棧頂運算符優先級，則依次出棧并存入到postexp中。

若ch運算符優先級大于op棧頂運算符優先級，將ch進棧。}若字符串exp掃描完畢，則將運算符棧op中“=”之前的所有運算符依次出棧并存放到postexp中。最后得到后綴表達式postexp。2023/2/118/40a+bcd/ef`\0`exppostexp+abcdef運算符棧opchchchchchch-/2023/2/119/40表達式“(56-20)/(4+2)”轉換成后綴表達式的過程：2023/2/120/40后綴表達式求值從左向右順序掃描表達式的每一項，根據它的類型做如下相應操作：如果該項是操作數，則將其壓入數值棧中；如果該項是操作符op，則連續從棧中退出兩個操作數Y和X，形成運算指令XopY，并將結果重新壓入棧中。當表達式的所有項都掃描并處理完后，棧頂存放的就是最后的計算結果。【例】計算56#20#-4#2#+/

(56–20)/(4+2)2023/2/121/40【問題描述】給定一個M×N的迷宮圖，求一條從指定入口到出口的路徑。2.求解迷宮問題圖中每個方塊，空白表示通道，陰影表示墻。所求路徑必須是簡單路徑，即在求得的路徑上不能重復出現同一通道塊。

2023/2/122/403.2隊列

3.2.1隊列的定義3.2.2隊列的順序存儲結構及其基本運算的實現3.2.3隊列的鏈式存儲結構及其基本運算的實現3.2.4隊列的應用3.2.5雙端隊列2023/2/123/40隊列（Queue）簡稱隊，它也是一種運算受限的線性表，其限制為僅允許在表的一端進行插入，在另一端進行刪除。把進行插入的一端稱做隊尾（rear），進行刪除的一端稱做隊首（front）。向隊列中插入新元素稱為進隊或入隊，新元素進隊后就成為新的隊尾元素；從隊列中刪除元素稱為出隊或離隊，元素出隊后，其后繼元素就成為隊首元素。3.2.1隊列的定義

特點：先進先出(FIFO,

FirstInFirstOut)a0

a1

a2

an-1frontrear2023/2/124/40隊列的基本運算：InitQueue(&q)：初始化隊列。構造一個空隊列q。DestroyQueue(&q)：銷毀隊列。釋放隊列q占用的存儲空間。QueueEmpty(q)：判斷隊列是否為空。若隊列q為空，則返回真；否則返回假。enQueue(&q,e)：進隊列。將元素e進隊作為隊尾元素。deQueue(&q,&e)：出隊列。從隊列q中出隊一個元素，并將其值賦給e。【例3.6】若元素進隊順序為1-2-3-4，能否得到3142的出隊順序？答案：否2023/2/125/40

3.2.2隊列的順序存儲結構及其基本運算的實現假設隊列的元素個數最大不超過整數MaxSize，所有元素都具有同一數據類型ElemType，則順序隊列類型SqQueue定義如下:

typedef

struct{

ElemType

data[MaxSize];

int

front,rear;//隊首和隊尾指針}SqQueue;

初始時，設front=rear=-1。

rear指向隊尾；front指向隊首的前一個位置。2023/2/126/401.基于順序存儲的隊列的基本運算frontrearA入隊AfrontrearB入隊ABfrontrearC,D入隊ABCDfrontrearA出隊BCDfrontrearB出隊CDfrontrearE,F,G入隊CDEFGCDEFGfrontrearH入隊,“溢出”frontrear空隊列MaxSize-12023/2/127/40基于順序存儲隊列的基本運算初始化隊列：銷毀隊列：隊空條件：隊滿條件：入隊操作：出隊操作：解決假溢出的辦法之一：將存放隊列元素的數組首尾相接，形成一個循環（環形）隊列。front==rearrear==MaxSize－1front=rear=-1free(q);先將隊尾指針加1，再將新元素加入該位置。

——隊尾指針指示實際隊尾的位置。先將隊頭指針加1，再取出該位置元素。——隊頭指針指示實際隊頭位置的前一位置。隊滿時再入隊將溢出（“假溢出”）。隊空時出隊需要進行隊空處理。2023/2/128/40rear

0

1

2

3

4

front

(a)空隊

(b)a,b,c入隊

rear

0

1

2

3

4

front

a

b

c

隊滿rear

0

1

2

3

4

a

b

c

d

front

(c)d入隊,rear

0

1

2

3

4

c

d

front

(d)出隊2次

rear

0

1

2

3

4

front

(e)出隊2次,隊空

2.環形隊中實現隊列的基本運算2023/2/129/40環形隊列首尾相連，當隊首指針front滿足front==MaxSize-1后，再前進一個位置就自動到0，可以利用求余運算（%）來實現。隊首指針進1：front=(front+1)％MaxSize隊尾指針進1：rear=(rear+1)％MaxSize指針初始化：front=rear=0隊滿條件:(q->rear+1)%

MaxSize==q->front隊空條件:q->rear==q->front注意：環形隊列最多存放MaxSize-1個元素！問題：如何求環形隊列中的元素個數？2023/2/130/40已知front、rear，求count：

已知front、count，求rear：

已知rear、count，求front：

count=4count=3MaxSize＝5【例3.7】對于環形隊列來說，如果知道隊頭指針和隊列中元素個數，就可以計算出隊尾指針。也就是說，可以用隊列中元素個數代替隊尾指針。設計出這種環形隊列的初始化、入隊、出隊和判空算法。count=(rear-front+MaxSize)%MaxSizerear=(front+count)%MaxSizefront=(rear-count+MaxSize)%MaxSize2023/2/131/40解:已知隊頭指針front和隊列中元素個數count。環形隊列的類型定義如下:

typedef

struct{

ElemType

data[MaxSize];

intfront; //隊首指針

intcount; //隊列中元素個數}QuType;count==0count==MaxSizerear=(front+count)%MaxSize隊空的條件：隊滿的條件：隊尾指針rear：初始化：入隊：出隊：判空：rear=(q->front+q->count+MaxSize)%MaxSize;rear=(rear+1)%MaxSize;q->data[rear]=x;q->count++;q->front=(q->front+1)%MaxSize;x=q->data[q->front];q->count--;2023/2/132/403.2.3隊列的鏈式存儲結構及其基本運算的實現隊列的隊首指針指向單鏈表的第一個結點，隊尾指針指向單鏈表的最后一個結點。只允許在單鏈表的表頭進行刪除操作、在單鏈表的表尾進行插入操作。鏈式隊列特別適合于數據元素變動比較大的情形。在進隊時無隊滿問題，但有隊空問題。frontrear鏈隊中數據結點的類型QNode定義如下:typedef

struct

qnode{

ElemTypedata;

struct

qnode*next;}QNode;鏈隊中頭結點的類型LiQueue定義如下:typedef

struct{

QNode*front;

QNode*rear;}LiQueue;

2023/2/133/40鏈隊的入隊和出隊操作示意圖

∧

∧

front

rear

q

(a)鏈隊初態

front

rear

q

(b)入隊3個元素

a

b

∧

c

front

rear

q

(c)出隊1個元素

b

∧

c

2023/2/134/40鏈隊存儲中的基本運算算法(1)初始化隊列InitQueue(q)：(2)銷毀隊列DestroyQueue(q