數據結構A·第3章第3章堆棧和隊列

引言堆棧和隊列也是最常見的數據結構，在算法設計中經常使用，它們在邏輯上同線性表一樣，都是線性結構，差別在于：線性表可以在表的任意位置插入和刪除元素，而堆棧和隊列只能在表的端點插入和刪除元素。第3章堆棧和隊列內容提要

1、定義堆棧與隊列抽象數據類型

2、討論堆棧與隊列的順序表示方法

3、討論堆棧與隊列的鏈接表示方法

4、以表達式計算為例討論堆棧的應用

5、介紹遞歸的概念和遞歸算法3.1堆棧a0a1…ai…an-1入棧出棧bottomtop

圖3-1棧的示意圖堆棧（簡稱棧）的示意圖S=(a0,a1,…,an-1)課堂提要第3章堆棧和隊列3.1堆棧3.2隊列3.3表達式的計算3.4遞歸3.1堆棧3.1.1堆棧抽象數據類型

堆棧是后進先出（LastInFirstOut——LIFO）的動態線性數據結構。

1.堆棧的定義堆棧工作的演示ACB3.1堆棧3.1.1堆棧抽象數據類型

同時，堆棧也是是后進先出（LastInFirstOut——LIFO）的動態線性數據結構。

1.堆棧的定義ACB堆棧工作的演示3.1堆棧3.1.1堆棧抽象數據類型

ADTStack{數據:0個或多個元素的線性序列（a0,a1,...,an-1),其最大允許長度為ＭaxStackSize。其插入和刪除運算都限制在同一端進行，并遵循LIFO原則。運算:Create()：建立一個空棧。

Destroy()：撤消一個棧。

IsEmpty()：若棧空，則返回true;否則返回false。

IsFull()：若棧滿，則返回true;否則返回false。

Top(x)：返回棧頂元素。若操作成功，則返回true;否則返回false。

Push(x)：在棧頂插入元素x。

Pop()：從棧中刪除棧頂元素。

Clear():清除堆棧中全部元素。}

2.棧的抽象數據類型3.1堆棧3.1.1堆棧抽象數據類型

3.棧的C++模板抽象類程序3-1堆棧的C++類#include<iostream.h>template<classT>classStack{public:virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualboolTop(T&x)const=0;virtualboolPush(Tx)=0;virtualboolPop()=0;virtualvoidClear()=0;};3.1堆棧3.1.2棧的順序表示

1.棧的順序表示法an-1a1a0topn-110棧s圖3-2順序棧maxTop………一維數組s存儲棧中元素，maxTop+1為最大允許容量，top指示棧頂，top==-1表示空棧,top==maxTop表示棧滿。

S=(a0,a1,…,an-1)3.1堆棧3.1.2棧的順序表示

2.順序棧類template<classT>classSeqStack:publicStack<T>{public:SeqStack(intmSize);~SeqStack(){delete[]s;}boolIsEmpty()const{return(top==-1);}boolIsFull()const{return(top==MaxTop);}boolTop(T&x)const;boolPush(Tx);boolPop();voidClear(){top=-1;}private:inttop;//總是指向棧頂元素

intmaxTop;T*s;}an-1a1a0topn-110棧s圖3-2順序棧maxTop………3.1堆棧3.1.2棧的順序表示

3.動態一維數組描述順序棧類an-1a1a0topn-110棧s圖3-2順序棧maxTop………template<classT>classSeqStack:publicStack<T>{public:……private:intmaxTop;inttop;T*s;}3.1堆棧3.1.2棧的順序表示

3.動態一維數組描述順序棧類an-1a1a0topn-110棧s圖3-2順序棧maxTop………構造函數template<classT>SeqStack<T>::SeqStack(intmSize){maxTop=mSize-1;s=newT[mSize];top=-1;}析構函數SeqStack<T>::~SeqStack(intMaxSize){delete[]s;}3.1堆棧3.1.2棧的順序表示

