1、第三章 棧與隊(duì)列山東財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院3.1 棧的基本概念棧是一種特殊的線性表，是操作受限的線性表，只能在表尾進(jìn)行插入或刪除操作。表首棧頂表尾棧底不含元素的空表稱空棧特點(diǎn)先進(jìn)后出FILO）后進(jìn)先出LIFO）棧棧S=(a1,a2,an)ana1a2.棧底棧底棧棧頂頂.出棧出棧進(jìn)棧進(jìn)棧棧的基本運(yùn)算Empty( )判斷棧空Full( )判斷棧滿Top( )返回棧頂元素Push(x)將元素x入棧Pop(x)出棧，并將棧頂元素存入x中棧的應(yīng)用舉例表達(dá)式或字符串的括號(hào)匹配問題算術(shù)表達(dá)式(x*(x+y)-z)算術(shù)表達(dá)式(x+y)*z)(對(duì)于給定表達(dá)式，從左到右逐字掃描，每個(gè)右括號(hào)和距他最近的沒有配對(duì)

2、的左括號(hào)匹配。將所有左括號(hào)依次放入棧中，遇到右括號(hào)，就與棧頂?shù)淖罄ㄌ?hào)配對(duì)，并將左括號(hào)出棧，若最后?？?，則匹配，若棧不為空，則不匹配。top= -1123450?？諚？諚ｍ斨羔槜ｍ斨羔榯op,指向?qū)嶋H棧頂指向?qū)嶋H棧頂后的空位置，初值為后的空位置，初值為-1top123450進(jìn)棧進(jìn)棧Atop出棧出棧棧滿棧滿BCDEF設(shè)數(shù)組維數(shù)為設(shè)數(shù)組維數(shù)為Mtop= -1,?？?，此時(shí)出棧，則下溢?？?，此時(shí)出棧，則下溢underflow)top=M-1,棧滿，此時(shí)入棧，則上溢棧滿，此時(shí)入棧，則上溢overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？諚？?.

3、2 用數(shù)組實(shí)現(xiàn)棧利用繼承派生棧類templateclass Stack：private list /利用list類派生棧類 public: Stack(int mx = 10)：list()max=mx; bool Empty( ) const return list():empty(); bool Full( ) const return size()=max; T Top( ) constreturn back(); Stack& Push(const T& x) push_back(x);return *this; Stack& Pop(T& x)pop_back(x);treturn

4、*this; pivate: int max;用數(shù)組實(shí)現(xiàn)?；惗xtemplateclass Stack public: Stack(int Max = 10); Stack( ) delete stack; bool Empty( ) const return top = -1; bool Full( ) const return top = = MaxTop; T Top( ) const; Stack& Push(const T& x); Stack& Pop(T& x); private: int top; /棧的棧頂元素所在數(shù)組分量的下標(biāo) int MaxTop; /數(shù)組能容納的棧元素

