第3章棧和隊(duì)列本章的基本內(nèi)容是：兩種特殊的線性表——棧和隊(duì)列從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限的線性表，他們的邏輯結(jié)構(gòu)相同。從抽象數(shù)據(jù)類型角度看，棧和隊(duì)列是兩種重要的抽象數(shù)據(jù)類型。

3.1棧棧的邏輯結(jié)構(gòu)（a1,a2,……,an）棧：限定僅在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底?？諚＃翰缓魏螖?shù)據(jù)元素的棧。

棧頂棧底a1a2a3入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧頂

3.1棧棧的邏輯結(jié)構(gòu)棧的操作特性：后進(jìn)先出a1a2a3入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂

3.1棧棧的邏輯結(jié)構(gòu)例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：棧的邏輯結(jié)構(gòu)

3.1棧棧底棧頂ab棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況1：

3.1棧棧底棧頂ab棧頂出棧序列：b情況2：例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)

3.1棧棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對表插入和刪除操作的位置進(jìn)行了限制，并沒有限定插入和刪除操作進(jìn)行的時(shí)間。例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況2：

3.1棧棧的抽象數(shù)據(jù)類型定義ADTStackData

棧中元素具有相同類型及后進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系Operation

InitStack

前置條件：棧不存在輸入：無功能：棧的初始化輸出：無后置條件：構(gòu)造一個(gè)空棧

3.1棧DestroyStack

前置條件：棧已存在輸入：無功能：銷毀棧輸出：無后置條件：釋放棧所占用的存儲空間Push

前置條件：棧已存在輸入：元素值x

功能：在棧頂插入一個(gè)元素x

輸出：如果插入不成功，拋出異常后置條件：如果插入成功，棧頂增加了一個(gè)元素棧的抽象數(shù)據(jù)類型定義

3.1棧Pop

前置條件：棧已存在輸入：無功能：刪除棧頂元素輸出：如果刪除成功，返回被刪元素值，否則，拋出異常后置條件：如果刪除成功，棧減少了一個(gè)元素GetTop

前置條件：棧已存在輸入：無功能：讀取當(dāng)前的棧頂元素輸出：若棧不空，返回當(dāng)前的棧頂元素值后置條件：棧不變棧的抽象數(shù)據(jù)類型定義

3.1棧Empty

前置條件：棧已存在輸入：無功能：判斷棧是否為空輸出：如果棧為空，返回1，否則，返回0

后置條件：棧不變endADT棧的抽象數(shù)據(jù)類型定義

3.1棧棧的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)順序棧——棧的順序存儲結(jié)構(gòu)如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲？

012345678a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top

3.1棧出棧：top減1進(jìn)棧：top加1?？眨簍op=-1

012345678a1topa2topa3top棧滿：top=MAX_SIZE-1棧的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)

3.1棧順序棧類的聲明constintMAX_SIZE=100;template<classDataType>class

seqStack{public:seqStack();~seqStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();boolEmpty();private:DataTypedata[MAX_SIZE];inttop;}

3.1棧順序棧的實(shí)現(xiàn)——入棧template<classDataType>voidseqStack<DataType>::Push(DataTypex){if(top==MAX_SIZE-1)throw“溢出”;

top++;data[top]=x;}操作接口：

voidPush(DataTypex);時(shí)間復(fù)雜度？data[++top]=x

3.1棧順序棧的實(shí)現(xiàn)——出棧template<classDataType>DataTypeseqStack<DataType>::Pop(){if(top==-1)throw“溢出”;

x=data[top--];

returnx;}操作接口：

DataTypePop();時(shí)間復(fù)雜度？

3.1棧兩棧共享空間解決方案1：直接解決：為每個(gè)棧開辟一個(gè)數(shù)組空間。解決方案2：

順序棧單向延伸——使用一個(gè)數(shù)組來存儲兩個(gè)棧在一個(gè)程序中需要同時(shí)使用具有相同數(shù)據(jù)類型的兩個(gè)棧，如何順序存儲這兩個(gè)棧？會出現(xiàn)什么問題？如何解決？

3.1棧兩棧共享空間：使用一個(gè)數(shù)組來存儲兩個(gè)棧，讓一個(gè)棧的棧底為該數(shù)組的始端，另一個(gè)棧的棧底為該數(shù)組的末端，兩個(gè)棧從各自的端點(diǎn)向中間延伸。兩棧共享空間