4.在順序存儲表示下實現棧上定義的操作an-1a1a0topn-110棧s圖3-2順序棧maxTop………（1）取棧頂元素template<classT>boolSeqStack<T>::Top(T&x)const{if(IsEmpty()){//空棧處理

cout<<"Empty"<<endl;returnfalse;}x=s[top];returntrue;}3.1堆棧3.1.2棧的順序表示

4.在順序存儲表示下實現棧上定義的操作an-1a1a0topn-110棧s圖3-2順序棧maxTop………（2）進棧（壓入）template<classT>boolSeqStack<T>::Push(T&x){if(IsFull()){//溢出處理

cout<<"Overflow"<<endl;returnfalse;}s[++top]=x;returntrue;}3.1堆棧3.1.2棧的順序表示

4.在順序存儲表示下實現棧上定義的操作an-1a1a0topn-110棧s圖3-2順序棧maxTop………（3）出棧（彈出）template<classT>boolSeqStack<T>::Pop(){if(IsEmpty()){//空棧處理

cout<<"Underflow"<<endl;returnfalse;}top--;returntrue;}3.1堆棧3.1.3棧的鏈接表示

1.棧的鏈接表示法（鏈式棧）鏈式棧的定義和操作的實現類似于單鏈表。an-1a0…top∧圖3-3鏈式棧

an-2an-3不帶表頭結點的單鏈表課堂提要第3章堆棧和隊列3.1堆棧

3.1.1棧抽象數據類型

3.1.2棧的順序表示

3.1.3棧的鏈接表示3.2隊列3.3表達式的計算3.4遞歸3.1堆棧3.1.3棧的鏈接表示

2.在鏈接表示下實現棧上定義的操作an-1a0…top∧圖3-3鏈式棧

an-2an-3入棧操作push(Tx)Node<T>*q=newNode<T>;q->element=x;q->link=top;top=q;3.1堆棧3.1.3棧的鏈接表示

2.在鏈接表示下實現棧上定義的操作an-1a0…top∧圖3-3鏈式棧

an-2an-3出棧操作Pop()Node<T>*q=top;top=top->link;deleteq;3.2隊列3.1.3棧的鏈接表示課堂提要第3章堆棧和隊列3.1堆棧3.2隊列

3.2.1隊列抽象數據類型

3.2.2隊列的順序表示

3.2.3隊列的鏈接表示3.3表達式的計算3.4遞歸隊列的示意圖

Q=(a0,a1,…,an-1)a0a1…an-1frontrear入隊出隊3.2隊列3.2.1隊列抽象數據類型

1.隊列的定義隊列是限定在表的一端插入，在表的另一端刪除的線性數據結構。若隊列中無元素，則為空隊列隊尾——允許插入元素的一端隊頭——允許刪除元素的另一端Q=(a0,a1,…,an-1)課堂提要第3章堆棧和隊列3.1堆棧3.2隊列

3.2.1隊列抽象數據類型

3.2.2隊列的順序表示

3.2.3隊列的鏈接表示3.3表達式的計算3.4遞歸3.2隊列3.2.1隊列抽象數據類型

1.隊列的定義a0a1…an-1frontrear入隊出隊若給定隊列Q=(a0,a1,…,an-1)，則稱a0是隊頭元素，an-1是隊尾元素。元素a0,…,an-1依次入隊，出隊的順序與入隊相同，a0出隊后，a1才能出隊，因此又稱隊列為先進先出（FirstInFirstOut——FIFO）的動態線性數據結構。3.2隊列3.2.1隊列抽象數據類型

1.隊列的定義ACBrearfront隊列工作的演示(入隊)3.2隊列3.2.1隊列抽象數據類型

1.隊列的定義rearfront隊列工作的演示(出隊)ACB3.2隊列3.2.1隊列抽象數據類型

