2015秋數(shù)據(jù)結(jié)構(gòu)課程-第3章-棧和隊(duì)列

第3章 棧和隊(duì)列2015/9/14工業(yè)大學(xué)測繪學(xué)院slide2第3章棧和隊(duì)列學(xué)習(xí)目標(biāo)掌握棧和隊(duì)列的定義、特性，并能正確應(yīng)用它們解決實(shí)際問題。熟練掌握棧的順序

、鏈?zhǔn)?/p>

以及相應(yīng)操作的實(shí)現(xiàn)，特別注意?？蘸蜅M的條件。熟練掌握隊(duì)列的順序

、鏈?zhǔn)?/p>

以及相應(yīng)操作的實(shí)現(xiàn)，特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide3第3章棧和隊(duì)列本章主要內(nèi)容3.1棧的邏輯結(jié)構(gòu)3.2棧的

結(jié)構(gòu)3.3棧的應(yīng)用3.4隊(duì)列的邏輯結(jié)構(gòu)3.5隊(duì)列的 結(jié)構(gòu)3.6隊(duì)列的應(yīng)用2015/9/14工業(yè)大學(xué)測繪學(xué)院slide4第3章棧和隊(duì)列3.1棧的邏輯結(jié)構(gòu)2015/9/14工業(yè)大學(xué)測繪學(xué)slide5第3章棧和隊(duì)列3.1棧的邏輯結(jié)構(gòu)（

Cont.）棧：限定僅在表尾進(jìn)行 和刪除操作的線性表?？諚＃翰缓魏螖?shù)據(jù)元素的棧。棧頂和棧底：允許

（入棧、進(jìn)棧、壓棧）和刪除（出棧、彈棧）的一端稱為棧頂，另一端稱為棧底?；静僮鳎涸跅ｍ斶M(jìn)行 、刪除、棧的初始化、判空及取棧頂元素。棧的特點(diǎn)：后進(jìn)先出（Last

In

Out，LIFO）。例：棧S=（a1，a2，……，an-1

，an）棧底 棧頂2015/9/14工業(yè)大學(xué)測繪學(xué)院slide6第3章棧和隊(duì)列3.1棧的邏輯結(jié)構(gòu)（

Cont.）例3.1：一個(gè)棧的輸入序列為1,2,3，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？可以通過窮舉所有可能性來求解：①

1入1出，

2入2出，3入3出， 即123；②

1入1出，

2、3入，3、2出， 即132；即231；即213；即321；③

1、2入，2出，

3入3出，④

1、2入，2、1出，3入3出，⑤

1、2、3入，3、2、1出，合計(jì)有5種可能性。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide7第3章棧和隊(duì)列3.1棧的邏輯結(jié)構(gòu)（

Cont.）例3.2：設(shè)依次進(jìn)入一個(gè)棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：Ａ）a，b，c，dＣ）b，c，d，aＢ）c，d，a，bＤ）a，c，d，b2015/9/14工業(yè)大學(xué)測繪學(xué)院slide8第3章棧和隊(duì)列3.1棧的邏輯結(jié)構(gòu)（

Cont.）棧的抽象數(shù)據(jù)類型ADTStack

{數(shù)據(jù)對(duì)象：D＝{

ai

|

ai

∈ElemSet,

i=1,2,...,n,n≥0

}數(shù)據(jù)關(guān)系：R1＝{

<ai-1,

ai

>|

ai-1,

ai∈D,

i=2,...,n}約定an

端為棧頂，a1基本操作：……端為棧底。}2015/9/14工業(yè)大學(xué)測繪學(xué)院slide9第3章棧和隊(duì)列3.1棧的邏輯結(jié)構(gòu)（

Cont.）2015/9/14工業(yè)大學(xué)測繪學(xué)slide10棧的基本操作：InitStack(&S)DestroyStack(&S)StackLength(S)StackEmpty(S)GetTop(S,

&e)ClearStack(&S)Push(&S,

e)Pop(&S,

&e)//初始化棧//銷毀棧//獲取棧的長度//棧是否為空//若棧非空，獲取棧頂元素//將棧清空//將新元素壓棧//將棧頂元素出棧，并返回其值第3章棧和隊(duì)列3.2

