3棧與隊(duì)列3.1棧基礎(chǔ)3.2STL之stack3.3棧應(yīng)用舉例3.4隊(duì)列基礎(chǔ)3.5STL之queue3.6隊(duì)列應(yīng)用舉例3.7在線題目求解學(xué)習(xí)目標(biāo)1.記憶和理解棧和隊(duì)列的基礎(chǔ)知識(shí)。2.掌握順序棧、鏈?zhǔn)綏?、循環(huán)隊(duì)列、鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)。3.學(xué)會(huì)運(yùn)用棧和隊(duì)列求解具體問(wèn)題。4.學(xué)會(huì)運(yùn)用STL之stack、queue求解具體問(wèn)題。3棧與隊(duì)列3.1?；A(chǔ)概述棧是插入、刪除操作都只能在表尾（棧頂）進(jìn)行的線性表。在棧中，表尾元素稱(chēng)為棧頂元素。在棧中插入元素稱(chēng)為入棧，而在棧中刪除元素稱(chēng)為出棧。除了入棧和出棧操作，棧的常見(jiàn)操作還包括初始化棧、判斷棧空、判斷棧滿、取棧頂元素等。進(jìn)棧序列為(1,2,3,4)，當(dāng)棧非空即可出棧，則以下選項(xiàng)中不可能的出棧序列為（）

A.1234B.4213C.3421D.21433.1?；A(chǔ)順序棧基礎(chǔ)順序棧是采用順序存儲(chǔ)結(jié)構(gòu)的棧，即用一維數(shù)組存儲(chǔ)數(shù)據(jù)元素。對(duì)于非空棧，把棧頂元素（表尾元素）的下標(biāo)稱(chēng)為棧頂指針，其初值設(shè)為-1。容量為5的順序棧示意圖如下，其中top為棧頂指針，當(dāng)棧非空時(shí)指向棧頂元素。3.1?；A(chǔ)順序棧的實(shí)現(xiàn)#include<iostream>usingnamespacestd;constintN=100;//存儲(chǔ)空間的最大可能分配量typedefintElemType;//為int取別名ElemTypestructSqStack{

ElemType*base;//順序棧的首地址，動(dòng)態(tài)數(shù)組的首地址

inttop;//棧頂指針，棧非空時(shí)，為棧頂元素的下標(biāo)(從0開(kāi)始)

voidInit();

//初始化棧

voidClear();

//清空棧

ElemTypeGetTop();

//取棧頂元素

voidPush(ElemTypee);

//入棧

voidPop();

//出棧

boolEmpty();

//判斷空棧};3.1?；A(chǔ)順序棧的實(shí)現(xiàn)voidSqStack::Init(){

//初始化棧，即構(gòu)造一個(gè)空棧

base=newElemType[N];

//創(chuàng)建動(dòng)態(tài)數(shù)組，數(shù)組名base

top=-1;

//置棧頂指針初值為-1}voidSqStack::Push(ElemTypee){//元素e入棧

if(top==N-1)return;

//若棧滿，則返回

top++;

//棧頂指針加1

base[top]=e;

//把e存放到棧頂指針?biāo)傅拇鎯?chǔ)單元}voidSqStack::Pop(){

//出棧

if(top==-1)return;

//若?？?，則返回

top--;

//棧頂指針減1}3.1?；A(chǔ)順序棧的實(shí)現(xiàn)voidSqStack::Clear(){

//清空棧

delete[]base;

//釋放?？臻g

top=-1;

//棧頂指針重置為初值1}boolSqStack::Empty(){

//判斷棧空

returntop==-1;

//若?？談t返回true，否則返回false}ElemTypeSqStack::GetTop(){

//取棧頂元素

returnbase[top];

//返回棧頂指針?biāo)冈貆3.1?；A(chǔ)順序棧的實(shí)現(xiàn)intmain(){

intn;SqStackst;//定義棧st.Init();//初始化棧cin>>n;for(inti=0;i<n;i++){ElemTypet;

cin>>t;

st.Push(t);

//入棧

}

3.1?；A(chǔ)順序棧的實(shí)現(xiàn)

//遍歷棧，當(dāng)棧非空時(shí)不斷取棧頂元素輸出后再出棧

while(st.Empty()==false){

//當(dāng)棧非空時(shí)循環(huán)

intt=st.GetTop();

//取棧頂元素

cout<<t<<endl;

//輸出棧頂元素

st.Pop();

//出棧

}

cout<<endl;

st.Clear();

//清空棧