5、的最大個(gè)數(shù) T *stack; / 棧元素?cái)?shù)組 ; 構(gòu)造函數(shù)構(gòu)造一個(gè)空棧templateStack:Stack( int Max)MaxTop=max-1;Stack=new TMax;Top=-1;取棧頂元素 返回棧頂元素的值 template T Stack: Top( ) const If(Empty() throw outbounds(); Else return stacktop; 入棧將元素x入棧templateStack& Stack:Push(const T& x) if (Full() throw NoMem( ); stack+top = x; return *this;/

6、時(shí)間復(fù)雜度為O(1)出棧將棧頂元素出棧，并存入x中templateStack& Stack:Pop(T& x) if (Empty( ) throw OutOfBounds(); x = stacktop -; return *this; /時(shí)間復(fù)雜度為O(1) 棧的數(shù)組實(shí)現(xiàn)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)所列的7個(gè)基本運(yùn)算都可在O(1)的時(shí)間里完成，效率高。缺點(diǎn)為了使每個(gè)棧在算法運(yùn)行過程中不會(huì)溢出，通常要為每個(gè)棧預(yù)置一個(gè)較大的?？臻g。另一方面，由于各個(gè)棧的實(shí)際大小在算法運(yùn)行過程中不斷變化。經(jīng)常會(huì)發(fā)生其中一個(gè)棧滿，而另一個(gè)?？盏那樾?，空間利用率低。兩個(gè)棧共用一個(gè)數(shù)組的實(shí)現(xiàn)2個(gè)棧共享一個(gè)數(shù)組stack0.n利用棧底

7、位置不變的特性，可以將2個(gè)棧的棧底分別設(shè)在數(shù)組stack的兩端。然后各自向數(shù)組stack的中間伸展，如下圖。好處：提高空間利用率，減好處：提高空間利用率，減少棧發(fā)生上溢的可能性。少棧發(fā)生上溢的可能性。3.3 用指針實(shí)現(xiàn)棧鏈棧用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)鏈棧結(jié)點(diǎn)類定義template class Stack;template class Node friend class Stack; private: T data; Node *next; ;用指針實(shí)現(xiàn)棧定義templateclass Stack public: Stack( ) top = 0; /約定空棧時(shí)top = 0 Stack( ); b

8、ool Empty( ) const return top = 0; bool Full( ) const; T Top( ) const; Stack& Push(const T& x); Stack& Pop(T& x); private: Node *top; ; / 指向棧頂結(jié)點(diǎn)的指針析構(gòu)函數(shù)釋放鏈棧中的所有空間templateStack:Stack()Node*next;While(top)next=top-next；Delet top；top=next；取棧頂元素返回棧頂元素的值templateT Stack: Top( ) constIf(Empty() throw outbou

9、nds();Else return top-data; .棧底棧底toptopxp入棧將元素x入棧為元素x創(chuàng)建一個(gè)新結(jié)點(diǎn)，然后將新結(jié)點(diǎn)插入到原有的棧頂結(jié)點(diǎn)之前，并修改棧頂指針，使之指向新的棧頂結(jié)點(diǎn)。入棧將元素x入棧templateStack& Stack:Push(const T& x) if Full( ) throw NoMem( ); Node *p = new Node; p-data = x; p-next = top; top = p; return *this; /時(shí)間復(fù)雜度為O(1) top .棧底棧底topp出棧返回棧頂元素的值將棧頂元素存于x中，修改原有棧頂指針指向棧頂?shù)南?/p>

10、一個(gè)元素，作為新的棧頂，釋放原棧頂結(jié)點(diǎn)空間。出棧將棧頂元素出棧，并存入x中templateStack& Stack:Pop(T& x) if (Empty( ) throw OutOfBounds( ); x = top-data; Node *p = top; top = top-next; delete p; return *this; /時(shí)間復(fù)雜度為O(1) 棧的應(yīng)用表達(dá)式或字符串的括號(hào)匹配問題算術(shù)表達(dá)式(x*(x+y)-z)算術(shù)表達(dá)式(x+y)*z)(對(duì)于給定表達(dá)式，從左到右逐字掃描，每個(gè)右括號(hào)和距他最近的沒有配對(duì)的左括號(hào)匹配。將所有左括號(hào)依次放入棧中，遇到右括號(hào)，就與棧頂?shù)淖罄ㄌ?hào)配對(duì)

11、，并將左括號(hào)出棧，若最后棧空，則匹配，若棧不為空，則不匹配。括號(hào)匹配算法凡出現(xiàn)左括弧，則進(jìn)棧凡出現(xiàn)右括弧，首先檢查棧是否空若?？?，則表明該“右括弧多余否則和棧頂元素比較，若相匹配，那么“左括弧出棧”否則表明不匹配表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？眨瑒t表明表達(dá)式中匹配正確否則表明“左括弧有余表達(dá)式的計(jì)算 表達(dá)式的三種標(biāo)識(shí)方法： OP + S1 + S2 為前綴表示法 S1 + OP + S2 為中綴表示法 S1 + S2 + OP 為后綴表示法中綴表達(dá)式求值從左到右掃描表達(dá)式，若當(dāng)前讀入的是操作數(shù)，則進(jìn)操作數(shù)NS棧，若讀入的符號(hào)是運(yùn)算符，應(yīng)進(jìn)行判斷：若是“（”，進(jìn)運(yùn)算符棧；若是“）”，當(dāng)運(yùn)算符棧頂是“（”