棧的結(jié)構(gòu)—順序棧單元依次存放自棧底到棧順序棧：利用一組地址連續(xù)的頂?shù)臄?shù)據(jù)元素。結(jié)構(gòu)定義：#define

STACK_INIT_SIZE

100#define

STACKINCREMENT

10typedef struct

{ElemType

*base;

//棧底指針ElemType

*top;

//棧頂指針int

stacksize;

//

當(dāng)前分配的

空間}SqStck;

//順序棧2015/9/14工業(yè)大學(xué)測繪學(xué)院slide11第3章棧和隊(duì)列3

.

2

棧的

結(jié)構(gòu)—順序棧（

Cont.）base為棧底指針,始終指向棧底,base=NULL表示棧結(jié)構(gòu)不存在。top為棧頂指針,初值指向棧底, 即top=base，表示棧空。非空棧的棧頂指針top始終指向棧頂元素的下一個(gè)位置。入棧： 新的棧頂元素，指針top加1---先 后加1出棧：指針top減1，刪除棧頂元素---先減1后刪除FEDCBAtop棧滿top-base=stacksizettopbase?？杖霔ush(s,x):s[top++]=x;出棧Pop(s,x):x=s[--top];base2015/9/14工業(yè)大學(xué)測繪學(xué)院slide12第3章棧和隊(duì)列3

.

2

棧的

結(jié)構(gòu)—順序棧（

Cont.）順序棧的壓棧操作：Status

Push(SqStack*

pS,

ElemType

e)

{if

(pS->top

-

pS->base

>=

pS->stacksize)

{pS->base

=

(ElemType*)realloc(pS->base,(pS->stacksize

+

STACKINCREMENT)*sizeof(ElemType));if

(!pS->base)

exit(0);pS->top

=

pS->base

+

pS->stacksize;pS->stacksize

+=

STACKINCREMENT;}*pS->top++=e;//改變S.top的值return

OK;}

//Push2015/9/14工業(yè)大學(xué)測繪學(xué)院slide13第3章棧和隊(duì)列3

.

2

棧的

結(jié)構(gòu)—順序棧（

Cont.）順序棧的出棧操作：Status

Pop(SqStack*

pS,

ElemType*

pe)

{//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK;否則返回ERRORif

(pS->top

==

pS->base)

return

ERROR;*pe

=

*--pS->top;return

OK;}

//

Pop//改變S.top的值2015/9/14工業(yè)大學(xué)測繪學(xué)院slide14第3章棧和隊(duì)列注意:

鏈棧中指針的方向3

.

2

棧的

結(jié)構(gòu)—鏈棧鏈棧：棧的鏈?zhǔn)?結(jié)構(gòu)稱為鏈棧，它是運(yùn)算受限的單鏈表。由于只能在鏈表頭部進(jìn)行操作，故鏈表通常不設(shè)頭結(jié)點(diǎn)，棧頂指針就是鏈表的頭指針。棧頂指針∧a1anan-1棧底元素2015/9/14工業(yè)大學(xué)測繪學(xué)院slide15第3章棧和隊(duì)列3

.

2

棧的

結(jié)構(gòu)—鏈棧（

Cont.）鏈棧的結(jié)構(gòu)：與單鏈表相同，壓棧和出棧操作即為在頭指針處的和刪除。鏈棧的特點(diǎn)：內(nèi)存足夠大的情況下，鏈?zhǔn)綏o“棧滿”問題，空間可擴(kuò)充。、刪除操作只發(fā)生在鏈表的頭指針位置。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide16第3章棧和隊(duì)列3.3 棧的應(yīng)用—數(shù)制轉(zhuǎn)換2808

10248

128

08

16

002數(shù)制轉(zhuǎn)換（除模留余法）例：(1024)10=(

2000

)8余數(shù)商2015/9/14工業(yè)大學(xué)測繪學(xué)slide17{棧*/void

conversion(

)InitStack(S);scanf(“%d”,N);while(N){Push(S,N%8);/*余數(shù)壓N=N/8;}while(!StackEmpty(S)){Pop(S,e);

/*出棧*/Printf(“%d”,e);}}第3章棧和隊(duì)列3.3

