棧和隊(duì)列課件

第三章

學(xué)時(shí)：6學(xué)時(shí)

3.1棧（Stack）3.2隊(duì)列（Queue）

1.定義L定義

2.邏輯結(jié)構(gòu)2.邏輯結(jié)構(gòu)

3.存儲(chǔ)結(jié)構(gòu)3.存儲(chǔ)結(jié)構(gòu)

4.運(yùn)算規(guī)則4.運(yùn)算規(guī)則

5.實(shí)現(xiàn)方式5.實(shí)現(xiàn)方式

本章主要介紹以下內(nèi)容：

1、棧的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作

2、隊(duì)列的概念、存儲(chǔ)結(jié)構(gòu)及其基本操作

3、棧與隊(duì)列的應(yīng)用舉例

本章重點(diǎn)難點(diǎn)：

1、棧的存儲(chǔ)結(jié)構(gòu)、特點(diǎn)、基本操作算法實(shí)現(xiàn)、以

及棧在遞歸算法實(shí)現(xiàn)中的應(yīng)用。

2、隊(duì)列存儲(chǔ)結(jié)構(gòu)、特點(diǎn)、基本操作、算法實(shí)現(xiàn)

、循環(huán)隊(duì)列及其應(yīng)用。

棧是僅在表尾進(jìn)行插入、刪除操作的線(xiàn)性表。

表尾（即an端）稱(chēng)為考頂/top;表頭（即ai端）稱(chēng)為戈底/base

從棧頂刪除最后一

想一想：要從棧中取出ai,個(gè)元素的操作，稱(chēng)

應(yīng)當(dāng)如何操作？出棧。

問(wèn)題1:堆棧是什么？它與一般線(xiàn)性表有什么不同？

堆棧是一種特殊的線(xiàn)性表，它只能在表的一端（即

棧頂）進(jìn)行插入和刪除運(yùn)算。

一般線(xiàn)性表堆棧

邏輯結(jié)構(gòu)：1:1邏輯結(jié)構(gòu)：1:1

存儲(chǔ)結(jié)構(gòu)：順序表、鏈表存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧

“出”=刪除=彈出=POP（a，

棧不存在的條件：base=NULL;

棧為空的條件：base=top;

棧滿(mǎn)的條件：top-base=stacksize;

問(wèn)題：什么叫“向上生成”的棧？

“向下生成”是如何生成的？

若入棧動(dòng)作使地址向高端增長(zhǎng)，稱(chēng)為“向上生成”的棧;

若入棧動(dòng)作使地址向低端增長(zhǎng)，稱(chēng)為“向下生成”的棧;

對(duì)于向上生成的堆棧：

入?？谠E：堆棧指針top“先壓后加”：S[top++]=an+l

出?？谠E：堆棧指針top“先減后彈"：e=S[-top]

問(wèn)題3:為什么要設(shè)計(jì)堆棧?

它有什么獨(dú)特用途?

1.調(diào)用函數(shù)或子程序非它莫屬；

2.遞歸運(yùn)算的有力工具；

3.用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；

4.簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題。

下面用3個(gè)例子來(lái)幫助理解堆棧:

例1.一個(gè)棧的輸入序列為1,2,3,若在入棧的過(guò)程中允許出

棧，則可能得到的出棧序列是什么？

答：可以通過(guò)窮舉所有可能性來(lái)求解:

①1入1出，2入2出，3入3出，即123；

②1入1出，2、3入，3、2出，即132；

③1、2入，2出，3入3出，即231；

④1、2入，2、1出，3入3出，即213；

⑤1、2、3入，3、2、1出,即321；

合計(jì)有5種可能性。

例2：一個(gè)棧的輸入序列是12345,若在入棧的過(guò)程中允

許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸

出呢？

答：

43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn);

12345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即。

思考：有無(wú)通用的判別原則?

例3：設(shè)依次進(jìn)入一個(gè)棧的元素序列為c,a,b,d,

則可得到出棧的元素序列是：

A)a,b,c,dB)c,d,a,b

C)b,ad,aD)a,c,d,b

答：A)、D)可以，B)、C)不行。

討論：有無(wú)通用的判別原則?

