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