棧的應(yīng)用—括號(hào)匹配檢驗(yàn)括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中（［］（））或［（［

］［ ］）］等為正確的格式，［（

］）或（［（

））或?yàn)椴徽_的格式。例如：考慮下列括號(hào)序列：(()])均[([][])]12345678分析可能出現(xiàn)的不匹配的情況:到來的右括弧非是所“期待”的;直到結(jié)束，也沒有到來所“期待”的括弧;2015/9/14工業(yè)大學(xué)測繪學(xué)院slide18第3章棧和隊(duì)列3.3

棧的應(yīng)用—括號(hào)匹配檢驗(yàn)（

Cont.）括號(hào)匹配的檢驗(yàn)算法的基本思想凡出現(xiàn)左括弧，則進(jìn)棧；凡出現(xiàn)右括弧，首先檢查棧是否空若棧空，則表明該“右括弧”多余否則和棧頂元素比較，若相匹配，則“左括弧出棧”否則表明不匹配表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？?，則表明表達(dá)式中匹配正確否則表明“左括弧”有余2015/9/14工業(yè)大學(xué)測繪學(xué)院slide19第3章棧和隊(duì)列3.3

棧的應(yīng)用—迷宮求解求迷宮路徑算法的基本思想：若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無通路”，則將當(dāng)前位置從路徑中刪除出去。通常用的是“窮舉求解”的方法############$$$####$$$###$$#####################################2015/9/14工業(yè)大學(xué)測繪學(xué)院slide20第3章棧和隊(duì)列3.3

棧的應(yīng)用—迷宮求解（

Cont.）迷宮求解問題：一個(gè)迷宮可用下圖所示方陣[m,n]表示，0表示能通過，1表示不能通過?，F(xiàn)假設(shè)從左上角[1,1]進(jìn)入迷宮，設(shè)計(jì)算法，尋求一條從右下角[m,n]出去的路徑。0100011000111111000110111001110110000111100111101111011011001101001011111110011011101001110111100111111110011011011111011100011011000000011111000111100100111110111102015/9/14工業(yè)大學(xué)測繪學(xué)院slide21第3章棧和隊(duì)列3.3

棧的應(yīng)用—迷宮求解（

Cont.）迷宮求解問題分析：迷宮用二維數(shù)組Maze[i,j](1≤i≤m,1≤j≤n)表示;入口maze[1,1]=0;當(dāng)前任意位置可用（i,j）坐標(biāo)表示；位置(i,j)周圍有8個(gè)方向可以走通，分別記為：E，SE

，S，SW，W，NW，N，NE。方向v按從正東開始且順時(shí)針分別記為1-8，v=1,…,8;設(shè)二維數(shù)組move

記下八個(gè)方位的增量；2015/9/14工業(yè)大學(xué)測繪學(xué)院slide22第3章棧和隊(duì)列3.3

棧的應(yīng)用—迷宮求解（

Cont.）迷宮求解問題：從(i,j)

到(g,h)

且v=2(東南)則有：g

=

i

+move[

2,

1

]

=

i

+

1

;2015/9/14工業(yè)大學(xué)測繪學(xué)院slide23第3章棧和隊(duì)列3.3

棧的應(yīng)用—迷宮求解（

Cont.）迷宮求解問題：為避免時(shí)時(shí)監(jiān)測邊界狀態(tài)，可把二維數(shù)組maze[1:m,1:n]擴(kuò)大為maze[0:m+1,0:n+1],且令0

行和0列、m+1行和n列的值為。/9/14工業(yè)大學(xué)測繪學(xué)院slide24第3章棧和隊(duì)列3.3

棧的應(yīng)用—迷宮求解（

Cont.）迷宮求解問題：采用試探的方法，當(dāng)?shù)竭_(dá)某個(gè)位置且周圍八個(gè)方向走不通時(shí)需要回退到上一個(gè)位置，并換一個(gè)方向繼續(xù)試探；為解決回退問題，需設(shè)一個(gè)棧，當(dāng)?shù)竭_(dá)一個(gè)新位置時(shí)將（v,

i,j）進(jìn)棧，回退時(shí)退棧。每次換方向?qū)ふ倚挛恢脮r(shí)，需測試該位置以前是否已經(jīng)經(jīng)過，對(duì)已到達(dá)的位置，不能重復(fù)試探，為此設(shè)矩陣mark

