數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 第4章

第4章棧和隊列

一、復(fù)習(xí)要點(diǎn)

本章主要討論3種線性結(jié)構(gòu)：棧、隊列與優(yōu)先級隊列。這3種結(jié)構(gòu)都是順序存取的表，

而且都是限制存取點(diǎn)的表。棧限定只能在表的一端（棧頂）插入與刪除，其特點(diǎn)是先進(jìn)后出。

隊列和優(yōu)先級隊列限定只能在表的一端（隊尾）插入在另一端（隊頭）刪除，不過優(yōu)先級隊

列在插入和刪除時需要根據(jù)數(shù)據(jù)對象的優(yōu)先級做適當(dāng)?shù)恼{(diào)整，令優(yōu)先級最高的對象調(diào)整到隊

頭，其特點(diǎn)是優(yōu)先級高的先出。而隊列不調(diào)整，其特點(diǎn)是先進(jìn)先出。這幾種結(jié)構(gòu)在開發(fā)各種

軟件時非常有用。

本章復(fù)習(xí)的要點(diǎn)：

1、基本知識點(diǎn)

要求理解棧的定義和特點(diǎn)，棧的抽象數(shù)據(jù)類型和在遞歸和表達(dá)式計算中的使用，在棧式

鐵路調(diào)車線上當(dāng)進(jìn)棧序列為1,2,3,…,n時，可能的出棧序列計數(shù)，棧的順序存儲表示和鏈

接存儲表示，特別要注意，鏈?zhǔn)綏５臈ｍ攽?yīng)在鏈頭，插入與刪除都在鏈頭進(jìn)行。另外，需要

理解隊列的定義和特點(diǎn)，隊列的抽象數(shù)據(jù)類型和在分層處理中的使用，隊列的順序存儲表示

（循環(huán)隊列）和鏈接存儲表示，需要注意的是，鏈?zhǔn)疥犃械年狀^應(yīng)在鏈頭，隊尾應(yīng)在鏈尾。

還需要理解優(yōu)先級隊列的定義和特點(diǎn)。優(yōu)先級隊列的最佳存儲表示是堆（heap）,本章介紹

的表示看懂即可。

2、算法設(shè)計

＞棧的5種操作（進(jìn)棧、退棧、取棧頂元素、判?？?、置空棧）的在順序存儲表示下

的實現(xiàn)，以及在鏈接存儲表示下的實現(xiàn)。

＞使用棧的后綴表達(dá)式計算算法

＞循環(huán)隊列的進(jìn)隊列、出隊列、取隊頭元素、判隊列空、置空隊列操作的實現(xiàn)

＞鏈?zhǔn)疥犃械倪M(jìn)隊列、出隊列、取隊頭元素、判隊列空、置空隊列操作的實現(xiàn)

二、難點(diǎn)和重點(diǎn)

1、棧：棧的特性、棧的基本運(yùn)算

＞棧的數(shù)組實現(xiàn)、棧的鏈表實現(xiàn)

＞棧滿及?？諚l件、抽象數(shù)據(jù)類型中的先決條件與后置條件

2、棧的應(yīng)用：用后綴表示計算表達(dá)式，中綴表示改后綴表示

3、隊列：隊列的特性、隊列的基本運(yùn)算

＞隊列的數(shù)組實現(xiàn)：循環(huán)隊列中隊頭與隊尾指針的表示，隊滿及隊空條件

＞隊列的鏈表實現(xiàn)：鏈?zhǔn)疥犃兄械年狀^與隊尾指針的表示、

三、習(xí)題的解析

4-2鐵路進(jìn)行列車調(diào)度時，常把站臺設(shè)計成棧式結(jié)構(gòu)的站臺，

如右圖所示。試問：

（1）設(shè)有編號為123,4,5,6的六輛列車，順序開入棧式結(jié)構(gòu)

的站臺，則可能的出棧序列有多少種？

（2）若進(jìn)站的六輛列車順序如上所述，那么是否能夠得到

435612,325641,154623和135426的出站序列，如果不能，說明為什么不能；如果能，說明如