2.隊列的抽象數據類型ADTQueue{

數據:0個或多個元素的線性序列（a0,a1,…,an-1),其最大長度為MaxQueueSize。它插入在一端進行，而刪除在另一端進行，并遵循FIFO原則。運算:Create()：建立一個空隊列。

Destroy()：撤消一個隊列。

IsEmpty()：若隊列空，則返回true;否則返回false。

IsFull()：若隊列滿，則返回true;否則返回false。

Front(x)：在x中返回隊頭元素。操作成功返回true；否則返回false。

EnQueue(x)：在隊尾插入元素x。操作成功返回true；否則返回false。

DeQueue()：從隊列中刪除隊頭元素。操作成功返回true；否則返回falseClear():清除隊列中全部元素。}3.2隊列3.2.1隊列抽象數據類型

3.隊列的C++模板抽象類template<classT>classQueue{public:Queue(){};~Queue(){}; virtualboolEnQueue(constTx)=0;virtualboolDeQueue()=0;virtualboolFront(T&x)=0; virtualboolIsEmpty()const=0; virtualboolIsFull()const=0;virtualvoidClear()=0; };3.2隊列3.2.2隊列的順序表示

1.隊列的順序表示法課堂提要第3章堆棧和隊列3.1堆棧3.2隊列

3.2.1隊列抽象數據類型

3.2.2隊列的順序表示

3.2.3隊列的鏈接表示3.3表達式的計算3.4遞歸01234=maxSize-1(a)空隊列fr

圖中f為front,r為rear3.2隊列3.2.2隊列的順序表示

1.隊列的順序表示法

從(d)可以看到，當再有元素需要入隊時將產生“溢出”，然而隊列中尚有三個空元素單元，我們稱這種現象為“假溢出”。指針f指向隊首元素的前一個位置，指針r指向隊尾元素50403020(b)元素20，30，40，50入隊01234=maxSize-1fr50(c)元素20，30，40依次出隊01234=maxSize-1fr50(d)元素60入隊01234=maxSize-1fr603.2隊列3.2.2隊列的順序表示

2.循環隊列表示法

把數組從邏輯上看成是一個頭尾相連的環。（a）空隊列滿隊列front==rear實際仍有一個元素的空間未使用0fr12340f123420304050r3.2隊列3.2.2隊列的順序表示

2.循環隊列表示法注意r值的變化：

4+1=>00f123420304050r（b）元素20，30，40，50入隊列（c）元素20，30，40出隊列0f123450r（d）元素60，70入隊列0f123450r60703.2隊列3.2.2隊列的順序表示

2.循環隊列表示法

實現循環隊列操作：

(1)為使入隊和出隊實現循環，可以利用取余運算符%。

(2)隊頭指針進一：

front=(front+1)%maxSize；

(3)隊尾指針進一：

rear=(rear+1)%maxSize；

(4)空隊列：當front==rear時為空隊列，

(5)滿隊列：當(rear+1)%maxSize==front時為滿隊列。滿隊列時實際仍有一個元素的空間未使用。3.2隊列3.2.2隊列的順序表示

3.順序隊列類template<classT>classSeqQueue:publicQueue<T>{public:SeqQueue(intmSize);~SeqQueue(){delete[]q;}

boolIsEmpty()const；

boolIsFull()const；

boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear(){front=rear=0;}private:intfront,rear;intmaxSize;T*q;};0fr12343.2隊列3.2.2隊列的順序表示

4.動態一維數組描述順序隊列類template<classT>classSeqQueue:publicQueue<T>{public:……

private:intfront,rear;intmaxSize;T*q;}01…n-1…maxSize-1frontrearq……3.2隊列3.2.2隊列的順序表示

4.動態一維數組描述順序隊列類01…n-1…maxSize-1frontrearq……構造函數template<classT>SeqQueue<T>::SeqQueue(intmSize){//生成一個空隊列

maxSize=mSize;q=newT[maxSize];front=rear=0;}析構函數~SeqQueue(){delete[]q;}3.2隊列3.2.2隊列的順序表示