，其初值為0

，一旦到達(dá)位置(i,j)時(shí)，置

mark[i,

j]=1。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide25第3章棧和隊(duì)列3.3

棧的應(yīng)用—迷宮求解（

Cont.）迷宮求解問題算法描述：1.在(1,1)進(jìn)入迷宮，并向正東（v=1）方向試探。2.監(jiān)測下一方位(g,

h)。若(g,

h)=(m,n)且maze[m,n]=0，則耗子到達(dá)出口，輸出走過的路徑；程序結(jié)束。3.若(g,h)≠(m,n)，但(g,h)方位能走通且第一次經(jīng)過，則記下這一步，并從(g,h)出發(fā)，再向東試探下一步。否則仍在(i,

j)方位換一個(gè)方向試探。4.若(i,j)方位周圍8個(gè)方位阻塞或已經(jīng)過，則需退一步，并換一個(gè)方位試探。若(i,

j)=(1,1)則到達(dá)，說明迷宮走不通。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide26第3章棧和隊(duì)列3.3

棧的應(yīng)用—表達(dá)式求值表達(dá)式(a

+

b)

*

(a

－

b)高級(jí)語言中，采用類似自然語言的中綴表達(dá)式，但計(jì)算機(jī)對(duì)中綴表達(dá)式的處理是很的，而對(duì)后綴或前綴表達(dá)式的計(jì)算則顯得非常簡單。前綴表達(dá)式（波蘭式）中綴表達(dá)式后綴表達(dá)式（逆波蘭式）*+ab－ab(a

+

b)

*

(a

－

b)ab+ab－*2015/9/14工業(yè)大學(xué)測繪學(xué)院slide27第3章棧和隊(duì)列3.3

棧的應(yīng)用—表達(dá)式求值（

Cont.）ab+ab－*后綴表達(dá)式的特點(diǎn)：在后綴表達(dá)式中，變量（操作數(shù)）出現(xiàn)的順序與中綴表達(dá)式順序相同。后綴表達(dá)式中不需要括號(hào)規(guī)定計(jì)算順序，而由運(yùn)算操作符的位置來確定運(yùn)算順序。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide28第3章棧和隊(duì)列3.3

棧的應(yīng)用—表達(dá)式求值（

Cont.）將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式A+(B-C)*D+E/F

ABC-D*+EF/+對(duì)中綴表達(dá)式從左至右依次掃描，由于操作數(shù)的順序保持不變，當(dāng)遇到操作數(shù)時(shí)直接輸出。為調(diào)整運(yùn)算順序，設(shè)立一個(gè)棧用以保存操作符，掃描到操作符時(shí)，將操作符壓入棧中。進(jìn)棧的原則是保持入棧操作符高于棧頂操作符的優(yōu)先級(jí)；否則，將棧頂操作符依次退棧并輸出，直到滿足要求為止；遇到“（”進(jìn)棧，當(dāng)遇到“）”時(shí)，退棧輸出直到“）”為止。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide29第3章棧和隊(duì)列3.3

棧的應(yīng)用—表達(dá)式求值（

Cont.）例：將中綴表達(dá)式A+(B-C)*D+E/F轉(zhuǎn)化為后綴表達(dá)式步驟中綴表達(dá)式Stack輸出9D+E/F+*ABC-10+E/F+*ABC-D11E/F+ABC-D*+12/F+ABC-D*+E13F+/ABC-D*+E14+/ABC-D*+EF15+ABC-D*+EF/16ABC-D*+EF/+2015/9/14工業(yè)大學(xué)測繪學(xué)院slide30第3章棧和隊(duì)列3.3

棧的應(yīng)用—表達(dá)式求值（

Cont.）由后綴表達(dá)式計(jì)算表達(dá)式的值對(duì)后綴表達(dá)式從左至右依次掃描，與中綴轉(zhuǎn)后綴相反，遇到操作數(shù)時(shí)，將操作數(shù)進(jìn)棧保存。當(dāng)遇到操作符時(shí)，從棧中退出兩個(gè)操作數(shù)并作相應(yīng)運(yùn)算，將計(jì)算結(jié)果進(jìn)棧保存；直到表達(dá)式結(jié)束，棧中唯一元素