何得到(即寫出"進(jìn)棧"或"出?！钡男蛄?。

【解答】

⑴可能的不同出棧序列有(l/(6+D)*G,=132種。

(2)不能得到435612和154623這樣的出棧序列。因為若在4,3,5,6之后再將1,2出棧,

則1,2必須一直在棧中，此時1先進(jìn)棧，2后進(jìn)棧，2應(yīng)壓在1上面，不可能1先于2出棧。

154623也是這種情況。出棧序列325641和135426可以得到。

4-5寫出下列中綴表達(dá)式的后綴形式：

⑴A*B*C

(2)-A+B-C+D

(3)A*-B+C

(4)(A+B)*D+E/(F+A*D)+C

【解答】

(1)AB*C*

(2)A-B+C-D+

(3)AB-*C+

(4)AB+D*EFAD*+/+C+

4-7設(shè)表達(dá)式的中綴表示為a*x-b/xt2,試?yán)脳⑺臑楹缶Y表示ax*bx2t/~寫

出轉(zhuǎn)換過程中棧的變化。

【解答】

若設(shè)當(dāng)前掃描到的運(yùn)算符ch的優(yōu)先級為icp(ch),該運(yùn)算符進(jìn)棧后的優(yōu)先級為isp(ch),

則可規(guī)定各個算術(shù)運(yùn)算符的優(yōu)先級如下表所示。

運(yùn)算符(A*,/,%+,一)

isp017538

icp086421

isp也叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)，icp也叫做棧外(incomingpriority)優(yōu)先數(shù)。當(dāng)

剛掃描到的運(yùn)算符ch的icp(ch)大于isp(stack)時，則ch進(jìn)棧；當(dāng)剛掃描到的運(yùn)算符ch的

icp(ch)小于isp(stack)時，則位于棧頂?shù)倪\(yùn)算符退棧并輸出。從表中可知，icp(“(”)最高，

但當(dāng)“("進(jìn)棧后，isp(“(")變得極低。其它運(yùn)算符進(jìn)入棧中后優(yōu)先數(shù)都升1,這樣可體現(xiàn)在

中綴表達(dá)式中相同優(yōu)先級的運(yùn)算符自左向右計算的要求。運(yùn)算符優(yōu)先數(shù)相等的情況只出現(xiàn)在

括號配對“)”或棧底的“；”號與輸入流最后的號配對時。前者將連續(xù)退出位于棧頂

