第三章棧和隊(duì)列

1第三章 棧和隊(duì)列棧隊(duì)列優(yōu)先級(jí)隊(duì)列與表不同的是，它們都是限制存取位置的線性結(jié)構(gòu)線性結(jié)構(gòu)§3.1棧（stack）只允許在一端插入和刪除的線性表允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點(diǎn)后進(jìn)先出(LIFO)2template<classE>class

Stack{ public:

Stack(

int=10); //構(gòu)造函數(shù)

void

Push(

constE

&item);//進(jìn)棧

EPop();//出棧

EgetTop();//取棧頂元素

void

makeEmpty();//置空棧

intIsEmpty()

const;//判?？辗?/p>

int

IsFull()

const;//判棧滿否}棧的抽象數(shù)據(jù)類(lèi)型3棧的數(shù)組表示—順序棧#include<assert.h>template<classE>

classSeqStack:publicStack<E>{private:int

top;

//棧頂指針E*elements;

//棧元素?cái)?shù)組

intmaxSize;

//棧最大容量

voidoverflowProcess();

//棧的溢出處理0123456789maxSize-1top(?？?elements4

public:Stack(intsz

=10);

//構(gòu)造函數(shù)

~Stack(){delete[]elements;

}

voidPush(Ex);

//進(jìn)棧

intPop(E&x);

//出棧

intgetTop(E&x);

//取棧頂

voidmakeEmpty(){top=-1;

}

//置空棧

intIsEmpty()const{returntop==-1;

}

intIsFull()const{returntop==maxSize-1;

} }5

top空棧toptoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出進(jìn)棧示例6topc退棧b退棧abaa退棧空棧topabdd退棧ctopabctoptoptopabdee退棧c退棧示例78順序棧的操作template<classE>voidSeqStack<E>::overflowProcess(){//私有函數(shù)：當(dāng)棧滿則執(zhí)行擴(kuò)充棧存儲(chǔ)空間處理

E*newArray=newE[2*maxSize]; //創(chuàng)建更大的存儲(chǔ)數(shù)組

for(inti=0;i<=top;i++)newArray[i]=elements[i]; maxSize+=maxSize;

delete[]elements;

elements=newArray; //改變elements指針};9template<classE>voidSeqStack<E>::Push(Ex){//若棧不滿,則將元素x插入該棧棧頂,否則溢出處理

if(IsFull()==true)overflowProcess(); //棧滿

elements[++top]=x;

//棧頂指針先加1,再進(jìn)棧};

template<classE>boolSeqStack<E>::Pop(E&x){//函數(shù)退出棧頂元素并返回棧頂元素的值

if(IsEmpty()==true)returnfalse; x=elements[top--]; //棧頂指針退1

returntrue; //退棧成功};

10template<classE>boolSeqstack<E>::getTop(E&x){//若棧不空則函數(shù)返回該棧棧頂元素的地址

if(IsEmpty()==true)returnfalse; x=elements[top];returntrue;};雙棧共享一個(gè)?？臻g（多棧共享?xiàng)？臻g）如何合理進(jìn)行?？臻g分配，以避免棧溢出或空間的浪費(fèi)？棧的鏈接存儲(chǔ)方式——鏈?zhǔn)綏?1兩個(gè)棧共享一個(gè)數(shù)組空間V[maxSize]設(shè)立棧頂指針數(shù)組

t[2]

和棧底指針數(shù)組

b[2]

t[i]和b[i]分別指示第

i

個(gè)棧的棧頂與棧底初始

t[0]=b[0]=-1,t[1]=b[1]=maxSize棧滿條件：t[0]+1==t[1]//棧頂指針相遇?？諚l件：t[0]=b[0]或t[1]=b[1]

//棧頂指針退到棧底雙棧共享一個(gè)?？臻g12boolPush(DualStack&DS,Ex,inti){if(DS.t[0]+1==DS.t[1])returnfalse;

if(i==0)DS.t[0]++;elseDS.t[1]--;DS.V[DS.t[i]]=x;returntrue;}boolPop(DualStack&DS,E&x,inti){if(DS.t[i]==DS.b[i])returnfalse;x=DS.V[DS.t[i]];if(i==0)DS.t[0]--;elseDS.t[1]++;returntrue;}