有！若輸入序列…，Pj…Pk…Pj…(Pj<Pk<Pj

一定不存在這樣的輸出序列…,P匕叫…Pk…

本節(jié)重點(diǎn)：順序棧和鏈棧的基本操作

棧的抽象數(shù)據(jù)類(lèi)型定義:

ADTStack{

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

數(shù)據(jù)關(guān)系：R=

入棧、出棧、

基本操作：建棧初始化、

判斷棧滿(mǎn)或棧空、

讀棧頂元素值等。

}ADTStack

順序棧的存儲(chǔ)表示（教材P46）：

#defineSTACK-INIT-SIZE/Jo//存儲(chǔ)空間初始分配量

#defineSTACKINCREMENT10//存儲(chǔ)空間分配增量

typedefstruct{

SElemType*base;//棧的基址即棧底指針

SElemType*top;//棧頂指針

intstacksize;//當(dāng)前分配的空間

}SqStack;

順序棧的入棧操作——例如用堆棧存放(A,B,C,D)

Push(D);

順序棧出棧操作——例如從棧中取出B

鏈棧的入棧操作和出棧操作(教材省略)

棧也可以用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示，用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示的棧就是鏈棧

(1)鏈棧的構(gòu)造方式以頭指針為棧頂，在頭指針處插入或刪除

datanext鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：

data域和next域，其定義為：

typedefStructSNode{

SElemTypedata;

StructSNode*next;

}Node;

Node*st,*p;

intm=sizeof(Node);

(2)操作

鏈棧

入棧

函數(shù)

鏈棧

出棧

函數(shù)

例3表達(dá)式求值(這是棧應(yīng)用的典型例子)

這里，表達(dá)式求值的算法是“算符優(yōu)先法”。

例如：編寫(xiě)算法，用棧實(shí)現(xiàn)表達(dá)式3*(7-2)求值。

一個(gè)算術(shù)表達(dá)式是由

操作數(shù)(x,y,z…)和

算符(*，/,+,(,

(1)表達(dá)式求值必須滿(mǎn)足算術(shù)四則運(yùn)算規(guī)則:

a.從左算到右

b.先乘除，后加減

c.先括號(hào)內(nèi)，后括號(hào)外

為了實(shí)現(xiàn)算符優(yōu)先算法，可以設(shè)定兩個(gè)工作棧,

OPND—存放操作數(shù)或運(yùn)算結(jié)果，OPTR—存放運(yùn)算符號(hào)。

（2）算法思想：

1）首先置操作數(shù)棧OPND為空棧，表達(dá)式的起始符#為運(yùn)算

符棧OPTR的棧底元素；

2）依次讀入表達(dá)式中的每個(gè)字符，

若運(yùn)算符是‘產(chǎn)或棧頂是結(jié)束計(jì)算，返回OPND棧頂

值。

if（是操作數(shù)）一貝”P(pán)USH（OPND,操作數(shù)）；

if（是運(yùn)算符）一則與OPTR棧頂元素進(jìn)行比較，按優(yōu)

的噌以挪篆達(dá)式求值完畢（當(dāng)前讀入的字符和OPTR

棧的棧頂元素均為#）

表達(dá)式求值過(guò)程的描述:3*(7-2)

OPTROPNDINPUTOPERATE

#3*(7?2)#Push(opnd,,3,)

#3*(7-2)#Push(optr,'*')

禮*3(7-2)#Push(optr,'(')

37-2)#Push(opnd,,7,)

3,7-2)#Push(optr,'-')

#,*,(「3,72)#Push(opnd,,2,)

#,*,(「3,7,2)#Operate(7-2)

#,*,(3,5)#Pop(optr)

禮*3,5#Operate?*5)

#15#GetTop(opnd)

例4漢諾（Hanoi）塔問(wèn)題

移動(dòng)時(shí)的規(guī)則：x

?：?每次只能移動(dòng)一個(gè)盤(pán)子；]

只能小盤(pán)子在大盤(pán)子上面；|

可以使用任一柱子。心

分析：

設(shè)三根柱子分別為X,y,Z,盤(pán)子在X柱上，要移到Z柱上。

1、當(dāng)n=l時(shí)，盤(pán)子直接從x柱移到z柱上；

2、當(dāng)n>l時(shí),則:

①設(shè)法將前n-1個(gè)盤(pán)子從x移到y(tǒng)柱上（借助z）,則盤(pán)

子n就能從x移到z柱上；

②再設(shè)法把n-1個(gè)盤(pán)子從y移到z柱上（這又是一個(gè)與原來(lái)

相同的問(wèn)題，只是規(guī)模少1了）。

設(shè)計(jì)如下:

VoidHanoi(intn,charx,chary,charz)

