第3章棧和隊列

3.1棧

3.2隊列

本章小結(jié)2023/2/11/403.1.1棧的定義3.1.2棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)3.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)3.1.4棧的應(yīng)用3.1棧（Stack）

a1a2a3a4a5a6插入xi刪除xj插入刪除2023/2/12/40棧是一種只能在一端進(jìn)行插入或刪除操作的線性表。表中允許進(jìn)行插入、刪除操作的一端稱為棧頂。棧頂?shù)漠?dāng)前位置是動態(tài)的，由一個稱為棧頂指針的位置指示器指示。表的另一端稱為棧底。當(dāng)棧中沒有數(shù)據(jù)元素時，稱為空棧。棧的插入操作通常稱為壓?；蜻M(jìn)棧，棧的刪除操作通常稱為退?；虺鰲?。棧的主要特點(diǎn)是“后進(jìn)先出”。也稱為后進(jìn)先出表。3.1.1棧的定義

2023/2/13/40a1a2a3入棧棧底棧頂插入：入棧、進(jìn)棧、壓棧棧頂棧頂棧的操作示意圖2023/2/14/40后進(jìn)先出a1a3入棧出棧棧底棧頂刪除：出棧、退棧、彈棧棧頂棧的操作示意圖a2棧頂2023/2/15/40【例3.3】設(shè)一個棧的輸入序列為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】若元素進(jìn)棧順序?yàn)?-2-3-4，能否得到3142的出棧順序？答案：否【例3.2】用S表示進(jìn)棧操作，X表示出棧操作，若元素進(jìn)棧順序?yàn)?234，為了得到1342的出棧順序，給出相應(yīng)的S和X操作串。答案：SXSSXSXX2023/2/16/40抽象數(shù)據(jù)類型棧的定義：《教材P65》基本運(yùn)算：InitStack(&s)：初始化棧，構(gòu)造一個空棧s。DestroyStack(&s)：銷毀棧，釋放棧s占用的存儲空間。StackEmpty(s)：判斷棧是否為空：為空，則返回真；否則返回假。Push(&s,e)：進(jìn)棧，將元素e插入到棧s中作為棧頂元素。Pop(&s,&e)：出棧，從棧s中退出棧頂元素，將其值賦給e。GetTop(s,&e)：取棧頂元素，返回當(dāng)前的棧頂元素，并將其值賦給e。2023/2/17/403.1.2棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)

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

typedef

struct{

ElemType

data[MaxSize]；

inttop；//棧頂指針

}SqStack；2023/2/18/40?？諚l件：top==-1

棧滿條件：top==MaxSize-1

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

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

s->top==-1(4)進(jìn)棧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棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)鏈棧的優(yōu)點(diǎn)是不存在棧滿的情況。鏈?zhǔn)綏５臈ｍ斣阪湵淼谋眍^，規(guī)定棧的所有操作都是在單鏈表的表頭進(jìn)行的。

鏈棧中數(shù)據(jù)結(jié)點(diǎn)的類型LiStack定義如下:

typedef

struct

linknode{

ElemTypedata;

struct

linknode*next;}LiStack;

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

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

(5)出棧Pop(s,e)

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

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

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

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

<操作數(shù)><操作數(shù)><操作符>，如AB+；2023/2/116/40中綴表達(dá)式

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

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

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

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

若ch為數(shù)字，將后續(xù)所有數(shù)字依次存放到postexp中，并以字符“#”標(biāo)志數(shù)值串結(jié)束。

若ch為左括號“(”，則將此括號進(jìn)棧到運(yùn)算符棧op中。

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

若ch運(yùn)算符優(yōu)先級小于op棧頂運(yùn)算符優(yōu)先級，則依次出棧并存入到postexp中。

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

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

2023/2/122/403.2隊列

3.2.1隊列的定義3.2.2隊列的順序存儲結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)3.2.3隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)3.2.4隊列的應(yīng)用3.2.5雙端隊列2023/2/123/40隊列（Queue）簡稱隊，它也是一種運(yùn)算受限的線性表，其限制為僅允許在表的一端進(jìn)行插入，在另一端進(jìn)行刪除。把進(jìn)行插入的一端稱做隊尾（rear），進(jìn)行刪除的一端稱做隊首（front）。向隊列中插入新元素稱為進(jìn)隊或入隊，新元素進(jìn)隊后就成為新的隊尾元素；從隊列中刪除元素稱為出隊或離隊，元素出隊后，其后繼元素就成為隊首元素。3.2.1隊列的定義

特點(diǎn)：先進(jìn)先出(FIFO,

FirstInFirstOut)a0

a1

a2

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

3.2.2隊列的順序存儲結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)假設(shè)隊列的元素個數(shù)最大不超過整數(shù)MaxSize，所有元素都具有同一數(shù)據(jù)類型ElemType，則順序隊列類型SqQueue定義如下:

typedef

struct{

ElemType

data[MaxSize];

int

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

初始時，設(shè)front=rear=-1。

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

——隊尾指針指示實(shí)際隊尾的位置。先將隊頭指針加1，再取出該位置元素?！狀^指針指示實(shí)際隊頭位置的前一位置。隊滿時再入隊將溢出（“假溢出”）。隊空時出隊需要進(jìn)行隊空處理。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.環(huán)形隊中實(shí)現(xiàn)隊列的基本運(yùn)算2023/2/129/40環(huán)形隊列首尾相連，當(dāng)隊首指針front滿足front==MaxSize-1后，再前進(jìn)一個位置就自動到0，可以利用求余運(yùn)算（%）來實(shí)現(xiàn)。隊首指針進(jìn)1：front=(front+1)％MaxSize隊尾指針進(jìn)1：rear=(rear+1)％MaxSize指針初始化：front=rear=0隊滿條件:(q->rear+1)%

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

已知front、count，求rear：

已知rear、count，求front：

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

typedef

struct{

ElemType

data[MaxSize];

intfront; //隊首指針

intcount; //隊列中元素個數(shù)}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隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)隊列的隊首指針指向單鏈表的第一個結(jié)點(diǎn)，隊尾指針指向單鏈表的最后一個結(jié)點(diǎn)。只允許在單鏈表的表頭進(jìn)行刪除操作、在單鏈表的表尾進(jìn)行插入操作。鏈?zhǔn)疥犃刑貏e適合于數(shù)據(jù)元素變動比較大的情形。在進(jìn)隊時無隊滿問題，但有隊空問題。frontrear鏈隊中數(shù)據(jù)結(jié)點(diǎn)的類型QNode定義如下:typedef

struct

qnode{

ElemTypedata;

struct

qnode*next;}QNode;鏈隊中頭結(jié)點(diǎn)的類型LiQueue定義如下:typedef

struct{

QNode*front;

QNode*rear;}LiQueue;

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

∧

∧

front

rear

q

(a)鏈隊初態(tài)

front

rear

q

(b)入隊3個元素

a

b

∧

c

front

rear

q

(c)出隊1個元素

b

∧

c

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