13棧的鏈接表示—鏈?zhǔn)綏ｆ準(zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^1415鏈?zhǔn)綏?LinkedStack)類(lèi)的定義#include<iostream.h>#include“stack.h”template<classE>structStackNode{//棧結(jié)點(diǎn)類(lèi)定義private:

Edata; //棧結(jié)點(diǎn)數(shù)據(jù)

StackNode<E>*link;//結(jié)點(diǎn)鏈指針public:StackNode(Ed=0,StackNode<E>*next=NULL)

:data(d),link(next){}};

16template<classE>classLinkedStack:publicStack<E>{//鏈?zhǔn)綏ｎ?lèi)定義

private: StackNode<E>*top;

//棧頂指針

public:LinkedStack():top(NULL){}

//構(gòu)造函數(shù)

～LinkedStack(){makeEmpty();

}//析構(gòu)函數(shù)

voidPush(Ex);

//進(jìn)棧

boolPop(E&x);

//退棧17

boolgetTop(E&x)const;

//取棧頂

boolIsEmpty()const{returntop==NULL;}

voidmakeEmpty();

//清空棧的內(nèi)容friendostream&operator<<(ostream&os,LinkedStack<E>&s);

//輸出棧元素的重載操作<<};18鏈?zhǔn)綏ｎ?lèi)操作的實(shí)現(xiàn)template<classE>LinkedStack<E>::makeEmpty(){

//逐次刪去鏈?zhǔn)綏Ｖ械脑刂敝翖ｍ斨羔槥榭铡?/p>

StackNode<E>*p; while(top!=NULL) //逐個(gè)結(jié)點(diǎn)釋放

{p=top;top=top->link;

deletep;}};template<classE>voidLinkedStack<E>::Push(Ex){//將元素值x插入到鏈?zhǔn)綏５臈ｍ?即鏈頭

top=newStackNode<E>(x,top);

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

assert(top!=NULL);

//創(chuàng)建失敗退出};19template<classE>boolLinkedStack<E>::Pop(E&x){//刪除棧頂結(jié)點(diǎn),返回被刪棧頂元素的值。

if(IsEmpty()==true)returnfalse;//棧空返回

StackNode<E>*p=top;

//暫存棧頂元素

top=top->link;

//退棧頂指針

x=p->data;deletep;

//釋放結(jié)點(diǎn)

returntrue; };20template<classE>boolLinkedStack<E>::getTop(E&x)const{

if(IsEmpty()==true)returnfalse;//?？辗祷?/p>

x=top->data;//返回棧頂元素的值

returntrue; };21template<classE>ostream&operator<<(ostream&os,LinkedStack<E>&s){//輸出棧中元素的重載操作<<os<<“棧中元素個(gè)數(shù)=”<<s.getSize()<<endl;LinkNode<E>*p=s.top;inti=0;while(p!=NULL){os<<++i<<“:”<<p->data<<endl;

p=p->link;

}returnos;};

思考：當(dāng)進(jìn)棧元素的編號(hào)為1,2,…,n時(shí)，可能的出棧序列有多少種？算術(shù)表達(dá)式有三種表示：中綴(infix)表示

<操作數(shù)><操作符><操作數(shù)>，如A+B；前綴(prefix)表示

<操作符><操作數(shù)><操作數(shù)>，如+AB；后綴(postfix)表示

<操作數(shù)><操作數(shù)><操作符>，如AB+；棧的應(yīng)用：表達(dá)式的計(jì)算22A+B*(C-D)-E/Fr1r4r2r3r5中綴表達(dá)式→后綴表達(dá)式A+B*(C-D)-E/FABCD-*+EF/-表達(dá)式示例23中綴表達(dá)式