return0;}在使用自定義棧時(shí)需先用成員函數(shù)Init初始化棧用成員函數(shù)GetTop取棧頂元素之前應(yīng)先判斷棧非空3.1?；A(chǔ)鏈棧基礎(chǔ)鏈棧實(shí)際上是插入、刪除都限定在棧頂?shù)逆湵?。若用帶頭結(jié)點(diǎn)的單鏈表（設(shè)指針域?yàn)閚ext）來(lái)表示鏈棧，則棧頂指針指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)（對(duì)應(yīng)棧頂元素）。鏈棧示意圖3.1?；A(chǔ)鏈棧的實(shí)現(xiàn)typedefintElemType;structLNode{

//

結(jié)點(diǎn)類(lèi)型

ElemTypedata;

//

數(shù)據(jù)域

LNode*next;

//

指針域};structLinkStack{

//

鏈棧結(jié)構(gòu)體類(lèi)型

LNode*head;

//

頭指針

voidInit();

//

初始化鏈棧

voidClear();

//

清空鏈棧

voidPush(ElemTypee);

//

入棧

voidPop();

//

出棧

ElemTypeGetTop();

//

取棧頂元素

boolEmpty();

//

判斷空表};3.1?；A(chǔ)鏈棧的實(shí)現(xiàn)voidLinkStack::Init(){

//

初始化棧

head=newLNode;

//

創(chuàng)建頭結(jié)點(diǎn)

head->next=NULL;

//

頭結(jié)點(diǎn)指針域置為空指針

}voidLinkStack::Clear(){

//

清空棧

while(head->next){

//

若還存在數(shù)據(jù)結(jié)點(diǎn)，則刪除

LNode*p=head->next;

//

p指向棧頂元素

head->next=p->next;

//

刪除棧頂元素

deletep;

//

釋放棧頂元素結(jié)點(diǎn)空間

}}3.1?；A(chǔ)鏈棧的實(shí)現(xiàn)voidLinkStack::Push(ElemTypee){

//

入棧

LNode*q=newLNode;

//

創(chuàng)建新結(jié)點(diǎn)

q->data=e;

q->next=head->next;

//

新結(jié)點(diǎn)鏈接到第一個(gè)數(shù)據(jù)結(jié)點(diǎn)之前

head->next=q;

//

新結(jié)點(diǎn)鏈接到頭結(jié)點(diǎn)之后

}voidLinkStack::Pop(){

//

出棧

if(head->next==NULL)return;

//

若是空棧，則返回

LNode*q=head->next;

//

q指向棧頂元素

head->next=q->next;

//

刪除棧頂元素

deleteq;

//

釋放棧頂元素空間

}3.1?；A(chǔ)鏈棧的實(shí)現(xiàn)ElemTypeLinkStack::GetTop(){

//

取棧頂元素

returnhead->next->data;

//

返回棧頂元素

}boolLinkStack::Empty(){

//

判斷?？?/p>

returnhead->next==NULL;//

若為空鏈表則返回true，否則返回false}#include<iostream>usingnamespacestd;intmain(){

intn;

LinkStackst;

//

定義棧

st.Init();

//

初始化棧

cin>>n;

3.1?；A(chǔ)鏈棧的實(shí)現(xiàn)

for(inti=0;i<n;i++){

intt;

cin>>t;

st.Push(t);

//

入棧

}

//

遍歷棧

while(st.Empty()==false){

//

當(dāng)棧非空則取棧頂元素輸出并出棧

intt=st.GetTop();

//

取棧頂元素

cout<<t<<endl;

//

輸出棧頂元素

st.Pop();

//

出棧

}

cout<<endl;

st.Clear();

//

清空棧

return0;}3.2STL之stack基礎(chǔ)知識(shí)STL之stack實(shí)現(xiàn)棧的功能。使用stack需包含頭文件stack。通過(guò)實(shí)例化方法定義棧，例如：stack<int>S;//定義棧S，每個(gè)元素為int類(lèi)型其常用操作包括如表3-1所示：3.2STL之stackSTL之stack的基本用法#include<iostream>#include<stack>usingnamespacestd;intmain(){

stack<int>s;

//定義棧

for(intk=0;k<5;k++){

s.push(k+1);

//入棧

}

cout<<s.size()<<endl;

//棧大小

while(s.empty()==false){//遍歷棧，棧非空時(shí)重復(fù)執(zhí)行

intt=s.top();

//取棧頂元素

cout<<t<<endl;

s.pop();//出棧}

return0;}3.3棧應(yīng)用舉例例3.3.1進(jìn)制轉(zhuǎn)換

要求將十進(jìn)制正整數(shù)N轉(zhuǎn)換為k（1<k<10）進(jìn)制數(shù)。十進(jìn)制整數(shù)轉(zhuǎn)換為其他進(jìn)制數(shù)，采用“除以基數(shù)逆序取余數(shù)至商為0為止”的方法。例如：十進(jìn)制整數(shù)123轉(zhuǎn)換為八進(jìn)制后面求得的余數(shù)需先輸出，符合“后進(jìn)先出”的特點(diǎn)，可借助棧來(lái)求解。3.3棧應(yīng)用舉例例3.3.1進(jìn)制轉(zhuǎn)換//把十進(jìn)制正整數(shù)N轉(zhuǎn)換為k（k<10）進(jìn)制voidConversion(intN,intk){

SqStackS;

//定義自定義棧

S.Init();

//使用自定義棧需先初始化

while(N>0){

S.Push(N%k);

N=N/k;

}while(S.Empty()==false){

int

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

cout<<e;

}

cout<<endl;}3.3棧應(yīng)用舉例例3.3.2括號(hào)匹配

對(duì)于由小括弧“(”、“)”和中括弧“[”、“]”構(gòu)成的字符串序列，判斷括號(hào)是否匹配。這里不區(qū)分小括號(hào)和中括號(hào)的優(yōu)先級(jí)。例如，([]())、[([][])]屬于匹配情況，而[(])、([())、(()])屬于不匹配情況。檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。例如，若出現(xiàn)“(”，則期待接著出現(xiàn)“)”；若出現(xiàn)“[”，則期待接著出現(xiàn)“]”。3.3棧應(yīng)用舉例例3.3.2括號(hào)匹配在括號(hào)匹配過(guò)程中，可能出現(xiàn)的不匹配情況如下：（1）到來(lái)的右括弧并非是所“期待”的；

例如，前面出現(xiàn)“(”，但后面到來(lái)“]”；（2）到來(lái)的是“不速之客”；

例如，前面沒(méi)有出現(xiàn)“(”，但后面到來(lái)“)”；（3）直到結(jié)束，也沒(méi)有到來(lái)所“期待”的右括弧；