即為表達(dá)式的值。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide31第3章棧和隊(duì)列3.3

棧的應(yīng)用—表達(dá)式求值（

Cont.）例：計(jì)算表達(dá)式a*b+(c-d/e)*f的值a

b

c

d

e

/

f

+abd/ec-d/e(c-d/e)fab+(c-d/e)f2015/9/14工業(yè)大學(xué)測繪學(xué)院slide32第3章棧和隊(duì)列3.4 隊(duì)列的邏輯結(jié)構(gòu)2015/9/14工業(yè)大學(xué)測繪學(xué)slide33第3章棧和隊(duì)列3.4

隊(duì)列的邏輯結(jié)構(gòu)（）隊(duì)列：只允許在一端進(jìn)行 操作，而另一端進(jìn)行刪除操作的線性表?？贞?duì)列：不含任何數(shù)據(jù)元素的隊(duì)列。隊(duì)尾和隊(duì)首：允許 （也稱入隊(duì)、進(jìn)隊(duì)）的一端稱為隊(duì)尾，允許刪除（也稱出隊(duì)）的一端稱為隊(duì)首。隊(duì)列的特點(diǎn)：先進(jìn)先出（

In

Out,FIFO）。a1

a2

a3

a4

a5入隊(duì)出隊(duì)2015/9/14工業(yè)大學(xué)測繪學(xué)院slide34第3章棧和隊(duì)列3.4

隊(duì)列的邏輯結(jié)構(gòu)（

Cont.）隊(duì)列的抽象數(shù)據(jù)類型ADT

Queue{數(shù)據(jù)對(duì)象：D＝{

ai

|

ai

∈ElemSet,

i=1,2,...,n,

n≥0

}數(shù)據(jù)關(guān)系：R1＝{

<ai-1,ai

>|

ai-1,

ai∈D,

i=2,...,n}約定an端為隊(duì)尾，a1端為隊(duì)首?；静僮鳎骸瓆2015/9/14工業(yè)大學(xué)測繪學(xué)院slide35第3章棧和隊(duì)列3.4

隊(duì)列的邏輯結(jié)構(gòu)（

Cont.）隊(duì)列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,

&e)ClearQueue(&Q)EnQueue(&Q,

e)DeQueue(&Q,

&e)QueueTravers(Q,

visit())2015/9/14工業(yè)大學(xué)測繪學(xué)院slide36第3章棧和隊(duì)列3

.

5

隊(duì)列的

結(jié)構(gòu)—順序隊(duì)列隊(duì)列的順序

結(jié)構(gòu)——順序隊(duì)列：如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序

？0

1

2

3

4a1a2a3a4入隊(duì)出隊(duì)性表尾部rear元素，時(shí)間復(fù)雜度O(1)入隊(duì)：出隊(duì)：性表頭部刪除元素，時(shí)間復(fù)雜度O(N)2015/9/14工業(yè)大學(xué)測繪學(xué)院slide37第3章棧和隊(duì)列3

.

5 隊(duì)列的 結(jié)構(gòu)—順序隊(duì)列（

Cont.）如何改進(jìn)出隊(duì)的時(shí)間性能？所有元素不必

在數(shù)組的前n個(gè)單元，隊(duì)頭不需要一定在下標(biāo)為0的位置。設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)指針，front指針指向隊(duì)頭元素，rear指針指向隊(duì)尾元素的下一位置。0

1

2

3

4

5a1a2a3a4入隊(duì)出隊(duì)front

rear空隊(duì)列時(shí)front=rear，入隊(duì)時(shí)rear加1，出隊(duì)時(shí)front加1，入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度均為O(1)2015/9/14工業(yè)大學(xué)測繪學(xué)院slide38第3章棧和隊(duì)列3.5 隊(duì)列的結(jié)構(gòu)—順序隊(duì)列（

Cont.）如何避免假溢出？0

1

2

3

4

5a3a4a5入隊(duì)出隊(duì)front