5.在順序存儲表示下實現隊列定義的操作template<classT>boolSeqQueue<T>::IsEmpty()const{returnfront==rear;}template<classT>boolSeqQueue<T>::IsFull()const{return(rear+1)%maxSize==front;}（1）判空（2）判滿3.2隊列3.2.2隊列的順序表示

5.在順序存儲表示下實現隊列定義的操作template<classT>boolSeqQueue<T>::Front(T&x){if(IsEmpty()){cout<<"empty"<<endl;returnfalse;}x=q[(front+1)%maxSize];returntrue;}（3）取隊列元素0f123420304050r3.2隊列3.2.2隊列的順序表示

5.在順序存儲表示下實現隊列定義的操作template<classT>boolSeqQueue<T>::EnQueue(Tx){if(IsFull()){cout<<"Full"<<endl;returnfalse;}q[(rear=(rear+1)%maxSize)]=x;returntrue;}（4）進隊列（插入）0f123420304050r元素50入隊列0f1234203040r3.2隊列3.2.2隊列的順序表示

5.在順序存儲表示下實現隊列定義的操作template<classT>boolSeqQueue<T>::DeQueue(){if(IsEmpty()){cout<<"Underflow"<<endl;returnfalse;}front=(front+1)%maxSize;returntrue;}（5）出隊列（刪除）0f123420304050r0f123450r

元素20，30，40出隊列3.2隊列3.2.3隊列的鏈接表示隊列的鏈接表示法（鏈式隊列）鏈式隊列的定義和操作的實現類似于單鏈表。課堂提要第3章堆棧和隊列3.1堆棧3.2隊列

3.2.1隊列抽象數據類型

3.2.2隊列的順序表示

3.2.3隊列的鏈接表示3.3表達式的計算3.4遞歸不帶表頭結點的單鏈表a0an-1…front∧圖3-3鏈式隊列

a1a2rear3.2隊列3.2.3隊列的鏈接表示隊列的鏈接表示法（鏈式隊列）a0an-1…front∧圖3-3鏈式隊列

a1a2rear入隊列EnQueue(Tx)Node<T>*q=newNode<T>;q->element=x;q->link=NULL;rear->link=q;rear=q;出隊列DeQueue()Node<T>*q=front;front=front->link;delq;3.3堆棧的應用—表達式計算3.3.1表達式課堂提要第3章堆棧和隊列3.1堆棧3.2隊列3.3表達式的計算

3.3.1表達式

3.3.2后綴表達式求值

3.3.3中綴表達式轉換為后綴表達式3.4遞歸

表達式：表達式習慣的書寫形式是一個雙目運算符位于兩個操作數之間，如a＋b;還有單目運算符，如I++和-a。條件運算符是C/C++語言中惟一的三目運算符。

中綴表達式：操作符在兩個操作數之間的表達式,如：a/(b-c)+d*e

前綴表達式：操作符放在兩個操作數之前的表達式,如：+/a-bc*de

后綴表達式：操作符放在兩個操作數之后的表達式（逆波蘭表達式）如：abc-/de*+3.3堆棧的應用—表達式計算逆波蘭式（ReversePolishnotation，RPN）

J.Lukasiewicz

19293.3堆棧的應用—表達式計算3.3.1表達式表3-1C++中部分操作符的優先級操作符優先級-,!7*,/,%6+,-5<,<=,>,>=4==,!=3&&2||1

有括號時先計算括號號中的表達式；高優先級先計算同級操作符計算：從左到右，或從右到左3.3堆棧的應用—表達式計算3.3.2后綴表達式求值比較中綴表達式及其對應的后綴表達式的例子表3.2中綴表達式和后綴表達式中綴表達式后綴表達式a*b+cab*c+a*b/cab*c/a*b*c*d*e*fab*c*d*e*f*a+(b*c+d)/eabc*d+e/+a*((b+c)/(d-e)-f)abc+de-/f-*a/(b-c)+d*eabc-/de*+課堂提要第3章堆棧和隊列3.1堆棧3.2隊列3.3表達式的計算