3.1棧棧1的底固定在下標(biāo)為0的一端；棧2的底固定在下標(biāo)為StackSize-1的一端。

top1和top2分別為棧1和棧2的棧頂指針；Stack_Size為整個(gè)數(shù)組空間的大?。▓D中用S表示）；a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1棧1底棧2底

3.1棧top1=-1什么時(shí)候棧1為空？a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1top1

3.1棧top1=-1什么時(shí)候棧1為空？a1

a2…aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1什么時(shí)候棧2為空？top2top2=Stack_Size

3.1棧top1=-1什么時(shí)候棧1為空？a1

a2……aitop1012…

…S-1兩棧共享空間top2bj

……b2

b1什么時(shí)候棧2為空？top2=Stack_Size什么時(shí)候棧滿？top2=top1+1

3.1棧constintStack_Size=100;template<classDataType>class

BothStack

{

public:BothStack();~BothStack();voidPush(inti,DataTypex);DataTypePop(inti);

DataTypeGetTop(inti);

boolEmpty(inti);

private:DataTypedata[Stack_Size];

inttop1,top2;};兩棧共享空間類的聲明

3.1棧1.如果棧滿，則拋出上溢異常；2.判斷是插在棧1還是棧2；2.1若在棧1插入，則2.1.1top1加1;

2.1.2在top1處填入x；2.2若在棧2插入，則2.2.1top2減1;

2.2.2在top2處填入x；兩棧共享空間的實(shí)現(xiàn)——插入操作接口：voidPush(inti,DataTypex);

3.1棧1.若是在棧1刪除，則

1.1若棧1為空棧，拋出下溢異常；

1.2刪除并返回棧1的棧頂元素；2.若是在棧2刪除，則

2.1若棧2為空棧，拋出下溢異常；

2.2刪除并返回棧2的棧頂元素；兩棧共享空間的實(shí)現(xiàn)——刪除操作接口：DataTypePop(inti);

3.1棧棧的鏈接存儲結(jié)構(gòu)及實(shí)現(xiàn)鏈棧：棧的鏈接存儲結(jié)構(gòu)firsta1a2an∧ai鏈棧需要加頭結(jié)點(diǎn)嗎？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。

3.1棧棧的鏈接存儲結(jié)構(gòu)及實(shí)現(xiàn)棧頂棧底鏈棧：棧的鏈接存儲結(jié)構(gòu)topanan-1a1∧firsta1a2an∧ai兩種示意圖在內(nèi)存中對應(yīng)同一種狀態(tài)，啟示？topa1an-1an∧棧頂棧底

3.1棧鏈棧的類聲明template<classDataType>classLinkStack{

public:LinkStack();

~LinkStack();

voidPush(DataTypex);DataTypePop();DataTypeGetTop();boolEmpty();private:Node<DataType>*top;}

3.1棧template<classDataType>voidLinkStack<DataType>

::Push(DataTypex){s=newNode<DataType>;s->data=x;s->next=top;top=s;}topanan-1a1∧鏈棧的實(shí)現(xiàn)——插入xstop操作接口：voidPush(DataTypex);

為什么沒有判斷棧滿？

3.1棧template<classDataType>DataTypeLinkStack<DataType>::Pop(){if(top==NULL)

throw"下溢";

x=top->data;p=top;top=top->next;

deletep;returnx;}鏈棧的實(shí)現(xiàn)——操作接口：DataTypePop();

topanan-1a1∧topp

top++可以嗎？

3.1棧順序棧和鏈棧的比較時(shí)間性能：相同，都是常數(shù)時(shí)間O(1)?？臻g性能：順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問題。鏈棧：沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時(shí)才會出現(xiàn)棧滿，但是每個(gè)元素都需要一個(gè)指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。

總之，當(dāng)棧的使用過程中元素個(gè)數(shù)變化較大時(shí)，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。

3.1棧3.2隊(duì)列隊(duì)列的邏輯結(jié)構(gòu)隊(duì)列：只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。允許插入（也稱入隊(duì)、進(jìn)隊(duì)）的一端稱為隊(duì)尾，允許刪除（也稱出隊(duì)）的一端稱為隊(duì)頭?？贞?duì)列：不含任何數(shù)據(jù)元素的隊(duì)列。（a1,a2,……,an）隊(duì)尾隊(duì)頭隊(duì)列的操作特性：先進(jìn)先出a1a2a3入隊(duì)隊(duì)尾隊(duì)頭出隊(duì)隊(duì)頭隊(duì)列的邏輯結(jié)構(gòu)3.2隊(duì)列隊(duì)列的抽象數(shù)據(jù)類型定義ADTQueueData