例如，括弧序列為“(((”。括號(hào)匹配問(wèn)題中，后面出現(xiàn)的“(”或“[”，期待先得到“)”或“]”的匹配，符合“后進(jìn)先出”的特點(diǎn)，因此可借助棧來(lái)完成。3.3棧應(yīng)用舉例例3.3.2括號(hào)匹配括號(hào)匹配算法思想：若出現(xiàn)左括弧，則進(jìn)棧；若出現(xiàn)右括弧，首先檢查棧是否空，若?？?，則表明該右括弧多余，否則檢查棧頂左括弧是否與之匹配，若相匹配，則左括弧出棧，否則表明不匹配。表達(dá)式檢驗(yàn)結(jié)束時(shí)，若棧空，則表明表達(dá)式中的括號(hào)匹配正確，否則表明左括弧多余。3.3棧應(yīng)用舉例例3.3.2括號(hào)匹配boolmatching(stringexp){

SqStackS;

//

定義自定義棧，元素類(lèi)型為char

S.Init();

//

初始化自定義棧

boolstate=true;

//

標(biāo)記變量初始化為true

for(int

i=0;i<exp.size()&&state==true;i++){

if(exp[i]=='('||exp[i]=='[')

//

遇左括弧

S.Push(exp[i]);//

左括弧入棧

elseif(exp[i]==')'&&!S.Empty()&&

S.GetTop()=='(')

S.Pop();

//

若小括號(hào)匹配，則左小括弧出棧

elseif(exp[i]==']'&&!S.Empty()&&S.GetTop()=='[')

S.Pop();

//

若中括號(hào)匹配，則左中括弧出棧

else

//

出現(xiàn)不匹配或棧空情況

state=false;

//

標(biāo)記變量state改為false

}

returnS.Empty()==true&&state==true;}3.3棧應(yīng)用舉例例3.3.3表達(dá)式求值表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯中一個(gè)基本的問(wèn)題。它的實(shí)現(xiàn)也是棧應(yīng)用中的一個(gè)典型的例子。表達(dá)式是由操作數(shù)、運(yùn)算符和界限符組成的有意義的式子。運(yùn)算符從運(yùn)算對(duì)象（操作數(shù)）的個(gè)數(shù)上可分為單目運(yùn)算符、二目運(yùn)算符和三目運(yùn)算符。界限符有左、右括弧和表達(dá)式結(jié)束符等。運(yùn)算符、界限符統(tǒng)稱(chēng)算符。這里僅討論只含二目運(yùn)算符+、-、*、/的算術(shù)表達(dá)式，并且操作數(shù)是僅一位的整數(shù)。表達(dá)式有前綴、中綴和后綴三種表示法，分別稱(chēng)為前綴式、中綴式和后綴式。3.3棧應(yīng)用舉例例3.3.3表達(dá)式求值設(shè)表達(dá)式為S1OPS2，其中S1、S2是操作數(shù)，OP是運(yùn)算符，則前綴式為OPS1S2，中綴式為S1OPS2，后綴式為S1S2OP例如，對(duì)于表達(dá)式a*b+(c-d/e)*f，相應(yīng)的三種表示法如下：（1）中綴式：a*b+c-d/e*f；（2）前綴式：+*ab*-c/def；（3）后綴式：ab*cde/-f*+。可見(jiàn)：（1）在三種表示法中，操作數(shù)之間的相對(duì)次序不變。（2）中綴式的缺點(diǎn)是丟失了括弧信息，致使無(wú)法還原原先的運(yùn)算次序。3.3棧應(yīng)用舉例例3.3.3表達(dá)式求值（3）前綴式的特點(diǎn)是連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式。（4）后綴式的特點(diǎn)是每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式；而且，運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式運(yùn)算順序。因此，這里討論根據(jù)后綴式求值。如何從后綴式求值：根據(jù)后綴式的特點(diǎn)，可以先找運(yùn)算符，再找操作數(shù)。3.3棧應(yīng)用舉例例3.3.3表達(dá)式求值后綴式ab*cde/-f*+的求值過(guò)程示意圖在求值過(guò)程中，需要把中間運(yùn)算結(jié)果保存起來(lái)，而且后面保存的結(jié)果要先取出來(lái)運(yùn)算，符合“后進(jìn)先出”的特點(diǎn)，因此借助棧實(shí)現(xiàn)。因中間計(jì)算結(jié)果可能為實(shí)數(shù)，故使用double類(lèi)型的運(yùn)算數(shù)棧。3.3棧應(yīng)用舉例例3.3.3表達(dá)式求值boolIsNum(charc);

//

判斷字符是否為操作數(shù)doubleCalculate(doublea,doubleb,charop);

//

計(jì)算c=aopb;doublePostfix_exp(stringA){

//

求后綴式A的運(yùn)算結(jié)果

SqStackS;

//

定義自定義棧，元素類(lèi)型為double

S.Init();

//

初始化棧

doubleresult,a,b,c;

for(inti=0;i<A.size();i++){

if(IsNum(A[i])){

//

若是運(yùn)算數(shù)

S.Push(A[i]-'0');

//

則入棧

}

else{

//

若遇到運(yùn)算符，則取出兩個(gè)運(yùn)算數(shù)

b=S.GetTop();

//

取第二個(gè)運(yùn)算數(shù)存放在變量b中

S.Pop();

//

出棧

a=S.GetTop();

//

取第一個(gè)運(yùn)算數(shù)存放在變量a中

S.Pop();3.3棧應(yīng)用舉例例3.3.3表達(dá)式求值

c=Calculate(a,b,A[i]);

//

調(diào)用calculate函數(shù)計(jì)算

S.Push(c);

//

中間運(yùn)算結(jié)果入棧

}

}

result=S.GetTop();

//

最終運(yùn)算結(jié)果存放在result中

S.Pop();

//

出棧

returnresult;

//

返回求值結(jié)果}boolIsNum(charc){

//

判斷字符是否為操作數(shù)

if(c>='0'&&c<='9')returntrue;

elsereturnfalse;}3.3棧應(yīng)用舉例例3.3.3表達(dá)式求值doubleCalculate(doublea,doubleb,charop){//

c=aopb

doublec;

switch(op){

case'+':

c=a+b;break;

case'-':

c=a-b;break;

case'*':

c=a*b;break;

case'/':

c=a/b;break;

}

returnc;}3.3棧應(yīng)用舉例例3.3.3表達(dá)式求值將原表達(dá)式轉(zhuǎn)換為后綴式的算法思想：使用一個(gè)運(yùn)算符棧，掃描原表達(dá)式，若遇到運(yùn)算數(shù)則把其連接到結(jié)果字符串（設(shè)為res，初值為空串）中，若遇運(yùn)算符，則比較當(dāng)前運(yùn)算符與棧頂運(yùn)算符的優(yōu)先級(jí)，若當(dāng)前運(yùn)算符的優(yōu)先級(jí)高，則入棧，否則，在當(dāng)前運(yùn)算符優(yōu)先級(jí)不高于棧頂運(yùn)算符時(shí)不斷出棧棧頂運(yùn)算符連接到res中，再把當(dāng)前運(yùn)算符入棧。另外，遇到左括弧時(shí)入棧，遇到右括弧時(shí)不斷出棧棧頂運(yùn)算符連接到res中，直到把左括弧出棧（左括弧不需連接）。最后，把剩余運(yùn)算符出棧連接到res中。具體算法實(shí)現(xiàn)可參考教材。3.3棧應(yīng)用舉例例3.3.4Hanoi塔問(wèn)題設(shè)A、B、C是三個(gè)塔座。開(kāi)始時(shí)，在塔座A上有n（1≤n≤64）個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。要求將塔座A上的這些圓盤(pán)移到塔座B上，并仍按同樣順序疊放。規(guī)則（1）：每次只能移動(dòng)一個(gè)圓盤(pán)；規(guī)則（2）：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則（3）：在滿足移動(dòng)規(guī)則（1）和（2）的前提下，可將圓盤(pán)移至A，B，C中任何一塔座上。3.3棧應(yīng)用舉例例3.3.4Hanoi塔問(wèn)題3個(gè)圓盤(pán)時(shí)怎么移動(dòng)?n個(gè)圓盤(pán)時(shí)如何處理?把n個(gè)盤(pán)從A移到B，借助C，若n==1，直接移，否則：把n-1個(gè)盤(pán)從A移動(dòng)到C，借助B直接從A到B移動(dòng)最大的盤(pán)把n-1個(gè)盤(pán)從C移動(dòng)到B，借助A3.3棧應(yīng)用舉例例3.3.4Hanoi塔問(wèn)題voidmove(charget,charput){

//

輸出移動(dòng)情況，從get到put

cout<<get<<"-->"<<put<<endl;}//遞歸函數(shù)，n個(gè)圓盤(pán)，從from移動(dòng)到to，借助byvoidhanoi(intn,charfrom,charto,charby){

if(n==1)move(from,to);

//

若只有1個(gè)盤(pán)，則直接移動(dòng)

else{

hanoi(n-1,from,by,to);

//

把n-1個(gè)盤(pán)從from移動(dòng)到by，借助to

move(from,to);//

若只有1個(gè)盤(pán)，則直接移動(dòng)

hanoi(n-1,by,to,from);//

把n-1個(gè)盤(pán)從by移動(dòng)到to，借助from

}}3.3棧應(yīng)用舉例例3.3.4Hanoi塔問(wèn)題intmain(){

intn;

cin>>n;

hanoi(n,

'A','B','C');

//

調(diào)用，實(shí)現(xiàn)把n個(gè)盤(pán)借助C從A移動(dòng)到B

return0;}3.4隊(duì)列基礎(chǔ)循環(huán)隊(duì)列基礎(chǔ)隊(duì)列又稱(chēng)作先進(jìn)先出表，是限定插入操作只能在“表尾”而刪除操作只能在“表頭”進(jìn)行的線性表。順序隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)疥?duì)列使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。循環(huán)隊(duì)列既可以采用順序存儲(chǔ)結(jié)構(gòu)又可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。這里討論的循環(huán)隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)。這里約定在順序隊(duì)列中隊(duì)頭指針front（一個(gè)整數(shù)，表示下標(biāo)）指向隊(duì)頭元素，隊(duì)尾指針rear（一個(gè)整數(shù)，表示下標(biāo)）指向非空隊(duì)列的隊(duì)尾元素的下一個(gè)位置；出隊(duì)時(shí)，front增1，入隊(duì)時(shí)元素存放到rear所指單元且rear增1。3.4隊(duì)列基礎(chǔ)循環(huán)隊(duì)列基礎(chǔ)一個(gè)包含4個(gè)元素的共有5個(gè)存儲(chǔ)單元的順序隊(duì)列如下，此時(shí)front=0，rear=4。