A+B*

(C-D)-E/F表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋簝?yōu)先級(jí)高的先計(jì)算優(yōu)先級(jí)相同的自左向右計(jì)算當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開(kāi)始計(jì)算

在后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)的優(yōu)先次序，括號(hào)在后綴表達(dá)式中不出現(xiàn)。后綴表達(dá)式ABCD-

*+EF/-24應(yīng)用后綴表示計(jì)算表達(dá)式的值idea：從左向右順序地掃描表達(dá)式，并用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。掃描中遇操作數(shù)則壓棧；遇操作符則從棧中退出兩個(gè)操作數(shù)，計(jì)算后將結(jié)果壓入棧最后計(jì)算結(jié)果在棧頂25r1r2r3r4r5r6計(jì)算例ABCD-

*+EF^G/-26計(jì)算后綴表達(dá)式

ABCD-

*+EF^G/-27計(jì)算后綴表達(dá)式

ABCD-

*+EF^G/-28voidCalculator::Run(){charch;

doublenewoperand;while(cin>>ch,ch!=‘;’){switch(ch){

case‘+’:case‘-’:case‘*’:case‘/’: case‘^’:DoOperator(ch);break; //計(jì)算

default:cin.putback(ch);

//將字符放回輸入流

cin>>newoperand;//讀操作數(shù)

S.Push(newoperand);}}}29void

Calculator::DoOperator(charop){//從棧S中取兩個(gè)操作數(shù)，形成運(yùn)算指令并計(jì)算進(jìn)棧

doubleleft,right;boolresult;

result=Get2Operands(left,right);//退出兩個(gè)操作數(shù)if(!result)return;switch(op){

case‘+’:S.Push(left+right);break;

//加

case‘-’:S.Push(left-right);break;

//減

case‘*’:S.Push(left*right);break;

//乘

case‘/’:

if(right!=0.0){S.Push(left/right);break;}

else

{cout<<“除數(shù)為0!\n”);exit(1);}

//除case‘^’:S.Push(Power(left,right));//乘冪}}30bool