隊(duì)列中元素具有相同類型及先進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系Operation

InitQueue

前置條件：隊(duì)列不存在輸入：無功能：初始化隊(duì)列輸出：無后置條件：創(chuàng)建一個(gè)空隊(duì)列3.2隊(duì)列

DestroyQueue

前置條件：隊(duì)列已存在輸入：無功能：銷毀隊(duì)列輸出：無后置條件：釋放隊(duì)列所占用的存儲空間

EnQueue

前置條件：隊(duì)列已存在輸入：元素值x

功能：在隊(duì)尾插入一個(gè)元素輸出：如果插入不成功，拋出異常后置條件：如果插入成功，隊(duì)尾增加了一個(gè)元素隊(duì)列的抽象數(shù)據(jù)類型定義3.2隊(duì)列

DeQueue

前置條件：隊(duì)列已存在輸入：無功能：刪除隊(duì)頭元素輸出：如果刪除成功，返回被刪元素值后置條件：如果刪除成功，隊(duì)頭減少了一個(gè)元素

GetQueue

前置條件：隊(duì)列已存在輸入：無功能：讀取隊(duì)頭元素輸出：若隊(duì)列不空，返回隊(duì)頭元素后置條件：隊(duì)列不變隊(duì)列的抽象數(shù)據(jù)類型定義3.2隊(duì)列Empty

前置條件：隊(duì)列已存在輸入：無功能：判斷隊(duì)列是否為空輸出：如果隊(duì)列為空，返回1，否則，返回0

后置條件：隊(duì)列不變endADT隊(duì)列的抽象數(shù)據(jù)類型定義3.2隊(duì)列01234入隊(duì)出隊(duì)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)順序隊(duì)列——隊(duì)列的順序存儲結(jié)構(gòu)如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲？例：a1a2a3a4依次入隊(duì)a1a2a3a4rearrearrearrear入隊(duì)操作時(shí)間性能為O(1)3.2隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲？例：a1a2依次出隊(duì)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a1a2a3a4rear3.2隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲？例：a1a2依次出隊(duì)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a2a3a4rear3.2隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲？例：a1a2依次出隊(duì)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4rear出隊(duì)操作時(shí)間性能為O(n)3.2隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)如何改進(jìn)出隊(duì)的時(shí)間性能？放寬隊(duì)列的所有元素必須存儲在數(shù)組的前n個(gè)單元這一條件，只要求隊(duì)列的元素存儲在數(shù)組中連續(xù)的位置。設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)指針