若接著出隊(duì)3個(gè)元素，入隊(duì)1個(gè)元素，則front=3，rear=5，此時(shí)rear超出下標(biāo)范圍，無(wú)法再存入新的元素，但下標(biāo)為0、1和2的三個(gè)存儲(chǔ)單元是空的，產(chǎn)生了“假溢出”現(xiàn)象（有空的存儲(chǔ)單元，但無(wú)法存入新元素）。為避免假溢出，使順序隊(duì)列的首尾相接，即當(dāng)rear增1等于隊(duì)列存儲(chǔ)單元總數(shù)MaxQSize時(shí)使rear=0，從而構(gòu)成循環(huán)隊(duì)列，下標(biāo)為MaxQSize-1和0的兩個(gè)存儲(chǔ)單元邏輯上相鄰。3.4隊(duì)列基礎(chǔ)循環(huán)隊(duì)列基礎(chǔ)循環(huán)隊(duì)列（MaxQSize=5）在隊(duì)空和隊(duì)滿情況下都有front==rear

為區(qū)分隊(duì)空和隊(duì)滿，采用少用一個(gè)存儲(chǔ)單元的方法，即若隊(duì)列存儲(chǔ)單元總數(shù)為MaxQSize，則在存儲(chǔ)了MaxQSize-1個(gè)元素時(shí)就認(rèn)為隊(duì)滿。循環(huán)隊(duì)列入隊(duì)時(shí)的隊(duì)尾指針增1操作修改為rear=(rear+1)%MaxQSize循環(huán)隊(duì)列出隊(duì)時(shí)的隊(duì)頭指針增1操作修改為front=(front+1)%MaxQSize3.4隊(duì)列基礎(chǔ)循環(huán)隊(duì)列基礎(chǔ)少用一個(gè)存儲(chǔ)單元的循環(huán)隊(duì)列示意圖（MaxQSize=8）