3.3.1表達式

3.3.2后綴表達式求值

3.3.3中綴表達式轉換為后綴表達式3.4遞歸3.3堆棧的應用—表達式計算3.3.2后綴表達式求值后綴表達式求值優點：1）無界限符；2）求值時無需考慮操作符的優先級。因此用后綴表達式求值計算簡便，在編譯程序中常用。利用棧很容易計算后綴表達式的值。為了方便算法的實現，在后綴表達式的后面，通常會加上1個后綴表達式的結束符“＃”。3.3堆棧的應用—表達式計算3.3.2后綴表達式求值后綴表達式求值算法:

（1）從左往右順序掃描后綴表達式；（2）遇到操作數就進棧；（3）遇到操作符就從棧中彈出兩個操作數，執行該操作符規定的運算；并將結果進棧；（4）重復上述操作，直到表達式結束。彈出棧頂元素即為結果。

3.3堆棧的應用—表達式計算3.3.2后綴表達式求值642-/32*+#棧操作遇到結束符，彈出棧頂元素9即為結果#96、3出棧，計算3+6，結果9進棧+632、3出棧，計算3*2，結果6進棧*2332進棧2333進棧332、6出棧，計算6/2，結果3進棧/262、4出棧，計算4-2，結果2進棧-2462進棧264

6掃描項表3.3后綴表達式的計算6進棧64進棧43.3堆棧的應用—表達式計算3.3.2后綴表達式求值642-/32*+#6-24/32*+#642=22利用棧計算后綴表達式值的演示3.3堆棧的應用—表達式計算3.3.2后綴表達式求值利用棧計算后綴表達式值的演示233642-/32*+#6-24/32*+#=3263.3堆棧的應用—表達式計算3.3.2后綴表達式求值利用棧計算后綴表達式值的演示33642-/32*+#6-24/32*+#=2663.3堆棧的應用—表達式計算3.3.2后綴表達式求值利用棧計算后綴表達式值的演示63=642-/32*+#6-24/32*+#9=9==>6/(4-2)+3*26

4

2

-

/

3

2

*

+=93.3堆棧的應用—表達式計算3.3.2后綴表達式求值在Linux系統中有后綴表達式計算器。$>dc43+p73.3堆棧的應用—表達式計算3.3.2后綴表達式求值舉例：模擬一個簡單的計算器假設該計算器可以接收后綴表達式，但只進行+、-、*、/和^運算。為實現計算器，定義一個計算器類。程序3.5計算器類#include”SeqStack.h”#include<math.h>classCalculator{public:Calculator(intmaxSize):s(maxSize){};//構造函數

voidRun();voidClear(s.Clear();)private:SeqStack<double>s;//私有數據成員是一個棧，用于存放操作數

voidPushOperand(double);//操作數進棧

boolGetOperands(double&,double&);//兩個操作數出棧

voidDoOperator(char);//操作符進行處理（遇到操作符時調用）};3.3堆棧的應用—表達式計算3.3.2后綴表達式求值舉例：模擬一個簡單的計算器成員函數的實現：voidCalculator::PushOperand(doubleop){s.Push(op);//操作數進棧}BOOLCalculator::GetOperands(double&op1,double&op2){//兩個操作數出棧

if(!s.Top(op1)){ cerr<<"Missingoperand!"<<endl;returnfalse;}s.Pop();if(!s.Top(op2)){ cerr<<"Missingoperand!"<<endl;returnfalse;}s.Pop();returntrue;}3.3堆棧的應用—表達式計算3.3.2后綴表達式求值舉例：模擬一個簡單的計算器voidCalculator::DoOperator(charoper)//遇到操作符時調用{boolresult;doubleoper1,oper2;result=GetOperands(oper1,oper2);//從棧中彈出2個操作數3.3堆棧的應用—表達式計算3.3.2后綴表達式求值舉例：模擬一個簡單的計算器if(result)//執行操作符oper指定的運算