Calculator::Get2Operands(double&left,double&right){//從棧S中取兩個(gè)操作數(shù)if(S.IsEmpty()==true){cerr<<“缺少右操作數(shù)！”<<endl;returnfalse;}S.Pop(right);if(S.IsEmpty()==true){cerr<<“缺少左操作數(shù)！”<<endl;returnfalse;}S.Pop(left);returntrue;}3132一般表達(dá)式的操作符有4種類(lèi)型：

算術(shù)操作符

如雙目操作符（+、-、*、/和%）以及單目操作符（-）。

關(guān)系操作符

包括<、<=、==、!=、>=、>。這些操作符主要用于比較。

邏輯操作符

如與(&&)、或(||)、非(!)。

括號(hào)‘(’和‘)’

,

它們的作用是改變運(yùn)算順序。33中綴表示→后綴表示先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序加上括號(hào)，再把操作符后移到右括號(hào)的后面并以就近移動(dòng)為原則，最后將所有括號(hào)消去。如中綴表示(A+B)*D-E/(F+A*D)+C，其轉(zhuǎn)換為后綴表達(dá)式的過(guò)程如下：

(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)后綴表示

AB+D*EFAD*+/-C+34利用棧將中綴表示轉(zhuǎn)換為后綴表示使用?？蓪⒈磉_(dá)式的中綴表示轉(zhuǎn)換成它的后綴表示。為了實(shí)現(xiàn)這種轉(zhuǎn)換，需要考慮各操作符的優(yōu)先級(jí)。35各個(gè)算術(shù)操作符的優(yōu)先級(jí)isp叫做棧內(nèi)(instackpriority)優(yōu)先級(jí)icp叫做棧外(incomingpriority)優(yōu)先級(jí)。操作符優(yōu)先級(jí)相等的情況只出現(xiàn)在括號(hào)配對(duì)或棧底的“;”號(hào)與輸入流最后的“;”號(hào)配對(duì)時(shí)。36中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法操作符棧初始化，將結(jié)束符‘;’進(jìn)棧。然后讀入中綴表達(dá)式字符流的首字符ch。重復(fù)執(zhí)行以下步驟，直到ch=‘;’，同時(shí)棧頂?shù)牟僮鞣彩恰?’，停止循環(huán)。若ch是操作數(shù)直接輸出，讀入下一個(gè)字符ch。若ch是操作符，判斷ch的優(yōu)先級(jí)icp和位于棧頂?shù)牟僮鞣鹢p的優(yōu)先級(jí)isp：37若icp(ch)>isp(op)，令ch進(jìn)棧，讀入下一個(gè)字符ch。若icp(ch)<isp(op)，退棧并輸出。若icp(ch)==isp(op)，退棧但不輸出，若退出的是“(”號(hào)讀入下一個(gè)字符ch。算法結(jié)束，輸出序列即為所需的后綴表達(dá)式383940遞歸的定義

若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過(guò)程直接地或間接地調(diào)用自己,則稱這個(gè)過(guò)程是遞歸的過(guò)程。以下三種情況常常用到遞歸方法。

定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的§3.2棧與遞歸41定義是遞歸的求解階乘函數(shù)的遞歸算法longFactorial(longn){if(n==0)return1;

elsereturnn*Factorial(n-1);}例如，階乘函數(shù)42求解階乘n!的過(guò)程主程序

main:factorial(4)參數(shù)4計(jì)算4*factorial(3)

返回24參數(shù)3計(jì)算3*factorial

(2)

返回6參數(shù)2計(jì)算2*factorial

(1)

返回2參數(shù)1計(jì)算1*factorial(0)

返回1參數(shù)0直接定值=1

返回1參數(shù)傳遞結(jié)果返回遞歸調(diào)用返回求值43例如，單鏈表結(jié)構(gòu)一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈表;一個(gè)結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個(gè)單鏈表。數(shù)據(jù)結(jié)構(gòu)是遞歸的f

f

搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值template<classE>

voidPrint(ListNode<E>*f){if(f->link==NULL)

cout<<f->data<<

endl;elsePrint(f->link);}fffff

a0a1a2a3a4遞歸找鏈尾4445問(wèn)題的解法是遞歸的例，漢諾塔(TowerofHanoi)問(wèn)題的解法： 如果n=1，則將這一個(gè)盤(pán)子直接從A柱移到C柱上。否則，執(zhí)行以下三步：用C柱做過(guò)渡，將A柱上的(n-1)個(gè)盤(pán)子移到B柱上：將A柱上最后一個(gè)盤(pán)子直接移到C柱上；用A柱做過(guò)渡，將B柱上的(n-1)個(gè)盤(pán)子移到C柱上。46#include<iostream.h>void

Hanoi(intn,

charA,

charB,

charC){//解決漢諾塔問(wèn)題的算法

if(n==1)cout<<"move"<<A<<"to"<<C<<endl;

else{Hanoi(n-1,A,C,B);

cout<<"move"<<A<<"to"<<C<<endl; Hanoi(n-1,B,A,C);

}}47(3,A,B,C)(2,A,C,B)A->CA,B,C(1,A,C,B)A,B,CA->CA->C(1,B,A,C)A,B,CA->CA->BA->BA->CB->CC->BA->C(2,B,A,C)A,B,C(1,A,C,B)A,B,CA->CA->C(1,B,A,C)A,B,CA->CB->CA->BB->AB->CA->C4849什么時(shí)候運(yùn)用遞歸？子問(wèn)題應(yīng)與原問(wèn)題做同樣的事情，且更為簡(jiǎn)單；把一個(gè)規(guī)模比較大的問(wèn)題分解為一個(gè)或若干規(guī)模比較小的問(wèn)題，分別對(duì)這些比較小的問(wèn)題求解，再綜合它們的結(jié)果，從而得到原問(wèn)題的解。

—分而治之策略（分治法）這些比較小的問(wèn)題的求解方法與原來(lái)問(wèn)題的求解方法一樣。50構(gòu)成遞歸的條件不能無(wú)限制地調(diào)用本身，必須有一個(gè)出口，化簡(jiǎn)為非遞歸狀況直接處理。

Procedure<name>(<parameterlist>){if(<initialcondition>)//遞歸結(jié)束條件

return(initialvalue);else//遞歸

return(<name>(parameterexchange));}51遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，退出時(shí)的次序正好相反：

遞歸調(diào)用

n!(n-1)!(n-2)!1!0!=1

返回次序主程序第一次調(diào)用遞歸過(guò)程為外部調(diào)用；遞歸過(guò)程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。它們返回調(diào)用它的過(guò)程的地址不同。遞歸過(guò)程與遞歸工作棧

longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);