在少用一個(gè)存儲(chǔ)單元的情況下，循環(huán)隊(duì)列隊(duì)空的條件為front==rear，隊(duì)滿的條件為(rear+1)%MaxQSize==front。在少用一個(gè)存儲(chǔ)單元的情況下，循環(huán)隊(duì)列中的元素個(gè)數(shù)如何計(jì)算？(rear-front+MaxQSize)%MaxQSize3.4隊(duì)列基礎(chǔ)循環(huán)隊(duì)列的實(shí)現(xiàn)constintMaxQSize=100;

//最大隊(duì)列長(zhǎng)度typedefintElemType;structSqQueue{

//循環(huán)隊(duì)列結(jié)構(gòu)體類(lèi)型

ElemType*base;

intfront;//頭指針，若隊(duì)列不空，指向隊(duì)頭元素

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

voidInit();

//構(gòu)造一個(gè)空隊(duì)列

voidClear();

//清空隊(duì)列

ElemTypeGetFront();

//取隊(duì)頭元素

voidEnQueue(ElemTypee);

//入隊(duì)

voidDeQueue();

//出隊(duì)

boolEmpty();

//判隊(duì)列空};3.4隊(duì)列基礎(chǔ)循環(huán)隊(duì)列的實(shí)現(xiàn)voidSqQueue::Init(){

//構(gòu)造空隊(duì)列

base=newElemType[MaxQSize];

//創(chuàng)建長(zhǎng)度為MaxQSize的動(dòng)態(tài)數(shù)組

front=rear=0;

//隊(duì)頭、隊(duì)尾指針置初值為0}boolSqQueue::Empty(){

//判斷空隊(duì)列

returnfront==rear;

//隊(duì)頭、隊(duì)尾指針相等表示隊(duì)空}voidSqQueue::Clear(){

//清空隊(duì)列

front=rear=0;

//隊(duì)頭、隊(duì)尾指針重置為0}3.4隊(duì)列基礎(chǔ)循環(huán)隊(duì)列的實(shí)現(xiàn)ElemTypeSqQueue::GetFront(){

//取隊(duì)頭元素，調(diào)用時(shí)確保隊(duì)列非空

returnbase[front];

//返回隊(duì)頭指針?biāo)冈貆voidSqQueue::EnQueue(ElemTypee){//入隊(duì)

if((rear+1)%MaxQSize==front)

//隊(duì)列滿

return;

base[rear]=e;

//元素存放到rear所指存儲(chǔ)單元

rear=(rear+1)%MaxQSize;

//rear增1}voidSqQueue::DeQueue(){

//出隊(duì)

if(front==rear)return;

//若為空隊(duì)列，則返回

front=(front+1)%MaxQSize;

//隊(duì)頭指針增1}3.4隊(duì)列基礎(chǔ)循環(huán)隊(duì)列的實(shí)現(xiàn)intmain(){

SqQueuesq;

//定義循環(huán)隊(duì)列

sq.Init();

//初始化循環(huán)隊(duì)列

for(inti=0;i<5;i++){

sq.EnQueue(i+1);

//入隊(duì)

}

//遍歷循環(huán)隊(duì)列

while(!sq.Empty()){

ElemTypet=sq.GetFront();

//取隊(duì)頭元素

cout<<t<<endl;

sq.DeQueue();

//出隊(duì)

}

sq.Clear();

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

return0;}3.4隊(duì)列基礎(chǔ)鏈?zhǔn)疥?duì)列基礎(chǔ)鏈?zhǔn)疥?duì)列是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的隊(duì)列，其插入操作限定在鏈表的表尾，刪除操作限定在鏈表的表頭。用帶頭結(jié)點(diǎn)的鏈表（設(shè)指針域?yàn)閚ext）表示鏈?zhǔn)疥?duì)列，用指向頭結(jié)點(diǎn)的指針front表示隊(duì)頭指針，用指向尾結(jié)點(diǎn)的指針rear表示隊(duì)尾指針鏈?zhǔn)疥?duì)列示意圖包含4個(gè)元素的鏈?zhǔn)疥?duì)列空的鏈?zhǔn)疥?duì)列3.4隊(duì)列基礎(chǔ)鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)typedefintElemType;structQNode{

//結(jié)點(diǎn)類(lèi)型

ElemTypedata;

//數(shù)據(jù)域

QNode*next;

//指針域};structLinkQueue{

//鏈?zhǔn)疥?duì)列類(lèi)型

QNode*front,*rear;

//隊(duì)頭、隊(duì)尾指針

voidInit();

//構(gòu)造一個(gè)空隊(duì)列

voidClear();

//清空隊(duì)列

ElemTypeGetFront();

//取隊(duì)頭元素

voidEnQueue(ElemTypee);

//入隊(duì)

voidDeQueue();

//出隊(duì)

boolEmpty();

//判隊(duì)列空};3.4隊(duì)列基礎(chǔ)鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)voidLinkQueue::Init(){

//構(gòu)造空隊(duì)列

front=rear=newQNode;

front->next=NULL;}boolLinkQueue::Empty(){

//判空

returnfront==rear;//若front==rear，則返回true，否則返回false}voidLinkQueue::Clear(){

//清空

while(front->next){//當(dāng)還存在數(shù)據(jù)結(jié)點(diǎn)時(shí)，不斷刪除隊(duì)頭元素結(jié)點(diǎn)

QNode*p=front->next;

front->next=p->next;

deletep;

}

rear=front;

//若已清空為空隊(duì)列，則隊(duì)尾指針指向頭結(jié)點(diǎn)}3.4隊(duì)列基礎(chǔ)鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)ElemTypeLinkQueue::GetFront(){

//取隊(duì)頭元素

returnfront->next->data;}voidLinkQueue::EnQueue(ElemTypee){//入隊(duì)

QNode*p=newQNode;

//創(chuàng)建新結(jié)點(diǎn)由p指向

p->data=e,p->next=NULL;

rear->next=p;

//新結(jié)點(diǎn)鏈接到隊(duì)尾

rear=p;

//新結(jié)點(diǎn)成為新的隊(duì)尾結(jié)點(diǎn)}3.4隊(duì)列基礎(chǔ)鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)voidLinkQueue::DeQueue(){

//出隊(duì)

if(front==rear)return;

//若為空隊(duì)，則返回

QNode*p=front->next;

//p指向待刪結(jié)點(diǎn)

front->next=p->next;

//調(diào)整隊(duì)頭指針

if(rear==p)

//刪的是最后一個(gè)元素

rear=front;

//若隊(duì)列刪空，則rear指向頭結(jié)點(diǎn)

deletep;

//釋放結(jié)點(diǎn)空間}3.4隊(duì)列基礎(chǔ)鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)intmain(){

LinkQueuelq;

//定義鏈?zhǔn)疥?duì)列

lq.Init();

//初始化鏈?zhǔn)疥?duì)列

for(inti=0;i<5;i++){

lq.EnQueue(i+1);

//入隊(duì)

}

//遍歷鏈?zhǔn)疥?duì)列

while(!lq.Empty()){

ElemTypet=lq.GetFront();

//取隊(duì)頭元素

cout<<t<<endl;

lq.DeQueue();

//出隊(duì)

}

lq.Clear();

//清空鏈?zhǔn)疥?duì)列

return0;}3.5STL之queue基礎(chǔ)知識(shí)STL之queue實(shí)現(xiàn)隊(duì)列的功能。使用queue需包含頭文件queue。通過(guò)實(shí)例化方法定義隊(duì)列，例如：queue<int>Q;//定義隊(duì)列Q，每個(gè)元素為int類(lèi)型其常用操作包括如表3-2所示：3.5STL之queueSTL之queue的基本用法#include<iostream>#include<queue>usingnamespacestd;intmain(){