3.2隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)例：a1a2a3a4依次入隊(duì)a1a2a3a4rearrearrearrear入隊(duì)操作時(shí)間性能仍為O(1)frontrear3.2隊(duì)列約定：隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素。例：a1a2依次出隊(duì)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a1a2a3a4rearfrontfrontfront出隊(duì)操作時(shí)間性能提高為O(1)3.2隊(duì)列例：a1a2依次出隊(duì)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4rearfront隊(duì)列的移動有什么特點(diǎn)？3.2隊(duì)列例：a1a2依次出隊(duì)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4rearfront整個(gè)隊(duì)列向數(shù)組下標(biāo)較大方向移動單向移動性3.2隊(duì)列假溢出：當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之后，隊(duì)列的空間就用盡了，盡管此時(shí)數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)繼續(xù)入隊(duì)會出現(xiàn)什么情況？01234入隊(duì)出隊(duì)a3a4rearfronta5rear3.2隊(duì)列循環(huán)隊(duì)列：將存儲隊(duì)列的數(shù)組頭尾相接。隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)如何解決假溢出？01234入隊(duì)出隊(duì)a3a4fronta5rearreara63.2隊(duì)列不存在物理的循環(huán)結(jié)構(gòu)，用軟件方法實(shí)現(xiàn)。求模：（4＋1）mod5＝0隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)如何實(shí)現(xiàn)循環(huán)隊(duì)列？01234入隊(duì)出隊(duì)a3a4frontreara63.2隊(duì)列如何判斷循環(huán)隊(duì)列隊(duì)空？隊(duì)空的臨界狀態(tài)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3rearfront3.2隊(duì)列如何判斷循環(huán)隊(duì)列隊(duì)空？執(zhí)行出隊(duì)操作隊(duì)空：front==rear隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3frontrearfront3.2隊(duì)列如何判斷循環(huán)隊(duì)列隊(duì)滿？隊(duì)滿的臨界狀態(tài)隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4fronta5reara63.2隊(duì)列如何判斷循環(huán)隊(duì)列隊(duì)滿？執(zhí)行入隊(duì)操作隊(duì)滿：front==rear隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)01234入隊(duì)出隊(duì)a3a4fronta5reara6reara73.2隊(duì)列方法一：修改隊(duì)滿條件，浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)數(shù)組中只有一個(gè)空閑單元；方法二：附設(shè)一個(gè)存儲隊(duì)列中元素個(gè)數(shù)的變量num，當(dāng)num=0時(shí)隊(duì)空，當(dāng)num=QueueSize時(shí)為隊(duì)滿；方法三：設(shè)置標(biāo)志flag，當(dāng)front=rear且flag=0時(shí)為隊(duì)空，當(dāng)front=rear且flag=1時(shí)為隊(duì)滿。如何確定不同的隊(duì)空、隊(duì)滿的判定條件？為什么要將隊(duì)空和隊(duì)滿的判定條件分開？隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)3.2隊(duì)列隊(duì)滿的條件：(rear+1)modQueueSize=front隊(duì)列的順序存儲結(jié)構(gòu)及實(shí)現(xiàn)(隊(duì)滿用方法一判斷)01234入隊(duì)rear<fronta3a4fronta5reara6出隊(duì)01234入隊(duì)rear>fronta3a4fronta5reara6出隊(duì)3.2隊(duì)列循環(huán)隊(duì)列類的聲明constintQueueSize=100;template<classDataType>classCirQueue{public:CirQueue()；~CirQueue()；

voidEnQueue(DataTypex);DataTypeDeQueue();

DataTypeGetQueue();

boolEmpty()；private:DataTypedata[QueueSize];

intfront,rear;};3.2隊(duì)列template<classDataType>voidCirQueue<DataType>::EnQueue(DataTypex){if((rear+1)%QueueSize==front)throw"上溢";

rear=(rear+1)%QueueSize;

data[rear]=x;}循環(huán)隊(duì)列的實(shí)現(xiàn)——入隊(duì)01234入隊(duì)出隊(duì)a3a4rearfronta5rear3.2隊(duì)列01234入隊(duì)a4a5a6出隊(duì)template<classDataType>DataTypeCirQueue<DataType>

::DeQueue(){if(rear==front)throw"下溢";

front=(front+1)%QueueSize;returndata[front];}循環(huán)隊(duì)列的實(shí)現(xiàn)——出隊(duì)frontrearfronta33.2隊(duì)列template<classDataType>DataTypeCirQueue<DataType>

::GetQueue(){if(rear==front)throw"下溢";

i=(front+1)%QueueSize;

returndata[i];}循環(huán)隊(duì)列的實(shí)現(xiàn)——讀隊(duì)頭元素01234入隊(duì)a4a5a6出隊(duì)frontreara3i3.2隊(duì)列隊(duì)列的鏈接存儲結(jié)構(gòu)及實(shí)現(xiàn)鏈隊(duì)列：隊(duì)列的鏈接存儲結(jié)構(gòu)隊(duì)頭指針即為鏈表的頭指針firsta1a2an∧如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲？rearfront3.2隊(duì)列隊(duì)列的鏈接存儲結(jié)構(gòu)及實(shí)現(xiàn)非空鏈隊(duì)列fronta1a2an∧rear空鏈隊(duì)列front∧rear3.2隊(duì)列鏈隊(duì)列類的聲明template<classDataType>classLinkQueue{public:LinkQueue();~LinkQueue();voidEnQueue(DataTypex);DataTypeDeQueue();

DataTypeGetQueue()；boolEmpty()；private:Node<DataType>*front,*rear;};3.2隊(duì)列操作接口：

LinkQueue();

算法描述：template<classDataType>LinkQueue<DataType>

::LinkQueue(){front=newNode<DataType>;front->next=NULL;rear=front;}鏈隊(duì)列的實(shí)現(xiàn)——構(gòu)造函數(shù)front∧rear3.2隊(duì)列xs鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)操作接口：

