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

第3章棧和隊(duì)列

3.1棧

3.2隊(duì)列

本章小結(jié)2023/2/11/403.1.1棧的定義3.1.2棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)3.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(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)前位置是動(dòng)態(tài)的，由一個(gè)稱為棧頂指針的位置指示器指示。表的另一端稱為棧底。當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，稱為空棧。棧的插入操作通常稱為壓?；蜻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è)一個(gè)棧的輸入序列為A,B,C,D，則借助一個(gè)棧所得到的輸出序列不可能是

。

(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)造一個(gè)空棧s。DestroyStack(&s)：銷毀棧，釋放棧s占用的存儲(chǔ)空間。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棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)

假設(shè)棧的元素個(gè)數(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】編寫一個(gè)算法利用順序棧判斷一個(gè)字符串是否是對(duì)稱串。所謂對(duì)稱串是指從左向右讀和從右向左讀的序列相同。串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)酱鎯?chǔ)結(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】編寫一個(gè)算法判斷輸入的表達(dá)式中的括號(hào)是否正確配對(duì)。（假設(shè)只含有左、右圓括號(hào)）算法思路：

設(shè)置一個(gè)括號(hào)棧，掃描表達(dá)式：遇到左括號(hào)進(jìn)棧，遇到右括號(hào)，若棧頂是左括號(hào)，則出棧。否則返回false。當(dāng)表達(dá)式掃描完畢，棧為空時(shí)返回true——表示括號(hào)正確匹配，否則返回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)證括號(hào)匹配檢驗(yàn)表達(dá)式求值迷宮問題遞歸（ch5）數(shù)制轉(zhuǎn)換行編輯程序2023/2/115/401.表達(dá)式求值【問題描述】用戶輸入一個(gè)包含“+”、“-”、“*”、“/”、正整數(shù)和圓括號(hào)的合法數(shù)學(xué)表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。一個(gè)表達(dá)式由操作數(shù)（亦稱運(yùn)算對(duì)象）、操作符（亦稱運(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)換為后綴表示？把每個(gè)運(yùn)算符都移到它的兩個(gè)運(yùn)算對(duì)象的后面，然后刪除掉所有的括號(hào)即可。中綴表達(dá)式

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

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

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

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

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

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

若ch運(yùn)算符優(yōu)先級(jí)大于op棧頂運(yùn)算符優(yōu)先級(jí)，將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á)式的每一項(xiàng)，根據(jù)它的類型做如下相應(yīng)操作：如果該項(xiàng)是操作數(shù)，則將其壓入數(shù)值棧中；如果該項(xiàng)是操作符op，則連續(xù)從棧中退出兩個(gè)操作數(shù)Y和X，形成運(yùn)算指令XopY，并將結(jié)果重新壓入棧中。當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計(jì)算結(jié)果。【例】計(jì)算56#20#-4#2#+/

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

2023/2/122/403.2隊(duì)列

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

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

FirstInFirstOut)a0

a1

a2

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

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

typedef

struct{

ElemType

data[MaxSize];

int

front,rear;//隊(duì)首和隊(duì)尾指針}SqQueue;

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

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

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

0

1

2

3

4

front

(a)空隊(duì)

(b)a,b,c入隊(duì)

rear

0

1

2

3

4

front

a

b

c

隊(duì)滿rear

0

1

2

3

4

a

b

c

d

front

(c)d入隊(duì),rear

0

1

2

3

4

c

d

front

(d)出隊(duì)2次

rear

0

1

2

3

4

front

(e)出隊(duì)2次,隊(duì)空

2.環(huán)形隊(duì)中實(shí)現(xiàn)隊(duì)列的基本運(yùn)算2023/2/129/40環(huán)形隊(duì)列首尾相連，當(dāng)隊(duì)首指針front滿足front==MaxSize-1后，再前進(jìn)一個(gè)位置就自動(dòng)到0，可以利用求余運(yùn)算（%）來實(shí)現(xiàn)。隊(duì)首指針進(jìn)1：front=(front+1)％MaxSize隊(duì)尾指針進(jìn)1：rear=(rear+1)％MaxSize指針初始化：front=rear=0隊(duì)滿條件:(q->rear+1)%

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

已知front、count，求rear：

已知rear、count，求front：

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

typedef

struct{

ElemType

data[MaxSize];

intfront; //隊(duì)首指針

intcount; //隊(duì)列中元素個(gè)數(shù)}QuType;count==0count==MaxSizerear=(front+count)%MaxSize隊(duì)空的條件：隊(duì)滿的條件：隊(duì)尾指針rear：初始化：入隊(duì)：出隊(duì)：判空：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隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的隊(duì)首指針指向單鏈表的第一個(gè)結(jié)點(diǎn)，隊(duì)尾指針指向單鏈表的最后一個(gè)結(jié)點(diǎn)。只允許在單鏈表的表頭進(jìn)行刪除操作、在單鏈表的表尾進(jìn)行插入操作。鏈?zhǔn)疥?duì)列特別適合于數(shù)據(jù)元素變動(dòng)比較大的情形。在進(jìn)隊(duì)時(shí)無隊(duì)滿問題，但有隊(duì)空問題。frontrear鏈隊(duì)中數(shù)據(jù)結(jié)點(diǎn)的類型QNode定義如下:typedef

struct

qnode{

ElemTypedata;

struct

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

struct{

QNode*front;

QNode*rear;}LiQueue;

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

∧

∧

front

rear

q

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

front

rear

q

(b)入隊(duì)3個(gè)元素

a

b

∧

c

front

rear

q

(c)出隊(duì)1個(gè)元素

b

∧

c

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