queue<int>q;

//

定義隊(duì)列

for(inti=0;i<5;i++){

q.push(i+1);

//

入隊(duì)

}

cout<<q.size()<<endl;

//

取得隊(duì)列大小

while(q.empty()==false){

//

遍歷隊(duì)列，當(dāng)隊(duì)列非空時(shí)重復(fù)執(zhí)行

intt=q.front();

//

取隊(duì)頭元素

cout<<t<<endl;

q.pop();

//

出隊(duì)

}

return0;}3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)

要求設(shè)計(jì)一個(gè)算法，計(jì)算從迷宮入口到出口的最短步數(shù)。如圖所示是一個(gè)4×4的迷宮，入口坐標(biāo)為(0,0)，出口坐標(biāo)為(3,3)。其中，'S'代表入口（起點(diǎn)）；'T'代表出口（終點(diǎn)）；'#'代表墻，不能走；'.'代表路，可以走。3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)依照步數(shù)遞增的策略求解，即先檢查1步是否能到出口，若不能則再檢查2步是否能到出口，如此反復(fù)，直到找到出口。算法基本思想：從迷宮入口點(diǎn)出發(fā)，向四周搜索，記下所有一步能到達(dá)的坐標(biāo)點(diǎn)；然后再依次從這些點(diǎn)出發(fā)，記下所有一步能到達(dá)的坐標(biāo)點(diǎn)，……，依此類(lèi)推，直到到達(dá)迷宮的出口點(diǎn)為止。在搜索過(guò)程中必須記下每一個(gè)可達(dá)的坐標(biāo)點(diǎn)，以便從這些點(diǎn)出發(fā)繼續(xù)向四周搜索。在搜索過(guò)程中，是按步數(shù)遞增順序進(jìn)行處理的。以這種處理方式，在找到出口點(diǎn)時(shí)，步數(shù)就是最少的。由于先到達(dá)的點(diǎn)會(huì)得到優(yōu)先處理，故使用具有“先進(jìn)先出”特點(diǎn)的隊(duì)列來(lái)保存已到達(dá)的坐標(biāo)點(diǎn)。3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)實(shí)現(xiàn)該算法需要解決迷宮如何表示、如何控制試探方向、如何避免重復(fù)走到同一個(gè)點(diǎn)、隊(duì)列如何設(shè)計(jì)等四個(gè)問(wèn)題。（1）表示迷宮的數(shù)據(jù)結(jié)構(gòu)

設(shè)迷宮最多有M行N列，則可用二維數(shù)組maze[M][N]來(lái)表示一個(gè)迷宮，其中數(shù)組元素maze[i][j]='.'或'#'，分別表示可走或不可走。另外，迷宮的實(shí)際行數(shù)、列數(shù)可用外部變量m、n表示。constintM=100;

//迷宮的最大行數(shù)constintN=100;//迷宮的最大列數(shù)charmaze[M][N];

//迷宮數(shù)組intm,n;

//迷宮的實(shí)際行數(shù)、列數(shù)3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)（2）試探方向設(shè)當(dāng)前點(diǎn)為(x,y)，則從該點(diǎn)1步可走到的4個(gè)相鄰的點(diǎn)如下所示。4個(gè)相鄰點(diǎn)在行、列坐標(biāo)上的增量分別為(0,

1)、(1,

0)、(0,

-1)和(-1,

0)。因此，定義一個(gè)二維的方向數(shù)組dir保存這些增量。intdir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

//對(duì)應(yīng)右、下、左、上四個(gè)方向i=x+dir[d][0];j=y+dir[d][1];從某點(diǎn)(x,

y)按某一方向d(0≤d≤3)到達(dá)的新點(diǎn)(i,

j)的坐標(biāo)3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)（3）如何防止重復(fù)到達(dá)某點(diǎn)，以避免發(fā)生死循環(huán)