returntemp; }

voidmain(){ intn;

n=Factorial(4);

}RetLoc1RetLoc25253遞歸工作棧每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量等另外分配存儲(chǔ)空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。

局部變量返回地址參數(shù)活動(dòng)記錄框架遞歸工作記錄遞歸工作棧54函數(shù)遞歸時(shí)的活動(dòng)記錄……………….<下一條指令>Function(<參數(shù)表>)……………….<return>調(diào)用塊函數(shù)塊返回地址(下一條指令)局部變量參數(shù)計(jì)算Factorial時(shí)活動(dòng)記錄的內(nèi)容遞歸調(diào)用序列01RetLoc211RetLoc222RetLoc236RetLoc2424RetLoc1參數(shù)返回值返回地址返回時(shí)的指令return4*6//返回

24

return3*2//返回

6

return

1//返回

1

return1*1//返回

1

return2*1//返回

2

5556遞歸過(guò)程改為非遞歸過(guò)程遞歸過(guò)程簡(jiǎn)潔、易編、易懂遞歸過(guò)程效率低，重復(fù)計(jì)算多改為非遞歸過(guò)程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過(guò)程其他情形必須借助棧實(shí)現(xiàn)非遞歸過(guò)程計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義57

求解斐波那契數(shù)列的遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5

調(diào)用次數(shù)

NumCall(k)=2*Fib(k+1)-1斐波那契數(shù)列的遞歸調(diào)用樹(shù)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)5859單向遞歸用迭代法實(shí)現(xiàn)longFibIter(longn){if(n<=1)returnn;

longtwoback=0,oneback=1,Current;

for(inti=2;i<=n;i++){Current=twoback+oneback;twoback=oneback;oneback=Current;

}

returnCurrent;}voidrecfunc(intA[],intn){if(n>=0){

cout

<<A[n]<<“”;n--;recfunc(A,n);}}

2536721899495463

60尾遞歸用迭代法實(shí)現(xiàn)voidsterfunc(intA[],intn){//消除了尾遞歸的非遞歸函數(shù)

while(n>=0){cout

<<"value"<<A[n]<<endl;n--;

}}