voidEnQueue(DataTypex);fronta1an∧rear∧rearfrontxs∧∧rearrear算法描述：s->next=NULL;rear->next=s;rear=s;如何沒有頭結(jié)點(diǎn)會怎樣？3.2隊(duì)列xs鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)操作接口：

voidEnQueue(DataTypex);fronta2an∧rear∧rear算法描述：s->next=NULL;rear->next=s;rear=s;如何沒有頭結(jié)點(diǎn)會怎樣？a13.2隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)操作接口：

voidEnQueue(DataTypex);front=rear=NULLxs∧rear算法描述：s->next=NULL;rear=s;front=s;如何沒有頭結(jié)點(diǎn)會怎樣？front算法描述：s->next=NULL;rear->next=s;rear=s;3.2隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)——入隊(duì)template<classDataType>voidLinkQueue<DataType>

::EnQueue(DataTypex){s=newNode<DataType>;s->data=x;s->next=NULL;rear->next=s;rear=s;}3.2隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)——出隊(duì)fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;3.2隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)——出隊(duì)fronta1a2an∧rearp考慮邊界情況：隊(duì)列中只有一個(gè)元素？fronta1p∧rear∧rear算法描述：if(p->next==NULL)rear=front;如何判斷邊界情況？3.2隊(duì)列template<classDataType>DataTypeLinkQueue<DataType>

::DeQueue(){if(rear==front)throw"下溢";p=front->next;x=p->data;front->next=p->next;if(p->next==NULL)rear=front;deletep;returnx;}鏈隊(duì)列的實(shí)現(xiàn)——出隊(duì)3.2隊(duì)列循環(huán)隊(duì)列和鏈隊(duì)列的比較時(shí)間性能:循環(huán)隊(duì)列和鏈隊(duì)列的基本操作都需要常數(shù)時(shí)間O(1)?？臻g性能:循環(huán)隊(duì)列：必須預(yù)先確定一個(gè)固定的長度，所以有存儲元素個(gè)數(shù)的限制和空間浪費(fèi)的問題。鏈隊(duì)列：沒有隊(duì)列滿的問題，只有當(dāng)內(nèi)存沒有可用空間時(shí)才會出現(xiàn)隊(duì)列滿，但是每個(gè)元素都需要一個(gè)指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。3.2隊(duì)列3.3應(yīng)用舉例3.3.1棧應(yīng)用的典型例子

——表達(dá)式求值的實(shí)現(xiàn)

遞歸

迷宮求解3.3.2隊(duì)列的應(yīng)用

——打印楊輝三角形733.3.1表達(dá)式求值算法表達(dá)式都是由操作數(shù)（operand）、運(yùn)算符（operator）和界限符（delimiter）組成的。討論簡單算術(shù)表達(dá)式的求值問題——只含加、減、乘、除四則運(yùn)算，所有的運(yùn)算對象均為數(shù)，并以“#”為結(jié)束符。常用算法——“算符優(yōu)先法”算符優(yōu)先法就是根據(jù)運(yùn)算符和界限符的優(yōu)先次序的規(guī)定來實(shí)現(xiàn)表達(dá)式求值的。算術(shù)四則運(yùn)算規(guī)則——運(yùn)算符的優(yōu)先次序規(guī)定：

1)先乘除，后加減；

2)從左算到右；

3)先括號內(nèi)，后括號外。算術(shù)表達(dá)式的三種表示算術(shù)表達(dá)式有三種表示：中綴(infix)表示

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

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

<操作數(shù)><操作數(shù)><操作符>，如AB+；中綴表達(dá)式和后綴表達(dá)式中綴表達(dá)式：運(yùn)算符在兩個(gè)運(yùn)算數(shù)中間的表達(dá)式。如：

1)X-Y2)

5+(6-4/2)*3

（字母表示運(yùn)算數(shù)）

后綴表達(dá)式：運(yùn)算符緊跟在兩個(gè)運(yùn)算數(shù)后面的表達(dá)式。如：

1)XY-2)5642/-3*+中綴到后綴中綴

5+(6-4/2)*3

到后綴5642/-3*+的轉(zhuǎn)變

5

(6-4/2)*3

+→5(6-4/2)

3*+

→56

4/2

-3*+→564

2