12、，則彈出棧頂元素，繼續(xù)掃描下一符號(hào)。否則當(dāng)前讀入符號(hào)暫不處理，從操作數(shù)棧彈出兩個(gè)操作數(shù)，從運(yùn)算符棧彈出一個(gè)運(yùn)算符，生成運(yùn)算指令，結(jié)果送入操作數(shù)棧，繼續(xù)處理當(dāng)前讀入符號(hào)。若讀入的運(yùn)算符的優(yōu)先級(jí)大于運(yùn)算符棧頂?shù)膬?yōu)先級(jí)，則進(jìn)運(yùn)算符棧，繼續(xù)掃描下一符號(hào)；否則從操作數(shù)棧頂彈出兩個(gè)操作數(shù)，從運(yùn)算符棧彈出一個(gè)運(yùn)算符，生成運(yùn)算指令，把結(jié)果送入操作數(shù)棧。繼續(xù)處理剛才讀入的符號(hào)。中綴表達(dá)式求值實(shí)例 計(jì)算：2+4-3*6操作數(shù)操作數(shù) 運(yùn)算符運(yùn)算符24+操作數(shù)操作數(shù) 運(yùn)算符運(yùn)算符6-操作數(shù)操作數(shù) 運(yùn)算符運(yùn)算符6-18操作數(shù)操作數(shù) 運(yùn)算符運(yùn)算符-12操作數(shù)操作數(shù) 運(yùn)算符運(yùn)算符6-36*后綴表達(dá)式求值1、從左到右讀入表達(dá)

13、式一個(gè)字符2、若是操作數(shù)，壓入棧，轉(zhuǎn)43、若是運(yùn)算符，從棧中彈出2個(gè)數(shù)，將運(yùn)算 結(jié)果再壓入棧4、若表達(dá)式輸入完畢，棧頂即表達(dá)式值； 若表達(dá)式未輸入完，轉(zhuǎn)1后綴表達(dá)式求值實(shí)例 計(jì)算 4+3*5，其后綴表達(dá)式為435*+top4top43toptop415top735top193.4 隊(duì)列的基本概念隊(duì)列是一種特殊的線性表，是操作受限的線性表隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表隊(duì)尾(rear)允許插入的一端隊(duì)首(front)允許刪除的一端特點(diǎn)先進(jìn)先出FIFO）a1 a2 a3.an 入隊(duì)入隊(duì)出隊(duì)出隊(duì)frontrear隊(duì)列隊(duì)列Q=(a1,a2,an)隊(duì)列的基本運(yùn)算Empty(

14、 ): 判斷隊(duì)列空Full( ):判斷隊(duì)列滿Front( ): 返回隊(duì)首元素Back():返回隊(duì)尾元素Push(x):將元素x入隊(duì)列隊(duì)尾Pop(x):刪除隊(duì)首元素并存入x中3.5 用指針實(shí)現(xiàn)隊(duì)列template class Node friend class Queue; private: T data; Node *next; ;用指針實(shí)現(xiàn)隊(duì)列定義templateclass Queue public: Queue( ) front = rear = 0; Queue( ); bool Empty( ) const return (front) ? false : true); bool Fu

15、ll( ) const; T Front( ) const; T Back( ) const; Queue& Push(const T& x); Queue& Pop(T& x); private: Node *que_front; / 指向隊(duì)首結(jié)點(diǎn)的指針 Node *que_rear; /指向隊(duì)尾結(jié)點(diǎn)的指針 ; 析構(gòu)函數(shù)釋放隊(duì)列中的所有空間templateQueue:Queue()Node*next;While(que_front)next=que_front-next；Delet que_front；que_front=next；取隊(duì)首元素 返回隊(duì)首元素的值 template T Queu