switch(oper)//根據操作符做相應的運算，先出棧的操作數oper1{//放在操作符的右邊，后出棧的oper2放在左邊

case'+':s.Push(oper2+oper1);break;case'-':s.Push(oper2-oper1);break;case'*':s.Push(oper2*oper1);break;case'/':if(fabs(oper1)<1e-6){//如果分母為0，則做出錯處理

cerr<<"Divideby0!"<<endl; Clear();} elses.Push(oper2/oper1);break;case'^':s.Push(pow(oper2,oper1));break;}elseClear();}3.3堆棧的應用—表達式計算3.3.2后綴表達式求值舉例：模擬一個簡單的計算器voidCalculator::Run(){charc;doublenewop;while(cin>>c,c!='#'){//從輸入流試讀入一個字符，遇結束符結束

switch(c){//讀入的字符做如下處理

case'+':case'-':case'*':case'/':case'^':DoOperator(c);break;//是操作符則進行相應的計算

default:cin.putback(c);//如不是操作符，則將試讀入的字符放回輸入流

cin>>newop;//讀入一個操作數

PushOperand(newop);break;//操作數進棧

}}if(s.Top(newop))cout<<newop<<endl;//取棧頂元素，得結果輸出}3.3堆棧的應用—表達式計算3.3.2后綴表達式求值舉例：模擬一個簡單的計算器計算器類的應用程序：#include“calculator.h”constintSIZE=20;voidmain(){CalculatorCal(SIZE);Cal.Run();}輸入：642-/32*+#結果：93.3堆棧的應用—表達式計算3.3.3中綴表達式轉換為后綴表達式注意：只考慮左結合的雙目運算。每個表達式以“＃”號作為其結束標記。輸入中綴表達式由運算符、操作數、園括弧和‘＃’四種不同類型的項組成的序列輸出后綴表達式課堂提要第3章堆棧和隊列3.1堆棧3.2隊列3.3表達式的計算

3.3.1表達式

3.3.2后綴表達式求值

3.3.3中綴表達式轉換為后綴表達式3.4遞歸3.3堆棧的應用—表達式計算3.3.3中綴表達式轉換為后綴表達式棧內優先級isp(in-stackpriority)棧外優先級icp(incomingpriority)對未進棧的左括號賦以最高優先級，對已進棧的左括號賦以最低優先級。假定表達式的語法正確性檢查已在表達式轉換之前完成。3.3堆棧的應用—表達式計算3.3.3中綴表達式轉換為后綴表達式轉換步驟：（1）從左到右掃描中綴表達式，遇到#轉（6）；否則繼續；（2）遇到操作數直接輸出；（不進棧）（3）遇到“）”，則連續出棧輸出，直到遇到“（”為止（注意：“（”出棧但不輸出）；（4）若是其它操作符，則與棧頂的操作符比較優先級；若小于棧頂操作符的棧內優先級，則連續出棧輸出，直到大于等于棧頂操作符的棧內優先級結束，該操作符進棧；（5）轉（1）繼續；（6）輸出棧中剩余操作符（#除外）。3.3堆棧的應用—表達式計算3.3.3中綴表達式轉換為后綴表達式a(/中綴表達式:a/(b-c)+d*e后綴表達式:abc-/de*+bc-)d+*e#3.3堆棧的應用—表達式計算3.3.3中綴表達式轉換為后綴表達式中綴表達式:a/(b-c)+d*e后綴表達式:abc-/de*+a(/bc-d+*e#3.3堆棧的應用—表達式計算3.3.3中綴表達式轉換為后綴表達式中綴表達式:a/(b-c