第三章棧和隊列

1第三章 棧和隊列棧隊列優(yōu)先級隊列與表不同的是，它們都是限制存取位置的線性結(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ù)類型3棧的數(shù)組表示—順序棧#include<assert.h>template<classE>

classSeqStack:publicStack<E>{private:int

top;

//棧頂指針E*elements;

//棧元素數(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退?？諚opabdd退棧ctopabctoptoptopabdee退棧c退棧示例78順序棧的操作template<classE>voidSeqStack<E>::overflowProcess(){//私有函數(shù)：當(dāng)棧滿則執(zhí)行擴(kuò)充棧存儲空間處理

E*newArray=newE[2*maxSize]; //創(chuàng)建更大的存儲數(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）如何合理進(jìn)行?？臻g分配，以避免棧溢出或空間的浪費(fèi)？棧的鏈接存儲方式——鏈?zhǔn)綏?1兩個棧共享一個數(shù)組空間V[maxSize]設(shè)立棧頂指針數(shù)組

t[2]

和棧底指針數(shù)組

b[2]

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

i

個棧的棧頂與棧底初始

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

//棧頂指針退到棧底雙棧共享一個?？臻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棧滿問題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^1415鏈?zhǔn)綏?LinkedStack)類的定義#include<iostream.h>#include“stack.h”template<classE>structStackNode{//棧結(jié)點(diǎn)類定義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)綏ｎ惗x

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)綏ｎ惒僮鞯膶?shí)現(xiàn)template<classE>LinkedStack<E>::makeEmpty(){

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

StackNode<E>*p; while(top!=NULL) //逐個結(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;//?？辗祷?/p>

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;//棧空返回

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

returntrue; };21template<classE>ostream&operator<<(ostream&os,LinkedStack<E>&s){//輸出棧中元素的重載操作<<os<<“棧中元素個數(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)棧元素的編號為1,2,…,n時，可能的出棧序列有多少種？算術(shù)表達(dá)式有三種表示：中綴(infix)表示

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

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

<操作數(shù)><操作數(shù)><操作符>，如AB+；棧的應(yīng)用：表達(dá)式的計算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á)式中相鄰兩個操作符的計算次序為：優(yōu)先級高的先計算優(yōu)先級相同的自左向右計算當(dāng)使用括號時從最內(nèi)層括號開始計算

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

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

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

ABCD-

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

ABCD-

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

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

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

default:cin.putback(ch);

//將字符放回輸入流

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

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

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

doubleleft,right;boolresult;

result=Get2Operands(left,right);//退出兩個操作數(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中取兩個操作數(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種類型：

算術(shù)操作符

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

關(guān)系操作符

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

邏輯操作符

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

括號‘(’和‘)’

,

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

(

(

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

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

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

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

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

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

(2)

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

(1)

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

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

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

f

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

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

cout<<f->data<<

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

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

Hanoi(intn,

charA,

charB,

charC){//解決漢諾塔問題的算法

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什么時候運(yùn)用遞歸？子問題應(yīng)與原問題做同樣的事情，且更為簡單；把一個規(guī)模比較大的問題分解為一個或若干規(guī)模比較小的問題，分別對這些比較小的問題求解，再綜合它們的結(jié)果，從而得到原問題的解。

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

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

return(initialvalue);else//遞歸

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

遞歸調(diào)用

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

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

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

returntemp; }

voidmain(){ intn;

n=Factorial(4);

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

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

24

return3*2//返回

6

return

1//返回

1

return1*1//返回

1

return2*1//返回

2

5556遞歸過程改為非遞歸過程遞歸過程簡潔、易編、易懂遞歸過程效率低，重復(fù)計算多改為非遞歸過程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過程其他情形必須借助棧實(shí)現(xiàn)非遞歸過程計算斐波那契數(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)用樹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隊列（queue）定義隊列是只允許在一端刪除，在另一端插入的線性表允許刪除的一端叫做隊頭(front)，允許插入的一端叫做隊尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)62template<classE>classQueue{public:Queue(){};

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

～Queue(){};

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

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

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

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

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

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

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

intmaxSize; //隊列最大容量public:

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

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

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

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

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

boolgetFront(E&x);

//取隊頭元素值

void

makeEmpty(){front=rear=0;}

boolIsEmpty()const{returnfront==rear;}

boolIsFull()const

{returnrear==maxSize;}

intgetSize()const{returnrear-front;}

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

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

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

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

隊空時

rear==front

隊滿時

rear==maxSize

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

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

=0;隊空條件：front

==

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

循環(huán)隊列(CircularQueue)01234567front01234567front01234567frontrearAABCrearrear空隊列A進(jìn)隊B,C進(jìn)隊0123456701234567A退隊B退隊01234567D,E,F,G,H,I進(jìn)隊frontBCrearAfrontBCrearfrontCrearDEFGHI6970循環(huán)隊列操作的定義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){//若隊列不滿,則將x插入到該隊列隊尾,否則返回

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

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

returntrue; };

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

if(IsEmpty()==true)returnfalse;

x=elements[front];//先取隊頭

front=(front+1)%maxSize;

//再隊頭指針加一

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

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

x=elements[front]; //返回隊頭元素

returntrue;};

隊列的鏈接表示—鏈?zhǔn)疥犃嘘狀^在鏈頭，隊尾在鏈尾。鏈?zhǔn)疥犃性谶M(jìn)隊時無隊滿問題，但有隊空問題。隊空條件為front==NULL73#include<iostream.h>#include“Queue.h”template<classE>structQueueNode{//隊列結(jié)點(diǎn)類定義

private:

Edata; //隊列結(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)疥犃蓄惖亩xtemplate<classE>classLinkedQueue{

private:

QueueNode<E>*front,*rear;//隊頭、隊尾指針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){

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

p=front;front=front->link;

deletep;}};77template<classE>bool

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

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

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

else{

//隊列不空,插入

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

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

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

deletep;

returntrue; };template<classE>bool

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

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

<stdio.h>#include

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

//隊列初始化

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

ints=0,t;

for(int

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

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<<'';

}