61§3.3隊(duì)列（queue）定義隊(duì)列是只允許在一端刪除，在另一端插入的線性表允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)62template<classE>classQueue{public:Queue(){};

//構(gòu)造函數(shù)

～Queue(){};

//析構(gòu)函數(shù)

virtualboolEnQueue(Ex)=0;//進(jìn)隊(duì)列

virtualboolDeQueue(E&x)=0; //出隊(duì)列

virtualboolgetFront(E&x)=0; //取隊(duì)頭

virtualboolIsEmpty()const=0; //判隊(duì)列空

virtualboolIsFull()const=0; //判隊(duì)列滿};63隊(duì)列的抽象數(shù)據(jù)類(lèi)型#include<assert.h>#include<iostream.h>#include“Queue.h”template<classE>classSeqQueue:publicQueue<E>{ //隊(duì)列類(lèi)定義protected:intrear,front; //隊(duì)尾與隊(duì)頭指針

E*elements; //隊(duì)列存放數(shù)組

intmaxSize; //隊(duì)列最大容量public:

SeqQueue(intsz=10);//構(gòu)造函數(shù)

隊(duì)列的數(shù)組存儲(chǔ)表示─順序隊(duì)列64～SeqQueue(){

delete[]elements;}//析構(gòu)函數(shù)

boolEnQueue(Ex);//新元素進(jìn)隊(duì)列

boolDeQueue(E&x);//退出隊(duì)頭元素

boolgetFront(E&x);

//取隊(duì)頭元素值

void

makeEmpty(){front=rear=0;}

boolIsEmpty()const{returnfront==rear;}

boolIsFull()const

{returnrear==maxSize;}

intgetSize()const{returnrear-front;}

};65隊(duì)列的進(jìn)隊(duì)和出隊(duì)（數(shù)組方式）

frontrear空隊(duì)列frontrearA進(jìn)隊(duì)AfrontrearB進(jìn)隊(duì)ABfrontrearC,D進(jìn)隊(duì)ABCDfrontrearA退隊(duì)BCDfrontrearB退隊(duì)CDfrontrearE,F,G進(jìn)隊(duì)CDEFGCDEFGfrontrearH進(jìn)隊(duì),溢出66隊(duì)列的進(jìn)隊(duì)和出隊(duì)

進(jìn)隊(duì):新元素在rear處加入，rear=rear+1。

出隊(duì):取出下標(biāo)為front的元素，front=front+1

隊(duì)空時(shí)

rear==front

隊(duì)滿時(shí)

rear==maxSize

（假溢出）解決假溢出的辦法之一：將隊(duì)列元素存放數(shù)組首尾相接，形成循環(huán)（環(huán)形）隊(duì)列。6768隊(duì)列存放數(shù)組被當(dāng)作首尾相連的表處理。隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize-1直接進(jìn)到0,可用語(yǔ)言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:front=(front+1)%maxSize;隊(duì)尾指針進(jìn)1:

rear=(rear+1)%maxSize;隊(duì)列初始化：front=rear

=0;隊(duì)空條件：front

==

rear;隊(duì)滿條件：(rear+1)%maxSize==front

循環(huán)隊(duì)列(CircularQueue)01234567front01234567front01234567frontrearAABCrearrear空隊(duì)列A進(jìn)隊(duì)B,C進(jìn)隊(duì)0123456701234567A退隊(duì)B退隊(duì)01234567D,E,F,G,H,I進(jìn)隊(duì)frontBCrearAfrontBCrearfrontCrearDEFGHI6970循環(huán)隊(duì)列操作的定義voidMakeEmpty(){front=rear=0;

}intIsEmpty()const

{returnfront==rear;}intIsFull()const{return(rear+1)%maxSize==front;}

template<classE>SeqQueue<E>::SeqQueue(intsz)

:front(0),rear(0),maxSize(sz){//構(gòu)造函數(shù)

elements=newE[maxSize];

assert(elements!=NULL);};71template<classE>bool

SeqQueue<E>::EnQueue(Ex){//若隊(duì)列不滿,則將x插入到該隊(duì)列隊(duì)尾,否則返回

if(IsFull()==true)returnfalse;elements[rear]=x;//先存入

rear=(rear+1)%maxSize;//尾指針加一

returntrue; };

72template<classE>boolSeqQueue<E>::DeQueue(E&x){//若隊(duì)列不空則函數(shù)退隊(duì)頭元素并返回其值

if(IsEmpty()==true)returnfalse;

x=elements[front];//先取隊(duì)頭

front=(front+1)%maxSize;

//再隊(duì)頭指針加一

returntrue;};template<classE>boolSeqQueue<E>::getFront(E&x)const{//若隊(duì)列不空則函數(shù)返回該隊(duì)列隊(duì)頭元素的值

if(IsEmpty()==true)returnfalse;//隊(duì)列空

x=elements[front]; //返回隊(duì)頭元素

returntrue;};