/-3*+后綴表達(dá)式的作用去掉中綴表達(dá)式的括號隱含中綴表達(dá)式的運(yùn)算次序運(yùn)算符左邊向右的計(jì)算，運(yùn)算數(shù)則是按其右邊最接近運(yùn)算符的先算的次序，運(yùn)算結(jié)果放回原處：計(jì)算過程5642/-3*+562–3*+

543*+512+

17

←最后結(jié)果應(yīng)用后綴表示計(jì)算表達(dá)式的值從左向右順序地掃描表達(dá)式，并用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。在后綴表達(dá)式的計(jì)算順序中已隱含了加括號的優(yōu)先次序，括號在后綴表達(dá)式中不出現(xiàn)。計(jì)算例利用棧的計(jì)算后綴表達(dá)式的過程棧

5642/-3*+

5/265-45345*125+

voidClear();//清空計(jì)算器

private:voidAddOperand(doublevalue);

//操作數(shù)入棧

BooleanGet2Operands(double&left,double&right);//從棧中退出兩個(gè)操作數(shù)

voidDoOperator(charop);//根據(jù)運(yùn)算符計(jì)算，結(jié)果入棧

Stack<double>s;//存放運(yùn)算數(shù)的工作棧};后綴表達(dá)式計(jì)算器的實(shí)現(xiàn)voidCalculator::AddOperand(doublevalue){s.Push(value);//操作數(shù)入棧

}BooleanCalculator::Get2Operands(double&left,double&right){

//從棧中退出兩個(gè)操作數(shù)

if(s.Empty()){cerr<<"MissingOperand!"<<endl;returnFalse;}right=s.Pop();if(s.Empty()){cerr<<"MissingOperand!"<<endl;returnFalse;}left=s.Pop();returnTrue;}