rear繼續(xù)入隊(duì)會(huì)出現(xiàn)什么情況？假溢出：當(dāng)元素 入到數(shù)組中下標(biāo)最大的位置上之后，隊(duì)列的空間用盡，但此時(shí)數(shù)組的底端還有空閑空間，這種現(xiàn)象叫做假溢出。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide39第3章棧和隊(duì)列3.5 隊(duì)列的結(jié)構(gòu)—順序隊(duì)列（

Cont.）如何避免假溢出？012345a3a4a5入隊(duì)出rear

front循環(huán)數(shù)組：將數(shù)組最后一個(gè)單元的下一個(gè)單元看成是0號(hào)單元，即把數(shù)組頭尾相接。循環(huán)隊(duì)列：用循環(huán)數(shù)組表示的隊(duì)列。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide40第3章棧和隊(duì)列3

.

5 隊(duì)列的 結(jié)構(gòu)—順序隊(duì)列（

Cont.）如何判斷循環(huán)隊(duì)列隊(duì)空和隊(duì)滿？隊(duì)空時(shí)，front和rear的相對(duì)位置：0

1

2

3

4隊(duì)空：front==rear入隊(duì)出隊(duì)rearfront2015/9/14工業(yè)大學(xué)測繪學(xué)院slide41第3章棧和隊(duì)列3

.

5 隊(duì)列的 結(jié)構(gòu)—順序隊(duì)列（

Cont.）如何判斷循環(huán)隊(duì)列隊(duì)空和隊(duì)滿？隊(duì)滿時(shí)，front和rear的相對(duì)位置：0

1

2

3

4a6a7a3a4a5入隊(duì)出隊(duì)front

rear隊(duì)滿：front==rear2015/9/14工業(yè)大學(xué)測繪學(xué)院slide42第3章棧和隊(duì)列3

.

5 隊(duì)列的 結(jié)構(gòu)—順序隊(duì)列（

Cont.）如何判斷循環(huán)隊(duì)列隊(duì)空和隊(duì)滿？方法一：增設(shè)一個(gè) 隊(duì)列中元素個(gè)數(shù)的計(jì)數(shù)器count

，當(dāng)front==rear且count==0時(shí)，隊(duì)空；當(dāng)front==rear且count==MaxSize時(shí)，隊(duì)滿。方法二：設(shè)置標(biāo)志flag，當(dāng)front==rear且flag==0時(shí)為隊(duì)空；當(dāng)front==rear且flag==1時(shí)為隊(duì)滿。方法三：保留隊(duì)空的判定條件：front==rear；把隊(duì)滿定條件修改為：(rear+1)%MaxSize==front。代價(jià)：浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)數(shù)組中有一個(gè)空閑單元。2015/9/14工業(yè)大學(xué)測繪學(xué)院slide43第3章棧和隊(duì)列3.5 隊(duì)列的結(jié)構(gòu)—順序隊(duì)列（

Cont.）順序隊(duì)列的結(jié)構(gòu)：#defineMAXQSIZE100//最大隊(duì)列長度typedef

struct

{ElemType

*base;

//

動(dòng)態(tài)分配 空間int

front;

//頭指針，若隊(duì)列不空，指向隊(duì)列頭元素intrear;//尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置}S

ueue;2015/9/14工業(yè)大學(xué)測繪學(xué)院slide44第3章棧和隊(duì)列3.5 隊(duì)列的結(jié)構(gòu)—順序隊(duì)列（

Cont.）順序隊(duì)列的初始化操作：Status

InitQueue(Sueue*

pQ,

int

maxsize)

{//

構(gòu)造一個(gè)最大 空間為

maxsize

的空循環(huán)隊(duì)列

QpQ->base=

(ElemType*)malloc(sizeof(ElemType)*maxsize);

if

(!pQ->base)

exit(0);pQ->front

=

pQ->rear

=

0;return

OK;}2015/9/14工業(yè)大學(xué)測繪學(xué)院slide45第3章棧和隊(duì)列3.5 隊(duì)列的結(jié)構(gòu)—順序隊(duì)列（

Cont.）順序隊(duì)列的入隊(duì)操作：Status

EnQueue(Sueue*

pQ,

ElemType

e)

{//

元素e為Q的新的隊(duì)尾元素if

((pQ->rear

+

1)

%

MAXQSIZE

==

pQ->front)return

ERROR;//隊(duì)列滿

pQ->base[pQ->rear]=e;pQ->rear

=

(pQ->rear

+

1)

%

MAXQSIZE;return

OK;}2015/9/14工業(yè)大學(xué)測繪學(xué)院slide46第3章棧和隊(duì)列3.5 隊(duì)列的結(jié)構(gòu)—順序隊(duì)列（

Cont.）順序隊(duì)列的出隊(duì)操作：Status

DeQueue(Sueue*

pQ,

ElemType*

e)

{//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，//

用e返回其值，并返回OK;

否則返回ERRORif

(pQ->front

==

pQ->rear)

return

ERROR;e

=

pQ->base[pQ->front];pQ->front

=

(pQ->front

+

1)

%

MAXQSIZE;return

OK;}2015/9/14工業(yè)大學(xué)測繪學(xué)院slide47第3章棧和隊(duì)列3

.

5

隊(duì)列的

結(jié)構(gòu)—鏈隊(duì)列鏈隊(duì)列：隊(duì)列的鏈?zhǔn)?結(jié)構(gòu)，其本質(zhì)是線性表的單鏈表，但只能尾進(jìn)頭出。如何改造單鏈表實(shí)現(xiàn)隊(duì)列的