隊(duì)列的鏈接表示—鏈?zhǔn)疥?duì)列隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。隊(duì)空條件為front==NULL73#include<iostream.h>#include“Queue.h”template<classE>structQueueNode{//隊(duì)列結(jié)點(diǎn)類(lèi)定義

private:

Edata; //隊(duì)列結(jié)點(diǎn)數(shù)據(jù)

QueueNode<E>*link;//結(jié)點(diǎn)鏈指針public:QueueNode(Ex=0,QueueNode<E>*next=NULL):data(x),link(next){}};

74鏈?zhǔn)疥?duì)列類(lèi)的定義template<classE>classLinkedQueue{

private:

QueueNode<E>*front,*rear;//隊(duì)頭、隊(duì)尾指針public:

LinkedQueue():rear(NULL),front(NULL){}

~LinkedQueue();

boolEnQueue(Ex);boolDeQueue(E&x);

boolgetFront(E&x);

voidmakeEmpty();//實(shí)現(xiàn)與~Queue()同

boolIsEmpty()const

{returnfront==NULL;

}};7576template<classE>LinkedQueue<E>::~LinkedQueue(){//析構(gòu)函數(shù)

QueueNode<E>*p;

while(front!=NULL){

//逐個(gè)結(jié)點(diǎn)釋放

p=front;front=front->link;

deletep;}};77template<classE>bool

LinkedQueue<E>::EnQueue(Ex){//將新元素x插入到隊(duì)列的隊(duì)尾

if(front==NULL){//創(chuàng)建第一個(gè)結(jié)點(diǎn)

front=rear=newQueueNode<E>(x);if(front==NULL)returnfalse;} //分配失敗

else{

//隊(duì)列不空,插入

rear->link=newQueueNode<E>(x);if(rear->link==NULL)returnfalse;rear=rear->link;}returntrue;};78template<classE>//如果隊(duì)列不空，將隊(duì)頭結(jié)點(diǎn)從鏈?zhǔn)疥?duì)列中刪去boolLinkedQueue<E>::DeQueue(E&x){

if(IsEmpty()==true)returnfalse;//判隊(duì)空

QueueNode<E>*p=front; x=front->data;front=front->link;

deletep;

returntrue; };template<classE>bool

LinkedQueue<E>::getFront(E&x){//若隊(duì)列不空，則函數(shù)返回隊(duì)頭元素的值

if(IsEmpty()==true)returnfalse; x=front->data;returntrue;};隊(duì)列的應(yīng)用：楊輝三角形(Pascal’striangle)逐行打印二項(xiàng)展開(kāi)式(a+b)i的系數(shù)79分析第i行元素與第i+1行元素的關(guān)系從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)i=2i=3i=401331014641012100110sts+t80從第i行數(shù)據(jù)計(jì)算并存放第i+1行數(shù)據(jù)121013310

146s=0t=1t=2t=1t=0t=1t=3t=3t=1t=0t=1s+ts=ts=ts=ts=ts=ts=ts=ts=ts+t

s+t

s+t

s+t

s+t

s+ts+ts+t8182利用隊(duì)列打印二項(xiàng)展開(kāi)式系數(shù)的算法#include

<stdio.h>#include

<iostream.h>#include"queue.h"voidYANGHVI(intn){Queueq(n+3);

//隊(duì)列初始化

q.makeEmpty();q.EnQueue(1);q.EnQueue(1);

ints=0,t;

for(int

i=1;i<=n;i++){//逐行計(jì)算

cout<<endl; q.EnQueue(0);

for(intj=1;j<=i+2;j++){//下一行q.DeQueue(t);q.EnQueue(s+t); s=t;

if(j!=i+2)cout<<s<<'';

}