設(shè)置一個(gè)輔助的標(biāo)記數(shù)組visited[m][n]，它的所有元素一開(kāi)始都初始化為false，表示所有點(diǎn)都未走過(guò)，一旦到達(dá)了某一點(diǎn)(i,j)之后，把visited[i][j]置為true表示該點(diǎn)已走過(guò)，下次再試探這個(gè)點(diǎn)時(shí)發(fā)現(xiàn)visited[i][j]==true就不能再走了。（4）隊(duì)列的設(shè)計(jì)

隊(duì)列存放搜索過(guò)程中搜索到的點(diǎn)。方便起見(jiàn)，設(shè)計(jì)一個(gè)表示點(diǎn)的結(jié)構(gòu)體，包含行、列坐標(biāo)和從起點(diǎn)走到該點(diǎn)的步數(shù)。structPos{

intx,y,steps;

//行、列坐標(biāo),當(dāng)前步數(shù)};3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)（4）隊(duì)列的設(shè)計(jì)

隊(duì)列的初始狀態(tài)為空隊(duì)列；首先入口點(diǎn)入隊(duì)，當(dāng)隊(duì)列非空時(shí)反復(fù)執(zhí)行以下操作：

隊(duì)頭元素出隊(duì)，并以其為搜索的出發(fā)點(diǎn)，當(dāng)搜索到一個(gè)可到達(dá)點(diǎn)(i,j)（i,j均為有效坐標(biāo)，且maze[i][j]=='.'、visited[i][j]==false）時(shí)，即將該點(diǎn)的坐標(biāo)位置入隊(duì)。

在搜索過(guò)程中，若遇到出口點(diǎn)則表示搜索成功，返回該點(diǎn)的步數(shù)并結(jié)束搜索；若遇到當(dāng)前隊(duì)列為空，則表明再無(wú)搜索出發(fā)點(diǎn)，這種情況下不存在從起點(diǎn)到終點(diǎn)的路徑，也結(jié)束搜索。3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)#include<iostream>#include<queue>usingnamespacestd;structPos{

//

坐標(biāo)的結(jié)構(gòu)體

intx,y,steps;};intdir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//

對(duì)應(yīng)右下左上四個(gè)方向constintM=100,N=100;

//

最大的行數(shù)、列數(shù)charmaze[M][N];

//

迷宮數(shù)組boolvisited[M][N];

//

標(biāo)記數(shù)組PosS,T;

//

起點(diǎn)和終點(diǎn)intm,n;

//

實(shí)際的行數(shù)、列數(shù)intmazeBFS();

//

迷宮廣度優(yōu)先搜索算法voidinputMaze();//輸入迷宮并記錄起點(diǎn)、終點(diǎn)的函數(shù)3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)intmain(){

cin>>m>>n;

//

輸入迷宮的實(shí)際行數(shù)、列數(shù)

inputMaze();

//

輸入迷宮并記錄起點(diǎn)、終點(diǎn)

intres=mazeBFS();

//

調(diào)用迷宮廣度優(yōu)先搜索算法

if(res==-1)

//

返回-1表示找不到通路

cout<<"impossible"<<endl;

else

//

找到通路則輸出最短步數(shù)

cout<<res<<endl;

return0;}3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)intmazeBFS(){

//

迷宮廣度優(yōu)先搜索

fill(&visited[0][0],&visited[m-1][n-1]+1,false);//

清空

queue<Pos>Q;

//

定義隊(duì)列

Q.push(S);

//

起點(diǎn)入隊(duì)

visited[S.x][S.y]=true;

//

置起點(diǎn)的訪問(wèn)標(biāo)記為true

while(!Q.empty()){

//

當(dāng)隊(duì)列非空時(shí)，循環(huán)處理

Posp=Q.front();

//

取隊(duì)頭元素

Q.pop();

//

出隊(duì)

if(p.x==T.x&&p.y==T.y)

//

成功到達(dá)終點(diǎn)，返回最短步數(shù)

returnp.steps;

for(inti=0;i<4;i++){

//

處理相鄰4個(gè)方向

//取得可能能走的點(diǎn)

Pose={p.x+dir[i][0],p.y+dir[i][1],p.steps+1};

if(e.x>=m||e.x<0||e.y>=n||e.y<0)

//

迷宮之外

continue;

3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)

if(visited[e.x][e.y]==true)

//

已走過(guò)

continue;

if(maze[e.x][e.y]=='#')

//

不能走

continue;

Q.push(e);

//

可走的相鄰點(diǎn)入隊(duì)

visited[e.x][e.y]=true;

//

置可走點(diǎn)訪問(wèn)標(biāo)記為true

}

}

return-1;

//

路徑不通，返回特殊值-1}3.6隊(duì)列應(yīng)用舉例例3.6.1迷宮最短步數(shù)voidinputMaze(){

//

輸入迷宮，記錄起點(diǎn)、終點(diǎn)

for(inti=0;i<m;i++){

for(intj=0;j<n;j++){

cin>>maze[i][j];

if(maze[i][j]=='S'){

S.x=i;

S.y=j;

S.steps=0;

}

elseif(maze[i][j]=='T'){

T.x=i,

T.y=j;

}

}

}}3.7在線題目求解例3.7.1胡同

有一個(gè)死胡同，寬度剛好只能讓一輛汽車(chē)通過(guò)，偏偏老有汽車(chē)開(kāi)到死胡同來(lái)，這下麻煩了，最先開(kāi)來(lái)的汽車(chē)要最后才能倒退出去。給定一個(gè)汽車(chē)開(kāi)來(lái)的序列和一個(gè)可能的倒車(chē)出去的序列，請(qǐng)判斷汽車(chē)能否都倒退出去，若能則輸出Yes，否則輸出No。輸入:

首先輸入一個(gè)整數(shù)T，表示測(cè)試數(shù)據(jù)的組數(shù)，然后是T組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)首先輸入一個(gè)正整數(shù)n（n≤10），代表開(kāi)來(lái)的汽車(chē)數(shù)，然后輸入2n個(gè)整數(shù)，其中，前n個(gè)整數(shù)表示汽車(chē)開(kāi)來(lái)的序列，后n個(gè)整數(shù)表示汽車(chē)可能倒出的序列。輸出:

對(duì)于每組測(cè)試，判斷能否倒車(chē)出該死胡同，若能則輸出“Yes”，否則輸出“No”。引號(hào)不必輸出。3.7在線題目求解例3.7.1胡同輸入樣例:2412342143412344213輸出樣例:YesNo解析：倒車(chē)時(shí)后面開(kāi)來(lái)的車(chē)要先退出，具有“后進(jìn)先出”的特點(diǎn)，可以借助棧求解。汽車(chē)開(kāi)來(lái)的序列可視為入棧序列，倒車(chē)序列可視為出棧序列。對(duì)于入棧序列中的每個(gè)數(shù)，逐個(gè)入棧，當(dāng)棧非空且棧頂元素與出棧序列中的當(dāng)前元素（用下標(biāo)j指向，初值為0）相等時(shí)，棧頂元素出棧，j增1。最后判斷棧是否為空，若為空則輸出Yes，否則輸出No。3.7在線題目求解例3.7.1胡同#include<iostream>#include<stack>usingnamespacestd;voidmatch(inta[],intb[],intn){

stack<int>s;

//定義棧

intj=0;

//j指向出棧序列中的當(dāng)前元素

for(inti=0;i<n;i++){//所有入棧序列中的元素入棧

s.push(a[i]);

//a[i]入棧

while(!s.empty()&&s.top()==b[j]){

s.pop();

//出棧

j++;

//j指向下一個(gè)元素

}

}

if(s.empty()==true)cout<<"Yes\n";

elsecout<<"No\n";}3.7在線題目求解例3.7.1胡同intmain(){

intT;

cin>>T;

while(T--){

inta[10],b[10];

intn,i;

cin>>n;

for(i=0;i<n;i++)cin>>a[i];

for(i=0;i<n;i++)cin>>b[i];

match(a,b,n);

}

return0;}3.7在線題目求解例3.7.2僅有尾指針的循環(huán)隊(duì)列

輸入一個(gè)整數(shù)序列：a1，a2，a3，…，an，進(jìn)行入隊(duì)或出隊(duì)操作。用帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意：不設(shè)頭指針），試編寫(xiě)相應(yīng)的置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法，并實(shí)現(xiàn)以下任務(wù)：對(duì)輸入的ai，當(dāng)ai>0時(shí)，將ai入隊(duì)；當(dāng)ai=0時(shí)，隊(duì)頭元素出隊(duì)，若出隊(duì)時(shí)發(fā)現(xiàn)隊(duì)空則產(chǎn)生下溢“UNDERFLOW”，一旦產(chǎn)生下溢，則停止處理。輸入:

測(cè)試數(shù)據(jù)有多組，處理到文件尾。每組測(cè)試數(shù)據(jù)首先輸入正整數(shù)n（n≤30），再輸入n個(gè)整數(shù)。輸出:

對(duì)于每組測(cè)試，若處理過(guò)程中未發(fā)生下溢，則依次輸出隊(duì)列中當(dāng)前還存在的元素（每?jī)蓚€(gè)數(shù)據(jù)之間留一個(gè)空格），否則輸出“UNDERFLOW”表示下溢。引號(hào)不必輸出。3.7在線題目求解例3.7.2僅有尾指針的循環(huán)隊(duì)列輸入樣例:111234560078071230000輸出樣例:45678UNDERFLOW解析：本題與與前述的鏈?zhǔn)疥?duì)列的不同之處在于不設(shè)頭指針且是循環(huán)鏈表。設(shè)指針域?yàn)閚ext，因是循環(huán)鏈表，尾結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，故rear->next可以視為頭指針front，此后的基本操作定義類(lèi)似前述的鏈?zhǔn)疥?duì)列。3.7在線題目求解例3.7.2僅有尾指針的循環(huán)隊(duì)列typedefintElemType;structQNode{

//結(jié)點(diǎn)類(lèi)型

ElemTypedata;

QNode*next;};structLinkQueue{

QNode*rear;

//隊(duì)尾指針

voidInit();

//構(gòu)造一個(gè)空隊(duì)列

voidClear();

//清空隊(duì)列

ElemTypeGetFront();

//取隊(duì)頭元素

voidEnQueue(ElemTypee);

//入隊(duì)

boolDeQueue();

//出隊(duì)

boolEmpty();

//判隊(duì)列空};3.7在線題目求解例3.7.2僅有尾指針的循環(huán)隊(duì)列voidLinkQueue::Init(){//構(gòu)造空隊(duì)列rear=newQNode;rear->next=rear;}//把e插入為新的隊(duì)尾元素voidLinkQueue::EnQueue(ElemTypee){QNode*p=newQNode;p->data=e;p->next=rear->next;rear->next=p;rear=p;}3.7在線題目求解例3.7.2僅有尾指針的循環(huán)隊(duì)列boolLinkQueue::DeQueue(){//刪除隊(duì)頭元素if(rear==rear->next)returnfalse;QNode*p=rear->next->next;rear->next->next=p->next;if(rear==p)rear=rear->next;deletep;returntrue;}3.7在線題目求解例3.7.2僅有尾指針的循環(huán)隊(duì)列#include<iostream>usingnamespacestd;voidsolve(intn){

LinkQueuelq;

lq.Init();

inti;

ElemTypet;

boolflag=true;

for(i=0;i<n;i++){

cin>>t;

if(t==0){

if(flag&&lq.DeQueue()==false){

cout<<"UNDERFLOW"<<endl;

flag=false;

}3.7在線題目求解例3.7.2僅有尾指針的循環(huán)隊(duì)列

}

else{

lq.EnQueue(t);

}

}

if(flag==false)return;

intcnt=0;

QNode*q=lq.rear->next->next;

while(q!=lq.rear->next){

cnt++;

if(cnt>1)cout<<"";

cout<<q->data;

q=q->next;

}

cout<<endl;