？a1a2an∧headfront隊(duì)首指針即為鏈表的頭結(jié)點(diǎn)指針。增加一個(gè)指向隊(duì)尾結(jié)點(diǎn)的指針。rear2015/9/14工業(yè)大學(xué)測繪學(xué)院slide48第3章棧和隊(duì)列3.5

隊(duì)列的結(jié)構(gòu)—鏈隊(duì)列（

Cont.）非空隊(duì)列：空隊(duì)列：a1a2an∧frontrear∧frontrear2015/9/14工業(yè)大學(xué)測繪學(xué)院slide49第3章棧和隊(duì)列3.5

隊(duì)列的結(jié)構(gòu)—鏈隊(duì)列（

Cont.）鏈隊(duì)列的 結(jié)構(gòu)定義：結(jié)點(diǎn)結(jié)構(gòu)typedef

struct

QNode{ElemType

data;struct

QNode*next;}

QNode,

*QueuePtr;front;rear;隊(duì)列結(jié)構(gòu)typedef

struct{QueuePtrQueuePtr}LinkQueue;2015/9/14工業(yè)大學(xué)測繪學(xué)院slide50第3章棧和隊(duì)列3.5

隊(duì)列的結(jié)構(gòu)—鏈隊(duì)列（

Cont.）鏈隊(duì)列的初始化操作：StatusInitQueue(LinkQueue*pQ){//構(gòu)造一個(gè)空隊(duì)列QpQ->front=pQ->rear=(QNode*)malloc(sizeof(QNode));分配失敗if

(!pQ->front)

exit(0);

//pQ->front->next

=

0;return

OK;}2015/9/14工業(yè)大學(xué)測繪學(xué)院slide51第3章棧和隊(duì)列3.5

隊(duì)列的鏈隊(duì)列的入隊(duì)操作：結(jié)構(gòu)—鏈隊(duì)列（

Cont.）Status

EnQueue(LinkQueue

*pQ,

ElemType

e){//

元素e為Q的新的隊(duì)尾元素p

=

(QNode*)malloc(sizeof(QNode));//

分配->data

=

e;pQ->rear->next

=

p;

pQ->rear

=

p;return

OK;}p-1>next

=

0;QNof

(!

exit(0)a;失a敗n∧e∧Q.frontQ.rearp2015/9/14工業(yè)大學(xué)測繪學(xué)院slide52第3章棧和隊(duì)列3

.

5

隊(duì)列的

結(jié)構(gòu)—鏈隊(duì)列（

Cont.）鏈隊(duì)列的出隊(duì)操作：Status

DeQueue(LinkQueue*

pQ,

ElemType*

e)

{//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，//用

e

返回其值，并返回OK；否則返回ERRORif

(pQ->front

==

Q.rear)

returnERROR;QNode*

p

=

pQ->front->next;

*e

=

p->data;

pQ->front->next

=

p->next;if

(pQ->rear

==

p)

pQ->rear

=

pQ