16、e: Front( ) const If(Empty() throw outbounds(); Else return que_front-data; 取隊(duì)尾元素 返回隊(duì)尾元素的值 template T Queue: Back( ) const If(Empty() throw outbounds(); Else return que_rear-data; 在隊(duì)尾插入元素templateQueue& Queue:EnQueue(const T& x) if Full( ) throw NoMem( ); Node *p = new Node; / 創(chuàng)建一個(gè)新結(jié)點(diǎn) p-data = x; p-n

17、ext = 0; /在隊(duì)尾插入新結(jié)點(diǎn) if (front) rear-next = p; /隊(duì)列非空 else front = p; /空隊(duì)列 rear = p; return *this; /時(shí)間復(fù)雜度為O(1)刪除隊(duì)首元素templateQueue& Queue:DeQueue(T& x) if (Empty( ) throw OutOfBounds( ); x = front-data; / 將隊(duì)首元素存于x中 Node *p = front; front = front-next; delete p; / 刪除隊(duì)首結(jié)點(diǎn) return *this;/時(shí)間復(fù)雜度為O(1) frontrea

18、rx入隊(duì)入隊(duì)xfront rear空隊(duì)空隊(duì)fronty z入隊(duì)入隊(duì) xyrearzfrontrearx出隊(duì)出隊(duì)yzxfront rear空隊(duì)列front rearA進(jìn)隊(duì)進(jìn)隊(duì)Afront rearB進(jìn)隊(duì)進(jìn)隊(duì)A Bfront rearC, D進(jìn)隊(duì)進(jìn)隊(duì)A B C Dfront rearA退隊(duì)退隊(duì)B C Dfront rearB退隊(duì)退隊(duì)C Dfront rearE,F,G進(jìn)隊(duì)進(jìn)隊(duì)C D E F GC D E F Gfront rearH進(jìn)隊(duì)進(jìn)隊(duì),溢出溢出隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列的順序存儲(chǔ)方式存在問題設(shè)數(shù)組維數(shù)為M，那么：當(dāng)front=-1,rear=M-1時(shí)，再有元素入隊(duì)發(fā)生溢出溢出當(dāng)front-1,r

19、ear=M-1時(shí)，再有元素入隊(duì)發(fā)生溢出假溢出解決方案隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)浪費(fèi)時(shí)間循環(huán)隊(duì)列3.6 用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0;實(shí)現(xiàn)：利用“模運(yùn)算入隊(duì)： rear=(rear+1)%M; sqrear=x;出隊(duì)： front=(front+1)%M; x=sqfront;0M-11frontrear.隊(duì)滿隊(duì)空的判斷條件J4J5J6012345rearfrontJ4,J5,J6出隊(duì)出隊(duì)J7,J8,J9入隊(duì)入隊(duì)012345rearfrontJ4J5J6012345rearfrontJ9J8J7解決方案：解

20、決方案：1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間：少用一個(gè)元素空間： 隊(duì)空：隊(duì)空：front=rear 隊(duì)滿：隊(duì)滿：(rear+1)%M=front用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列隊(duì)列元素的類型：T循環(huán)數(shù)組的規(guī)模: MaxSize存放隊(duì)列的循環(huán)數(shù)組：T *queue 指示隊(duì)首元素的前一個(gè)位置的下標(biāo)：front;指示隊(duì)尾元素位置的下標(biāo)： rear;約定：front= rear時(shí)為空隊(duì)列，(rear + 1) % MaxSize = front) 時(shí)為滿隊(duì)列。用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列定義templateclass Queue public: Queue(int Max = 10); Queue( ) delete queue; bool Empty( ) const return front = rear; bool Full( ) const return (rear + 1) % MaxSize = front) ? 1 : 0); T Front( ) const; T Back( ) const; Queue& Push(c