的運(yùn)算符，直到遇到“(”為止。然后將“(”退棧以對消括號，后者將結(jié)束算法。

步序掃描項項類型動作棧的變化輸出

0b'；'進(jìn)棧，讀下一符號

1a操作數(shù)的直接輸出，讀下一符號A

2*操作符「isp(';')<icp(，*'),進(jìn)棧，讀下一符號?*A

3X操作數(shù)▽直接輸出，讀下一符號?*ax

4-操作符?-isp('*')>icp('-'),退棧輸出ax*

isp(';1)<icp('-'),進(jìn)棧,讀下一符號ax*

5b操作數(shù)b直接輸出，讀下一符號ax*b

6/操作符bisp('-1)<icp(7),進(jìn)棧，讀下一符號;-/ax*b

7X操作數(shù)b直接輸出，讀下一符號;-/ax*bx

8t操作符bisp("1)<icp('t*),進(jìn)棧，讀下一符號;-/tax*bx

92操作數(shù)b直接輸出，讀下一符號;-/tax*bx2

退棧輸出

109操作符?-isp('t')>icp(';'),;-/ax*bx2t

isp(7')>icp(';'),退棧輸出ax*bx2t/

isp('~1)>icp(';*),退棧輸出ax*bx2t/

衣結(jié)束

4-9假設(shè)以數(shù)組Q[m]存放循環(huán)隊列中的元素，同時以rear和length分別指示循環(huán)隊列中的

隊尾位置和隊列中所含元素的個數(shù)。試給出該循環(huán)隊列的隊空條件和隊滿條件，并寫出相應(yīng)

的插入(enqueue)和刪除(dlqueue)元素的操作。

【解答】

循環(huán)隊列類定義

#include<assert.h>

template<classType>classQueue{〃循環(huán)隊列的類定義

public:

Queue(int=IO);

-Queue(){delete[]elements;}

voidEnQueue(Type&item);

TypeDeQueue();

TypeGetFront();

voidMakeEmpty(){length=0;}〃置空隊列

intIsEmpty()const{returnlength==0;}〃判隊列空否

intIsFull()const{returnlength==maxSize;}〃判隊列滿否

private:

intrear,length;〃隊尾指針和隊列長度

l\pe*elements;〃存放隊列元素的數(shù)組

intmaxSize;〃隊列最大可容納元素個數(shù)

}

template<classType>Queue<Type>::Queue(intsz):rear(maxSize-1),length(0),maxSize(sz){

〃構(gòu)造函數(shù)：建立一個最大具有maxSize個元素的空隊列。

elements=newType|maxSize];〃創(chuàng)建隊列空間

assert(elements!=0);〃斷言：動態(tài)存儲分配成功與否

)

template<classType>voidQueue<Type>::EnQueue(Type&item){

〃插入函數(shù)

assert(!IsFull());〃判隊列是否不滿，滿則出錯處理

length++;〃長度加1

rear=(rear+1)%maxSize;〃隊尾位置進(jìn)1

elemcnts[rear]=item;〃進(jìn)隊列

template<classType>TypeQueue<Type>::DeQueue(){

〃刪除函數(shù)

assert(!IsEmpty());〃判斷隊列是否不空，空則出錯處理

length—;〃隊列長度減1

returnelementsl(rear-lenglh+maxSize)%maxSize];〃返回原隊頭元素值

template<classType>TypeQueue<T5,pe>::GetFront(){

〃讀取隊頭元素值函數(shù)

assert(!IsEmpty());

returnelements[(rear-length+1+maxSize)%maxSize];〃返回隊頭元素值

4-11若使用循環(huán)鏈表來表示隊列，p是鏈表中的一個指針。試基于此結(jié)構(gòu)給出隊列的插入

(enqueue)和刪除(dequeue)算法，并給出p為何值時隊列空。

【解答】

鏈?zhǔn)疥犃械念惗x

template<classType>classQueue;〃鏈?zhǔn)疥犃蓄惖那耙暥x

template<classType>classQueueNode{〃鏈?zhǔn)疥犃薪Y(jié)點(diǎn)類定義

friendclassQueue<riype>;

private:

Typedata;〃數(shù)據(jù)域

QueueNode<l^pe>：i：link;〃鏈域

public:

QueueNode(Typed=0,QueueNode*1=NULL):data(d),link(1){}〃構(gòu)造函數(shù)

template<classT^pe>classQueue{〃鏈?zhǔn)疥犃蓄惗x

public:

Queue():p(NULL){}〃構(gòu)造函數(shù)

-Queue();〃析構(gòu)函數(shù)

voidEnQueue(constI\pe&item);〃將item加入到隊列中

TypeDeQueue();〃刪除并返回隊頭元素

TypeGetFront();〃查看隊頭元素的值

voidMakeEmpty();〃置空隊列，實現(xiàn)與-Queue()相同

intIsEmpty()const{returnp==NULL;}〃判隊列空否

private:

QueueNode<lype>*p;〃隊尾指針(在循環(huán)鏈表中)

)；

template<classType>Queue<Tj7pe>::-Queue(){

〃隊列的析構(gòu)函數(shù)

QueueNode<Type>*s;

while(p!=NULL){s=p;p=p->link;deletes;}〃逐個刪除隊列中的結(jié)點(diǎn)

}

template<classType>voidQueue<Type>::EnQueue(constType&item){

〃隊列的插入函數(shù)

if(p==NULL){〃隊列空，新結(jié)點(diǎn)成為第一個結(jié)點(diǎn)

p=newQueueNode<Type>(item,NULL);p->link=p;

)

else{〃隊列不空，新結(jié)點(diǎn)鏈入p之后

QueueNode<Type>*s=newQueueNode<Type>(item,NULL);

s->link=p->link;p=p->link=s;〃結(jié)點(diǎn)p指向新的隊尾

)

)

隊列的刪除函數(shù)

template〈classT^pe>TypeQueue<Type>::DeQueue(){

〃隊列的插入函數(shù)

if(p==NULL){cout?”隊列空,不能刪除!"?endl;return0;}

QueueNode<Type>*s=p;〃隊頭結(jié)點(diǎn)為p后一個結(jié)點(diǎn)

p->link=s->link;〃重新鏈接，將結(jié)點(diǎn)s從鏈中摘下

Typeretvalue=s->data;deletes;〃保存原隊頭結(jié)點(diǎn)中的值，釋放原隊頭結(jié)點(diǎn)

returnretvalue;〃返回數(shù)據(jù)存放地址

}

隊空條件p==NULL

四、其他練習(xí)題

4-16單選題

(1)棧的插入和刪除操作在進(jìn)行。

A棧頂B棧底C任意位置D指定位置

(2)當(dāng)利用大小為n的數(shù)組順序存儲一個棧時，假定用top==n表示?？?，則向這個棧

插入一個元素時，首先應(yīng)執(zhí)行語句修改top指針。

Atop++;Btop—;Ctop=0;Dtop;

(3)若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能出現(xiàn)種情況。

A3,2,1B2,1,3C3,1,2D1,3,2

(4)在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的________位置。

A前一個B后一個C當(dāng)前D后面

(5)當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為。

An-2Bn-1CnDn+1

(6)從一個順序存儲的循環(huán)隊列中刪除一個元素時，首先需要o

A隊頭指針加一B隊頭指針減一

C取出隊頭指針?biāo)傅脑谼取出隊尾指針?biāo)傅脑?/p>

(7)假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f和r,則判斷隊空的條件為

Af+l==rBr+l==fCf==ODf==r

(8)假定一個鏈?zhǔn)疥犃械年狀^和隊尾指針分別為front和rear,則判斷隊空的條件為

Afront==rearBfront!=NULLCrear!=NULLDfront==NULL

【解答】

(1)A(2)B(3)C(4)A(5)B(6)B

(7)D(8)D

4-17填空題

(1)隊列的插入操作在_______進(jìn)行，刪除操作在_________進(jìn)行。

(2)棧又稱為的表，隊列又稱為的表。

(3)向一個順序棧插入一個元素時，首先使后移一個位置，然后把待插入元素

到這個位置上。

(4)從一個棧刪除元素時，需要前移一位。

(5)在一個循環(huán)隊列Q中，判斷隊空的條件為,判斷隊滿的條件為o

(6)在一個順序棧中，若棧頂指針等于，則為空棧；若棧頂指針等于,

則為滿棧。

(7)在一個鏈?zhǔn)綏Ｖ?，若棧頂指針等于NULL則為；在一個鏈?zhǔn)疥犃兄?，若?/p>

頭指針與隊尾指針的值相同，則表示該隊列為或該隊列o

(8)向一個鏈?zhǔn)綏２迦胍粋€新結(jié)點(diǎn)時，首先把棧頂指針的值賦給,然后把新結(jié)

