數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第3章 棧與隊(duì)列

第3章 棧與隊(duì)列棧與隊(duì)列：限定操作的線性表。1 棧1.1 邏輯結(jié)構(gòu)1.1.1 定義限定只能在表的一端進(jìn)行插入、刪除的線性表。棧頂top，棧底bottom。后進(jìn)先出LIFO表(Last In First Out)1.1.2 基本操作進(jìn)棧Push/出棧Pop取棧頂元素GetTop判別?？読sEmpty/棧滿isFull1.1.3 應(yīng)用領(lǐng)域?qū)嵗骸斑M(jìn)制數(shù)轉(zhuǎn)換”、“表達(dá)式求值”、“函數(shù)調(diào)用關(guān)系”、“括號(hào)匹配問(wèn)題”、“漢諾塔問(wèn)題”、“迷宮問(wèn)題”、“九連環(huán)” 許多問(wèn)題的求解分為若干步驟，而當(dāng)前步驟的解答，是建立在后繼步驟的解答基礎(chǔ)上的。=問(wèn)題分解的步驟和求解的步驟次序恰好相反。1.2 順序棧/ 項(xiàng)目路徑：1順序棧/1.2.1 類的定義const int StackSize=10;template <class T> class SeqStack T m_DataStackSize; / 存放棧元素的數(shù)組 int m_Top; / 棧頂指針，表示下一個(gè)進(jìn)棧元素的下標(biāo)public: SeqStack( ); SeqStack(SeqStack<T> &Q); SeqStack( ); void Push(T e); / 進(jìn)棧 T Pop( ); / 出棧 T GetTop( ); / 取棧頂元素（不刪除） bool isEmpty( ); / 判斷棧是否為空;1.2.2 基本操作1.2.2.1 構(gòu)造/析構(gòu)template <class T>SeqStack<T>:SeqStack( ) / 構(gòu)造 m_Top=0; template <class T>SeqStack<T>:SeqStack(SeqStack<T> &Q) / 拷貝構(gòu)造 m_Top = Q.m_Top; for(int i=0; i<m_Top; i+) m_Datai=Q.m_Datai;template <class T>SeqStack<T>:SeqStack( ) / 析構(gòu)1.2.2.2 狀態(tài)判斷/ 判斷棧是否為空template <class T> bool SeqStack<T>:isEmpty( ) if(m_Top=0) return true; return false;/ 判斷棧是否為滿template <class T> bool SeqStack<T>:isFull( ) if(m_Top=StackSize) return true; return false;1.2.2.3 進(jìn)棧/出棧template <class T> void SeqStack<T>:Push(T e) / 進(jìn)棧 if(m_Top = StackSize) throw "上溢" m_Datam_Top=e; m_Top+;template <class T>T SeqStack<T>:Pop( ) / 出棧 if(m_Top=0) throw "下溢" m_Top-; return m_Datam_Top;template <class T> T SeqStack<T>:GetTop() / 取棧頂元素值if(m_Top=0) throw "下溢" return m_Datam_Top-1;1.3 順序棧的聯(lián)想缺點(diǎn)：空間浪費(fèi)思考：二棧合用同一順序空間？ / 項(xiàng)目路徑：1順序棧(2個(gè))/1.4 鏈棧/ 項(xiàng)目路徑：2鏈棧/1.4.1 類的定義template <class T>struct LinkNode T data; LinkNode<T> *next; ;template <class T>class LinkStack LinkNode<T> *m_Top; / 棧頂指針：鏈表頭指針public: LinkStack( ); LinkStack( ); void Push(T x); / 進(jìn)棧 T Pop( ); / 出棧 T GetTop( ); / 取棧頂元素（不刪除） bool isEmpty( ); / 判斷鏈棧是否為空棧;/ 棧滿：系統(tǒng)內(nèi)存不夠1.4.2 基本操作1.4.2.1 構(gòu)造/析構(gòu)template <class T>LinkStack<T>:LinkStack( ) m_Top = NULL; template <class T>LinkStack<T>:LinkStack( ) while(m_Top) LinkNode<T> *p=m_Top->next; delete m_Top; m_Top=p; 1.4.2.2 進(jìn)棧/出棧/ 進(jìn)棧template<class T> void LinkStack<T>:Push(T e) LinkNode<T> *newp = new LinkNode<T> newp->data = e; newp->next = m_Top; m_Top = newp; / 出棧template <class T> T LinkStack<T>:Pop( ) if(m_Top=NULL) throw "下溢" T e = m_Top->data; / 暫存棧頂元素 LinkNode<T> *p = m_Top; m_Top = m_Top->next; delete p; / 刪除首結(jié)點(diǎn) return e;2 棧的應(yīng)用 常識(shí)體驗(yàn)：函數(shù)調(diào)用棧2.1 進(jìn)制轉(zhuǎn)換示例數(shù)據(jù)： (1348)10=(2504)8，除8取余的過(guò)程：Nn div 8n mod 8134816841682102125202void Conversion(int n,int k) LinkStack<int> S; while( n!=0 ) S.Push(n%8); / 進(jìn)棧次序: 個(gè)位、十位 .高位 n=n/8; while(!S.isEmpty() cout<<S.Pop(); / 出棧次序: 高位.個(gè)位2.2 檢驗(yàn)括號(hào)匹配示例數(shù)據(jù)：Equal( "(a)(b) " ) : 0Equal( "(a)(b)" ) : 1Equal( "(a)(b)" ) : -1int Equal(char s) LinkStack<char> S; for(int i=0; si; i+) switch(si) case '(': S.Push(si); break; case ')': if(S.isEmpty() return(-1); / )多 S.Pop(); break; if( !S.isEmpty() ) return(1); / (多 return(0); / 完全匹配2.3 迷宮算法(思考) 2.4 后綴表達(dá)式求值中綴表達(dá)式后綴表達(dá)式A+B*CABC*+B*(D-C)+ABDC-*A+2*(3-4)+5234-*5+算符在運(yùn)算數(shù)之間算符在運(yùn)算數(shù)之后，沒(méi)有括號(hào)，算符沒(méi)有優(yōu)先級(jí)按“算符優(yōu)先級(jí)”求值按“順序計(jì)算法”求值輔助數(shù)據(jù)結(jié)構(gòu)：一個(gè)運(yùn)算數(shù)棧OPND。算法：自左向右掃描后綴表達(dá)式，直至遇到結(jié)束符為止。 遇算數(shù)：進(jìn)棧， 遇算符：退棧二數(shù)，運(yùn)算結(jié)果再進(jìn)棧，/ 只能處理1位數(shù)運(yùn)算數(shù)float PostExpression(char s) LinkStack<float> OPND; / 運(yùn)算數(shù)棧 for(int i=0; si; i+) if(si>='0' && si<='9') OPND.Push(si-'0'); else float opd1=OPND.Pop(); float opd2=OPND.Pop(); OPND.Push( Eval(opd2,si,opd1) ); return(OPND.GetTop(); /* 棧中唯一值：表達(dá)式值 */ float Eval(float a, char op, float b) switch(op) case '+': return(a+b); case '-': return(a-b); case '/': return(a/b); case '*': return(a*b); 2.5 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式示例數(shù)據(jù)： Mid: "2*(3-4)+5#" Post："234-*5+" 輔助數(shù)據(jù)結(jié)構(gòu)：一個(gè)運(yùn)算符棧OPTR。 算法：自左向右掃描Mid，直至遇到結(jié)束符#。 遇算數(shù)：加入Post。 遇算符op：取棧頂算符pre_op 若op>pre_op：op進(jìn)棧； 若op<pre_op：退棧，pre_op加入Post； 若op=pre_op：退棧。技術(shù)細(xì)節(jié)： #：優(yōu)先級(jí)最低的運(yùn)算符。 為保證第一個(gè)運(yùn)算符有“上一個(gè)運(yùn)算符”：OPTR.Push('#'); 為保證最后一個(gè)運(yùn)算符能被執(zhí)行： "3*5+2#"分析：Mid ="2*(3-4/5)+6#" = Post="2345/-*6+"c='*'c='('c='-' c='/' c=')'c=')'C=')'c='+'c='+'c='+'C='#'void MidToPost(char Mid,char Post) LinkStack<char> OPTR; / 運(yùn)算符棧 OPTR.Push('#'); int iMid=0,iPost=0; char c=MidiMid+; while(c!='#' | OPTR.GetTop()!='#') if(c>='0' && c<='9') PostiPost+=c; c=MidiMid+; continue; char pre_op=OPTR.GetTop(); switch( Precede(pre_op,c) ) / 比較算符優(yōu)先級(jí) case '<': / pre_op < c OPTR.Push(c); c=MidiMid+; break; case '=': OPTR.Pop(); c=MidiMid+; break; case '>': / pre_op > c OPTR.Pop(); PostiPost+=pre_op; PostiPost=0;/ 算符優(yōu)先級(jí)比較的代碼分析：先乘除，后加減；從左到右；先括號(hào)內(nèi)，再括號(hào)外。后算符前算符×()#>><<<>>>><<<>>×>>>><>>>>>><>>(<<<<<=)>>>>>>#<<<<<=char priority77= / + - * / ( ) # '>', '>', '<', '<', '<', '>', '>', / + '>', '>', '<', '<', '<', '>', '>', / - '>', '>', '>', '>', '<', '>', '>', / * '>', '>', '>', '>', '<', '>', '>', / / '<', '<', '<', '<', '<', '=', '0', / ( '>', '>', '>', '>', '0', '>', '>', / ) '<', '<', '<', '<', '<', '0', '=' / # ; int OpID(char op) switch (op) case '+' : return(0); case '-' : return(1); case '*' : return(2); case '/' : return(3); case '(' : return(4); case ')' : return(5); case '#' : return(6); char Precede(char op1,char op2) return(priorityOpID(op1)OpID(op2); 2.6 中綴表達(dá)式求值的算法示例數(shù)據(jù)： s: 1+2*(3+4*(5+6)#與2.5算法的相似處：當(dāng)前運(yùn)算是否立即執(zhí)行？必須先和“上一個(gè)運(yùn)算符”比較優(yōu)先級(jí)。 輔助數(shù)據(jù)結(jié)構(gòu)：運(yùn)算符棧OPTR，運(yùn)算數(shù)棧OPND 算法：自左向右掃描s，直至遇到結(jié)束符#。 遇算數(shù)：OPND.Push(c-'0'); 遇算符op：取棧頂算符pre_op 若op>pre_op：OPTR.Push(c); 若op<pre_op：OPTR.Pop(); OPND退棧兩次，計(jì)算，再進(jìn)棧 若op=pre_op：OPTR.Pop();跟蹤示例：3*(7-2)#c='3'C='*'c='('c='7'c='-'c='2'C=')'c=')'c='#'float MidExpression(char s) / 3*(7-2) LinkStack<float> OPND; / 運(yùn)算數(shù)棧 LinkStack<char> OPTR; OPTR.Push('#'); / 運(yùn)算符棧 int i=0; while(si!='#' | OPTR.GetTop()!='#') char c=si; if(c>='0' && c<='9') OPND.Push(c-'0'); i+; continue; char pre_op=OPTR.GetTop(); switch( Precede(pre_op, c) ) case '<': / pre_op < c OPTR.Push(c); i+; break; case '=': OPTR.Pop(); i+; break; case '>': / pre_op > c 執(zhí)行pre_op OPTR.Pop(); float opd1=OPND.Pop(); float opd2=OPND.Pop(); OPND.Push( Eval(opd2,pre_op,opd1) ); return(OPND.GetTop(); 測(cè)試案例："#"， "3#"，"3+5#"，"3+5+2#""3*5+2#"， "3+5*2#"，"(3+5)*2#"， "(3+5)*(2+1)#"，"(3+5)/2+1)*2#" 作業(yè)與上機(jī)實(shí)現(xiàn)棧類和中綴表達(dá)式求值功能。層次1：運(yùn)算數(shù)可以實(shí)數(shù)、負(fù)數(shù)層次2：表達(dá)式語(yǔ)法檢查、報(bào)錯(cuò)誤位置層次3：多個(gè)表達(dá)式依次求值（含變量）層次4：超長(zhǎng)運(yùn)算數(shù)的表達(dá)式求值附錄：九連環(huán)的玩法void down_1(int n) printf("%2ddown,",n); /下第n個(gè)環(huán)void down_12() printf("12down,"); /下1、2環(huán)void up_1(int n) printf("%2dup, ",n); /上第n個(gè)環(huán)void up_12() printf("12up, "); /上1、2環(huán)void huan_down(int n) /下前n個(gè)環(huán) if(n=1) down_1(n); return; if(n=2) down_12(); return; huan_down(n-2); down_1(n); huan_up(n-2); huan_down(n-1);void huan_up(int n) /上前n個(gè)環(huán) if(n=1) up_1(n); return; if(n=2) up_12(); return; huan_up(n-1); huan_down(n-2); up_1(n); huan_up(n-2);/打印下九連環(huán)的步驟main() huan_down(9); 3 隊(duì)列3.1 邏輯結(jié)構(gòu)只能在一端(隊(duì)尾rear)插入，在另一端(隊(duì)頭front)刪除的線性表。先進(jìn)先出表FIFO(First In First Out)基本操作：進(jìn)隊(duì)列Enter/出隊(duì)列Leave 判別隊(duì)列空isEmpty/隊(duì)列滿isFull應(yīng)用領(lǐng)域：排隊(duì)模型。排隊(duì)問(wèn)題無(wú)處不在，各種服務(wù)行業(yè)、甚至生產(chǎn)管理中都存在排隊(duì)問(wèn)題。3.2 鏈隊(duì)列/ 項(xiàng)目路徑：3鏈隊(duì)列/ 3.2.1 類的定義template <class T>struct LinkNode T data; LinkNode<T> *next; ;template <class T>class LinkQueue LinkNode<T> *m_Front; / 隊(duì)頭指針 LinkNode<T> *m_Rear; / 隊(duì)尾指針public: LinkQueue( ); LinkQueue( ); void Enter(T e); / 進(jìn)隊(duì)列 T Leave( ); / 出隊(duì)列 T GetFront( ); / 取隊(duì)列的隊(duì)頭元素 bool isEmpty( ); / 判斷隊(duì)列是否為空;3.2.2 基本操作3.2.2.1 構(gòu)造/析構(gòu)template <class T>LinkQueue<T>:LinkQueue() m_Front = m_Rear = NULL; template <class T>LinkQueue<T>:LinkQueue( ) /* 銷毀隊(duì)列 */ 3.2.2.2 進(jìn)/出隊(duì)列/ 進(jìn)隊(duì)列template <class T> void LinkQueue<T>:Enter(T e) LinkNode<T> *newp = new LinkNode<T> newp->data=e; newp->next=NULL; if(m_Front=NULL) m_Front=m_Rear=newp; else m_Rear->next=newp; m_Rear=newp; / 出隊(duì)列template <class T>T LinkQueue<T>:Leave() if(m_Front=NULL) throw "下溢" LinkNode<T> *p=m_Front; T e=p->data; /暫存隊(duì)頭元素 m_Front=p->next; delete p; if(m_Front=NULL) m_Rear=NULL; return e;/取隊(duì)頭元素template <class T> T LinkQueue<T>:GetFront() if(m_Front=NULL) throw "下溢" return m_Front->data; 3.2 順序隊(duì)列/ 項(xiàng)目路徑：4循環(huán)隊(duì)列/3.2.1 類的定義const int QueueSize=6; / 隊(duì)列存儲(chǔ)空間的長(zhǎng)度template <class T> class CirQueue T m_DataQueueSize; / 存放隊(duì)列元素的數(shù)組 int m_Front; / 隊(duì)頭指針 int m_Rear; / 隊(duì)尾指針public: CirQueue( ); CirQueue( ); void Enter(T e); / 進(jìn)隊(duì)列 T Leave( ); / 出隊(duì)列 T GetFront( ); / 取隊(duì)頭元素（不刪除） bool isEmpty( ); / 判斷隊(duì)列是否為空 bool isFull( ); / 判斷隊(duì)列是否為滿; 3.2.2 隊(duì)頭/尾指針的取值討論=循環(huán)隊(duì)列 以往的常識(shí)：進(jìn)隊(duì)列m_Rear+； 出隊(duì)列m_Front+ 常識(shí)中隱藏了陷阱：假溢出！ 循環(huán)隊(duì)列： 進(jìn)隊(duì)列m_Rear =(m_Rear +1)% QueueSize； 出隊(duì)列m_Front=(m_Front+1)% QueueSize； 約定：m_Rear下一個(gè)進(jìn)隊(duì)列元素的位置m_Front隊(duì)列不空時(shí)，指向首元素；隊(duì)列為空時(shí)，等于rear隊(duì)列空時(shí)m_Front=m_Rear隊(duì)列滿時(shí)(m_Rear+1) % QueueSize=m_Front=必須浪費(fèi)一個(gè)結(jié)點(diǎn)空間3.2.3 基本操作3.2.3.1 構(gòu)造/析構(gòu)template <class T>CirQueue<T>:CirQueue( ) m_Front = m_Rear = 0; template <class T>CirQueue<T>:CirQueue( ) 3.2.3.2 進(jìn)/出隊(duì)列/ 進(jìn)隊(duì)列template <class T> void CirQueue<T>:Enter(T e) if(m_Rear+1) % QueueSize=m_Front) throw "上溢" m_Datam_Rear = e; m_Rear = (m_Rear+1) % QueueSize; / 出隊(duì)列template <class T> T CirQueue<T>:Leave() if(m_Rear=m_Front) throw "下溢" T e = m_Datam_Front; m_Front = (m_Front+1) % QueueSize; return e;/ 隊(duì)列長(zhǎng)度template <class T> int CirQueue<T>:Length() return (m_Rear-m_Front+QueueSize)% QueueSize; 3.2.4 循環(huán)隊(duì)列的其他設(shè)計(jì)方案方法一：增加成員變量m_Flag （0:非滿，1:非空）方法二：增加成員變量m_Length（表示隊(duì)列長(zhǎng)度）4 隊(duì)列的實(shí)例：離散事件的模擬4.1 逐行打印二項(xiàng)展開式(a + b)n的系數(shù)(楊輝三角形)void YANGVI(int n, vector<int> &coefs) LinkQueue<int> Q; / 整數(shù)隊(duì)列 Q.Enter(1); Q.Enter(1); /第1行 for(int i=2; i<=n; i+) / 逐行計(jì)算 Q.Enter(1); int e1=Q.Leave(); for(int j=1; j<i; j+) int e2=Q.Leave(); Q.Enter(e1+e2); e1=e2; Q.Enter(1); for(i=0; !Q.isEmpty(); i+) coefs.push_back( Q.Leave() );4.2 最簡(jiǎn)單的排隊(duì)問(wèn)題某加油站只有一臺(tái)加油機(jī)，平均為每輛車加油需要5分鐘，假定一個(gè)小時(shí)內(nèi)，有20輛車隨機(jī)進(jìn)入加油站加油，計(jì)算每輛車的平均等待時(shí)間。/ ServiceTime: 每輛車加油需要的時(shí)間/ TotalTime: 總的時(shí)間段/ n: 在TotalTime內(nèi),n輛車隨機(jī)進(jìn)入加油站/ 返回平均等待時(shí)間float OilStation(int n,int TotalTime,float ServiceTime) / 生成模擬數(shù)據(jù) vector<float> ArriveTimes; for(int i=0; i<n; i+) ArriveTimes.push_back(rand()%TotalTime); sort( ArriveTimes.begin(), ArriveTimes.end() ); / 模擬數(shù)據(jù)全部進(jìn)隊(duì)列 LinkQueue<float> Q; for(i=0; i<n; i+) Q.Enter(ArriveTimesi); / 出隊(duì)列，仿佛享受加油站的服務(wù) float BeginOilTime=0, WaitTime=0; while( !Q.isEmpty() ) float ArriveTime=Q.Leave(); if(BeginOilTime > ArriveTime) WaitTime+=BeginOilTime - ArriveTime; / 需要等待 else BeginOilTime = ArriveTime; / 不需等待 BeginOilTime += ServiceTime; / 加油機(jī)為下輛車加油的時(shí)刻 return WaitTime/n;思考：加油站有二臺(tái)加油機(jī)的情形？有k臺(tái)加油機(jī)的情形？4.3 稍微復(fù)雜一些的排隊(duì)問(wèn)題銀行營(yíng)業(yè)所有n種業(yè)務(wù)，每類業(yè)務(wù)的服務(wù)時(shí)間是Ti，每種業(yè)務(wù)量是Ki/日。問(wèn)每類業(yè)務(wù)應(yīng)該設(shè)置幾個(gè)服務(wù)窗口？4.4 優(yōu)先級(jí)隊(duì)列(Priority Queue) 優(yōu)先級(jí)：數(shù)據(jù)元素的某個(gè)值。 進(jìn)隊(duì)列：按次序從隊(duì)尾進(jìn)。 出隊(duì)列：取隊(duì)列中優(yōu)先權(quán)最高的元素。5 棧、隊(duì)列的習(xí)題5.1 進(jìn)棧出棧的組合問(wèn)題（初級(jí)） 已知操作次序：push(1); pop(); push(2); push(3); pop(); pop( ); push(4); pop( ); 請(qǐng)寫出出棧序列。 設(shè)進(jìn)棧次序固定為push(1); push(2); push(3); push(4); 請(qǐng)分析1、2、3、4的24種排列中，哪些序列可以通過(guò)出棧操作實(shí)現(xiàn)，哪些不能實(shí)現(xiàn)？12341243132413421423 X143221342143231423412413 X24313124 X3142 X321432413412 X342141234132 X4213 X4231 X4312 X4321 X5.2 兩個(gè)棧組合一個(gè)隊(duì)列的問(wèn)題/ 項(xiàng)目路徑：5兩個(gè)鏈棧組合一個(gè)隊(duì)列/a0,ai進(jìn)隊(duì)列a0出隊(duì)列ai+1,an-1進(jìn)隊(duì)列a1,ai出隊(duì)列ai+1出隊(duì)列template <class T>class LinkQueue LinkStack<T> S1,S2;public: LinkQueue( ) LinkQueue( ) void Enter(T e); / 進(jìn)隊(duì)列 T Leave( ); / 出隊(duì)列;template <class T> void LinkQueue<T>:Enter(T e) / 進(jìn)隊(duì)列 S1.Push(e); template <class T> T LinkQueue<T>:Leave( ) / 出隊(duì)列 T e; if( !S2.isEmpty() ) return( S2.Pop() ); while( !S1.isEmpty() ) S2.Push( S1.Pop() ); return( S2.Pop() );5.3 進(jìn)棧出棧的組合問(wèn)題（高級(jí)）已知進(jìn)棧次序?yàn)?n，要求窮舉出所有可能的出棧序列。/ 項(xiàng)目路徑：6棧的棧/5.3.1 數(shù)據(jù)結(jié)構(gòu)小棧SeqStack<int> s;特殊的數(shù)據(jù)成員m_Output：儲(chǔ)存出棧序列大棧SeqStack<SeqStack<int> > S;5.3.2 算法思想：取出大棧中的小棧，進(jìn)行“進(jìn)?！?、“出?！弊兓?，再次進(jìn)棧。當(dāng)某小棧已經(jīng)進(jìn)棧n次、出棧n次時(shí)，其中的數(shù)據(jù)成員m_Output就已儲(chǔ)存了一種出棧序列。5.3.3 算法步驟初始狀態(tài)：s.Push(1); S.Push(s);當(dāng)大棧不空時(shí)，循環(huán)執(zhí)行以下語(yǔ)句：大棧出棧，得s=S.Pop(), 記s的進(jìn)棧次數(shù)為k； 若k=n && s.isEmpty(), 執(zhí)行s.Output()，輸出一種組合序列，轉(zhuǎn)； 若k<n，進(jìn)棧變化：s1=s，s1的下個(gè)數(shù)進(jìn)棧，s1進(jìn)大棧； 若s不空，出棧變化：s2=s，s2出棧，s2進(jìn)大棧； 轉(zhuǎn)5.3.4 算法結(jié)果分析i個(gè)數(shù)序列個(gè)數(shù)Si第1段Ai,1第2段Ai,2第3段Ai,3第4段Ai,4第5段Ai,5第6段Ai,6第7段Ai,7第8段Ai,8第9段Ai,9第10段Ai,102211352214145531542141494161324242281451742913213290482061814304294292971657527719486214301430100157227511035811016796486248623432200210014291544491 3-25