棧和隊列課件

第三章

學時：6學時

3.1棧（Stack）3.2隊列（Queue）

1.定義L定義

2.邏輯結構2.邏輯結構

3.存儲結構3.存儲結構

4.運算規(guī)則4.運算規(guī)則

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

本章主要介紹以下內容：

1、棧的概念、存儲結構及其基本操作

2、隊列的概念、存儲結構及其基本操作

3、棧與隊列的應用舉例

本章重點難點：

1、棧的存儲結構、特點、基本操作算法實現(xiàn)、以

及棧在遞歸算法實現(xiàn)中的應用。

2、隊列存儲結構、特點、基本操作、算法實現(xiàn)

、循環(huán)隊列及其應用。

棧是僅在表尾進行插入、刪除操作的線性表。

表尾（即an端）稱為考頂/top;表頭（即ai端）稱為戈底/base

從棧頂刪除最后一

想一想：要從棧中取出ai,個元素的操作，稱

應當如何操作？出棧。

問題1:堆棧是什么？它與一般線性表有什么不同？

堆棧是一種特殊的線性表，它只能在表的一端（即

棧頂）進行插入和刪除運算。

一般線性表堆棧

邏輯結構：1:1邏輯結構：1:1

存儲結構：順序表、鏈表存儲結構：順序棧、鏈棧

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

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

棧為空的條件：base=top;

棧滿的條件：top-base=stacksize;

問題：什么叫“向上生成”的棧？

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

若入棧動作使地址向高端增長，稱為“向上生成”的棧;

若入棧動作使地址向低端增長，稱為“向下生成”的棧;

對于向上生成的堆棧：

入棧口訣：堆棧指針top“先壓后加”：S[top++]=an+l

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

問題3:為什么要設計堆棧?

它有什么獨特用途?

1.調用函數或子程序非它莫屬；

2.遞歸運算的有力工具；

3.用于保護現(xiàn)場和恢復現(xiàn)場；

4.簡化了程序設計的問題。

下面用3個例子來幫助理解堆棧:

例1.一個棧的輸入序列為1,2,3,若在入棧的過程中允許出

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

答：可以通過窮舉所有可能性來求解:

①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；

合計有5種可能性。

例2：一個棧的輸入序列是12345,若在入棧的過程中允

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

出呢？

答：

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

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

思考：有無通用的判別原則?

例3：設依次進入一個棧的元素序列為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)不行。

討論：有無通用的判別原則?

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

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

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

棧的抽象數據類型定義:

ADTStack{

數據對象：D=

數據關系：R=

入棧、出棧、

基本操作：建棧初始化、

判斷棧滿或棧空、

讀棧頂元素值等。

}ADTStack

順序棧的存儲表示（教材P46）：

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

#defineSTACKINCREMENT10//存儲空間分配增量

typedefstruct{

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

SElemType*top;//棧頂指針

intstacksize;//當前分配的空間

}SqStack;

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

Push(D);

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

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

棧也可以用鏈式結構來表示，用鏈式結構來表示的棧就是鏈棧

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

datanext鏈棧中每個結點由兩個域構成：

data域和next域，其定義為：

typedefStructSNode{

SElemTypedata;

StructSNode*next;

}Node;

Node*st,*p;

intm=sizeof(Node);

(2)操作

鏈棧

入棧

函數

鏈棧

出棧

函數

例3表達式求值(這是棧應用的典型例子)

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

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

一個算術表達式是由

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

算符(*，/,+,(,

(1)表達式求值必須滿足算術四則運算規(guī)則:

a.從左算到右

b.先乘除，后加減

c.先括號內，后括號外

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

OPND—存放操作數或運算結果，OPTR—存放運算符號。

（2）算法思想：

1）首先置操作數棧OPND為空棧，表達式的起始符#為運算

符棧OPTR的棧底元素；

2）依次讀入表達式中的每個字符，

若運算符是‘產或棧頂是結束計算，返回OPND棧頂

值。

if（是操作數）一貝”PUSH（OPND,操作數）；

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

的噌以挪篆達式求值完畢（當前讀入的字符和OPTR

棧的棧頂元素均為#）

表達式求值過程的描述: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）塔問題

移動時的規(guī)則：x

?：?每次只能移動一個盤子；]

只能小盤子在大盤子上面；|

可以使用任一柱子。心

分析：

設三根柱子分別為X,y,Z,盤子在X柱上，要移到Z柱上。

1、當n=l時，盤子直接從x柱移到z柱上；

2、當n>l時,則:

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

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

②再設法把n-1個盤子從y移到z柱上（這又是一個與原來

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

設計如下:

VoidHanoi(intn,charx,chary,charz)

{//將n個編號從上至(下為L.?n的盤子從x柱，借助y柱移到z柱

if(n==1)

move(x,1,z);//將編號為1的盤子從x柱移到z柱

else{//將nT個編號從上到下為1…n-1的盤子從x柱，借助y

柱移到z柱

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

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

//將nT個編號從上到下為l...n-l的盤子從y柱，借助x柱

Hanoi(n-1,y,x9z);

32隊列

隊列的定義限制在一端插入、在另一端刪除的線性表

稱為一個隊列。插入端稱為隊尾，刪除端稱為隊首。

分別用一個“隊頭指針”和一個“隊尾指針”指向隊

首和隊尾。

a2

隊列的順序存儲結構及算法實現(xiàn)

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

隊列，設置兩個指針分別指向隊頭合隊

尾。

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

象而設置的頭尾連接的隊列。

?鏈式隊列：每個元素定義成一個結點，

含兩個域：其中數據域：存放結點數據,

順序隊列:

4-1圖顯示順序表入隊出隊的過程:

從示意圖中可以看到，隨著入隊、出隊操作的進行，

整個隊列會整體向后移動，這樣就出現(xiàn)了圖4-1(d)

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

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

有效的利用。

rear=9

圖4」

Rcdl1

front="l

(a)

(b)

2.循環(huán)隊列

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

動操作，當移動數據較多時將會影響隊列的操

作速度。一個更有效的方法是將隊列的數據區(qū)

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

表示隊首的元素Q［0］與表示隊尾的元素

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

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

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

MAXSIZE-1

front14-2循環(huán)隊

歹U

上圖是假設長度為10的循環(huán)隊列操作示意圖。

因為是頭尾相接的循環(huán)結構，所以將入隊時的隊尾指

針加1操作修改為：

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

將出隊時的隊頭指針加1操作修改為：

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

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

有：@6、a7、a8>@9四個元素；

隨著@『@15相繼入隊，此時front=4,rear=4,隊

列已滿，如(b)所示，可見在隊滿情況下有：

front==rear0

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

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

二rear,也就是說，僅根據等式front二二rear無法有

效判別是“隊滿”還是“隊空