點(diǎn)的存儲位置賦給。

(9)向一個循環(huán)隊列中插入元素時，需要首先移動,然后再向所指位置

新插入的元素。

(10)當(dāng)用長度為n的數(shù)組順序存儲一個棧時，若用top==n表示?？?，則表示棧滿的

條件為。

(11)向一個棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€新結(jié)點(diǎn)*p時，應(yīng)執(zhí)行和

________操作。

(12)從一個棧頂指針為top的非空鏈?zhǔn)綏Ｖ袆h除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回

收結(jié)點(diǎn)時，應(yīng)執(zhí)行操作。

(13)假定front和rear分別為一個鏈?zhǔn)疥犃械年狀^和隊尾指針，則該鏈?zhǔn)疥犃兄兄挥幸?/p>

個結(jié)點(diǎn)的條件為。

(14)中綴表達(dá)式3*(x+2)-5所對應(yīng)的后綴表達(dá)式為。

(15)后綴表達(dá)式“45*32+-”的值為。

【解答】

(1)隊尾，隊頭

(2)后進(jìn)先出，先進(jìn)先出

(3)棧頂指針，寫入

(4)棧頂指針

(5)Q.front==Q.rear,(Q.rear+1)%MaxSize+1==Q.front

(6)-1,MaxSize-1

(7)空棧，空，只含有一個結(jié)點(diǎn)

(8)新結(jié)點(diǎn)的指針域，棧頂指針

(9)隊尾指針，寫入

(10)top==0

(11)p->link=top,top=p

(12)top=top->link

(13)front==rear&&front!=NULL或者front==rear&&rear!=NULL

(14)3x2+*5-

(15)15

4-18設(shè)有一個順序棧S,元素51/2評3,54叫5,56依次進(jìn)棧,如果6個元素的出棧順序為S2,S3,

S4,S6,S5,S1,則順序棧的容量至少應(yīng)為多少？

【解答】

3

4-19設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為(data,link),且top是指向棧頂?shù)闹羔?。若想在鏈?zhǔn)綏５臈?/p>

頂插入一個由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列哪一個操作？

(1)top->link=s;(2)s->link=top->link;top->link=s;