{//將n個(gè)編號(hào)從上至(下為L(zhǎng).?n的盤(pán)子從x柱，借助y柱移到z柱

if(n==1)

move(x,1,z);//將編號(hào)為1的盤(pán)子從x柱移到z柱

else{//將nT個(gè)編號(hào)從上到下為1…n-1的盤(pán)子從x柱，借助y

柱移到z柱

Hanoi(n-1,x,z,y);

move(x,n,z);//修編號(hào)為11的盤(pán)子從*柱移到2柱

//將nT個(gè)編號(hào)從上到下為l...n-l的盤(pán)子從y柱，借助x柱

Hanoi(n-1,y,x9z);

32隊(duì)列

隊(duì)列的定義限制在一端插入、在另一端刪除的線(xiàn)性表

稱(chēng)為一個(gè)隊(duì)列。插入端稱(chēng)為隊(duì)尾，刪除端稱(chēng)為隊(duì)首。

分別用一個(gè)“隊(duì)頭指針”和一個(gè)“隊(duì)尾指針”指向隊(duì)

首和隊(duì)尾。

a2

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)

?順序隊(duì)列：用連續(xù)的空間區(qū)域存放一個(gè)

隊(duì)列，設(shè)置兩個(gè)指針?lè)謩e指向隊(duì)頭合隊(duì)

尾。

■循環(huán)隊(duì)列：為解決順序隊(duì)列中的溢出現(xiàn)

象而設(shè)置的頭尾連接的隊(duì)列。

?鏈?zhǔn)疥?duì)列：每個(gè)元素定義成一個(gè)結(jié)點(diǎn)，

含兩個(gè)域：其中數(shù)據(jù)域：存放結(jié)點(diǎn)數(shù)據(jù),

順序隊(duì)列:

4-1圖顯示順序表入隊(duì)出隊(duì)的過(guò)程:

從示意圖中可以看到，隨著入隊(duì)、出隊(duì)操作的進(jìn)行，

整個(gè)隊(duì)列會(huì)整體向后移動(dòng)，這樣就出現(xiàn)了圖4-1(d)

中的現(xiàn)象：隊(duì)尾指針雖然已經(jīng)移到了最后，而隊(duì)列卻

未真滿(mǎn)的“假溢出”現(xiàn)象，使得隊(duì)列的空間沒(méi)有得到

有效的利用。

rear=9

圖4」

Rcdl1

front="l

(a)

(b)

2.循環(huán)隊(duì)列

為了解決上述隊(duì)列的“假溢出”現(xiàn)象，要做移

動(dòng)操作，當(dāng)移動(dòng)數(shù)據(jù)較多時(shí)將會(huì)影響隊(duì)列的操

作速度。一個(gè)更有效的方法是將隊(duì)列的數(shù)據(jù)區(qū)

Q：0?.MAXLEN-1］看成是首尾相連的環(huán)，即將

表示隊(duì)首的元素Q［0］與表示隊(duì)尾的元素

Q［MAXLEN-L］連接起來(lái)，形成一個(gè)環(huán)形表，這

就成了循環(huán)隊(duì)列，如圖（4-2）所示。

循環(huán)隊(duì)列示意圖

MAXSIZE-1

front14-2循環(huán)隊(duì)

歹U

上圖是假設(shè)長(zhǎng)度為10的循環(huán)隊(duì)列操作示意圖。

因?yàn)槭穷^尾相接的循環(huán)結(jié)構(gòu)，所以將入隊(duì)時(shí)的隊(duì)尾指

針加1操作修改為：

p->rear=(p->rear+l)%MAXLEN；

將出隊(duì)時(shí)的隊(duì)頭指針加1操作修改為：

p->front=(p->front+l)%MAXLEN；

在圖4-4(a)中，此時(shí)front=4,rear=8,隊(duì)列中具

有：@6、a7、a8>@9四個(gè)元素；

隨著@『@15相繼入隊(duì)，此時(shí)front=4,rear=4,隊(duì)

列已滿(mǎn)，如(b)所示，可見(jiàn)在隊(duì)滿(mǎn)情況下有：

front==rear0

若在(a)的情況下，@6?ag相繼出隊(duì)，此時(shí)隊(duì)空，

front=8,rear=8,如(c)所示，也有：front二

二rear,也就是說(shuō)，僅根據(jù)等式front二二rear無(wú)法有

效判別是“隊(duì)滿(mǎn)”還是“隊(duì)空