voidCalculator::DoOperator(charop){

//根據(jù)運(yùn)算符計(jì)算，結(jié)果入棧

doubleleft,right;Booleanresult;result=Get2Operands(left,right);if(result==True)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){ cerr<<"Dividedby0!"<<endl; s.MakeEmpty(); exit(0);}elses.Push(left/right);break; case'^':s.Push(pow(left,right));break; } elses.MakeEmpty();};voidCalculator::Run(){charch;doublenewoperand;while(cin>>ch,ch!='='){switch(ch){ case'+':case'-':case'*':case'/‘:case'^':DoOperator(ch);break; default:cin.putback(ch);cin>>newoperand; AddOperand(newoperand);break;}}

assert(!s.Empty());//若棧底無數(shù)，錯誤！終止

cout<<"Theresultis:"<<s.Pop()<<endl;

//輸出結(jié)果（棧底元素）

}voidCalculator::Clear(){s.MakeEmpty();}voidmain(){Calculatorcal(10);cal.Run();}中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式建立運(yùn)算符棧,并向棧底壓入#(若表達(dá)式以#結(jié)束)從左向右依次讀入表達(dá)式如果是運(yùn)算數(shù),則輸出如果是操作符則按下面操作如果棧外運(yùn)算符優(yōu)先級高于棧頂元素優(yōu)先級,棧外運(yùn)算符入棧如果棧外運(yùn)算符優(yōu)先級低于棧頂元素優(yōu)先級,則棧頂運(yùn)算符出棧輸出,直至棧頂運(yùn)算符優(yōu)先級低于棧外運(yùn)算符,棧外運(yùn)算符如棧.當(dāng)棧外為),棧內(nèi)運(yùn)算符退至(為止當(dāng)棧外為#,棧內(nèi)運(yùn)算符退至#為止算符優(yōu)先關(guān)系算符——運(yùn)算符和界限符的統(tǒng)稱，它們構(gòu)成的集合命名為OP。根據(jù)前述算術(shù)四則運(yùn)算三條規(guī)則，在運(yùn)算的每一步中，任意兩個(gè)相繼出現(xiàn)的算符op1和op2之間的優(yōu)先關(guān)系至多是下面三種關(guān)系之一:op1<op2op1的優(yōu)先權(quán)低于op2op1=op2op1的優(yōu)先權(quán)等于op2op1>op2op1的優(yōu)先權(quán)高于op2+－*/()#+>><<<>>－>><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=θ1θ2算符間的優(yōu)先級關(guān)系算符θ1在算符θ2前面。在算法中，相對應(yīng)于θ1在棧內(nèi)，θ2在棧外*+##*+#+##)/-(+#/-(+#(+#+#利用棧的轉(zhuǎn)換過程5+(6–4/2)*3#5642/-3*+

輸出棧外

-(+#中綴表達(dá)式求值算法將前面中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式，及后綴表達(dá)式計(jì)算兩過程結(jié)合起來，利用所給的+、-、*、/、（、）、和#的算術(shù)運(yùn)算符間的優(yōu)先級的關(guān)系，可計(jì)算中綴表達(dá)式。設(shè)置兩個(gè)棧：（1）操作數(shù)棧（OPRD）存放處理表達(dá)式過程中的操作數(shù)。（2）運(yùn)算符棧（OPTR）存放處理表達(dá)式過程中的運(yùn)算符。首先在運(yùn)算符棧中先在棧底壓入一個(gè)表達(dá)式的結(jié)束符“#”。運(yùn)算符棧（OPTR）操作數(shù)棧（OPRD）toptop#表達(dá)式求值算法計(jì)算表達(dá)式:5+(6-4/2)*3#的過程?！紫仍谶\(yùn)算符棧中先在棧底壓入一個(gè)表達(dá)式的結(jié)束符“#”。算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#

top表達(dá)式求值算法計(jì)算表達(dá)式:5+(6-4/2)*3#的過程?！x取表達(dá)式第一個(gè)字符，是數(shù)，壓入運(yùn)算數(shù)棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）top#5top表達(dá)式求值算法計(jì)算表達(dá)式:5+(6-4/2)*3#的過程?！x取表達(dá)式第2個(gè)字符“+”，優(yōu)先級：“+”>“#”，壓入算符棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）top#5+top表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–4/2)*3#的過程?！x取表達(dá)式第3個(gè)字符“(”優(yōu)先級：在棧外“(”>“+”，壓入算符棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–4/2)*3#的過程?！x取表達(dá)式第4個(gè)字符“6”壓入運(yùn)算數(shù)棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+6(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–4/2)*3#的過程?！x取表達(dá)式第5個(gè)字符“–”優(yōu)先級：在棧外“–”>棧內(nèi)“(”，壓入算符棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+6—(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–4/2)*3#的過程?！x取表達(dá)式第6個(gè)字符“4”壓入運(yùn)算數(shù)棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+46—(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/2)*3#的過程?！x取表達(dá)式第7個(gè)字符“/”優(yōu)先級：在棧外“/”>棧內(nèi)“–”，壓入算符棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+46/—(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/2)*3#的過程?！x取表達(dá)式第8個(gè)字符“2”壓入運(yùn)算數(shù)棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+426/—(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2)*3#的過程。

↑讀取表達(dá)式第9個(gè)字符“)”優(yōu)先級：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算,直至“(”算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+426/—(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2)*3#的過程。

↑讀取表達(dá)式第9個(gè)字符“)”優(yōu)先級：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算,直至“(”算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+426/—(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2)*3#的過程。↑讀取表達(dá)式第9個(gè)字符“)”優(yōu)先級：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算,直至“(”算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+426/—(22=表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2)*3#的過程?！x取表達(dá)式第9個(gè)字符“)”優(yōu)先級：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算,直至“(”算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+62—(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2)*3#的過程?！x取表達(dá)式第9個(gè)字符“)”優(yōu)先級：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算,直至“(”算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+62－(44=表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2)*3#的過程?！x取表達(dá)式第9個(gè)字符“)”優(yōu)先級：在棧外“)”<棧內(nèi)任何算法，算符出棧計(jì)算,直至“(”算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+4(表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2

)*3#的過程。↑讀取表達(dá)式第10個(gè)字符“*”優(yōu)先級：在棧外“*”>棧內(nèi)“+”，算符“*”入棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+4*表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2

)

*3#的過程?！x取表達(dá)式第11個(gè)字符“3”運(yùn)算數(shù)“3”入數(shù)棧算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+4*3表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2

)*3#的過程?！x取表達(dá)式第12個(gè)字符“#”優(yōu)先級：在棧外“#”<棧內(nèi)“*”，“*”出棧計(jì)算算符棧（OPTR）運(yùn)算數(shù)棧（OPRD）toptop#5+4*3表達(dá)式求值算法計(jì)算表達(dá)式:5+(6–

4

/

2

)*3#的過程。