(3)s->link=top;top=s;(4)s->link=top;top=top->link;

【解答】

(3)

4-20設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為(data,link),且top是指向棧頂?shù)闹羔?。若想摘除鏈?zhǔn)綏５?/p>

棧頂結(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行下列哪一個操作？

(1)x=top->data;top=top->link;(2)top=top->link;x=top->data;

(3)x=top;top=top->link;(4)x=top->data;

【解答】

(1)

4-21設(shè)循環(huán)隊列的結(jié)構(gòu)是

constintMaxSize=100;

typedefintDataTypc;

typedefstruct{

DataTypedata[MaxSize];

intfront,rear;

}Queue;

若有一個Queue類型的隊列Q,試問判斷隊列滿的條件應(yīng)是下列哪一個語句？

(1)Q.front==Q.rear;(2)Q.front-Q.rear==MaxSize;

(3)Q.front+Q.rear==MaxSize;(4)Q.front==(Q.rear+1)%MaxSize;

【解答】

(4)

4-22設(shè)循環(huán)隊列的結(jié)構(gòu)如4-21。若有一個Queue類型的隊列Q,試問應(yīng)用下列哪一個語句

計算隊列元素個數(shù)？

(1)(Q.rear-Q.front+MaxSize)%MaxSize;(2)Q.rear-Q.front+1;

(3)Q.rear-Q.front-1;(4)Q.rear-Qfront;

【解答】

(1)

4-23假設(shè)以數(shù)組Qfm]存放循環(huán)隊列中的元素，同時以rear和length分別指示循環(huán)隊列中的

隊尾位置和隊列中所含元素的個數(shù)。試給出該循環(huán)隊列的隊空條件和隊滿條件，并寫出相應(yīng)

的插入(EnQueue)和刪除(DiQueue)元素的操作。

【解答】

隊空：length==0隊滿：length==Maxsize

4-24所謂回文，是指從前向后順讀和從后向前倒讀都一樣的不含空白字符的串。例如did,

madamimadam,pop即是回文。試編寫一個算法，以判斷一個串是否是回文。

【解答1】

將字符串中全部字符進(jìn)棧，然后將棧中的字符逐個與原字符串中的字符進(jìn)行比較。算法

如下：

intpalindrome(charA[],intn){

stack<char>st(n+1);

intyes=1,i=0;

while(A[i]!='*\0"){st.Push(A[iJ);i++;)〃掃描字符串，所有字符進(jìn)棧

i=0;

while(A[i]!="\0")〃比較字符串

if(A[i]==st.GetTop()){st.Pop();i++;}

else{yes=0;break;)

returnyes;

}

【解答2】

采用遞歸算法，判斷從s到e中的字符串是否回文，通過函數(shù)返回是或不是。

intpalindrome(charA|],ints,inte){

if(A[s]!=A[e])return0;

elseif(s>e)return1;

elsepalindrome(A,s+1,e-l);

)

4-25借助棧實現(xiàn)單鏈表上的逆置運(yùn)算。

【解答】由于進(jìn)棧與出棧順序正好相反，因此，借助?？梢詫崿F(xiàn)單鏈表的逆置運(yùn)算。方法是

讓單鏈表中的結(jié)點(diǎn)依次進(jìn)棧，再依次出棧。

#include"stack.h*'

#include"LinkList.h"

template<classType>voidinvert(LinkList<Type>L){

Stack<ListNode<Type>*>S;

ListNodc<iype>*p=L.First(),*q;

while(p!=NULL){S.Push(p);p=p.Next();}〃依次將鏈中結(jié)點(diǎn)進(jìn)棧

p=L.Firster();p->setLink(NULL);〃單鏈表表頭結(jié)點(diǎn)鏈指針置空

while(!S.IsEmpty()){〃將棧中保存的結(jié)點(diǎn)依次出棧

q=S.GetTop();S.Pop();

q->SetLink(p->getLink());〃鏈入逆置后的鏈中

p->setLink(q);

p=p->getLink();

)

4-27試編寫一個算法，檢查一個程序中的花括號、方括號和圓括號是否配對，若能夠全部

配對則返回1,否則返回0。

【解答】在算法中，掃描程序中的每一個字符，當(dāng)掃描到每個花、中、圓左括號時，令其進(jìn)

棧，當(dāng)掃描到花、中、圓右括號時，則檢查棧頂是否