第3章棧和隊列習題練習答案

設將整數依次進棧但只要出棧時棧非空則可將出棧操作按任何次序夾入其中請回答下述問題 
　　()若入出棧次序為Push() Pop()Push()Push() Pop() Pop( )Push() Pop( )則出棧的數字序列為何(這裡Push(i)表示i進棧Pop( )表示出棧)? 
　　()能否得到出棧序列和?並說明為什麼不能得到或者如何得到 
　　()請分析 的種排列中哪些序列是可以通過相應的入出棧操作得到的 

答
　　()出棧序列為
    ()不能得到序列因為要得到的出棧序列則應做Push()Pop()Push()Push    ()Push()Pop()這樣在棧頂在棧底所以不能得到的出棧序列能得到的出棧序列具體操作為Push() Pop()Push()Push()Push()Pop()Pop()Pop()
　　()在 的種排列中可通過相應入出棧操作得到的序列是
　　   
      不能得到的序列是
　　　　

鏈棧中為何不設置頭結點?
答
    鏈棧不需要在頭部附加頭結點因為棧都是在頭部進行操作的如果加了頭結點等於要對頭結點之後的結點進行操作反而使算法更復雜所以只要有鏈表的頭指針就可以了

循環隊列的優點是什麼? 如何判別它的空和滿? 

答
　　循環隊列的優點是它可以克服順序隊列的假上溢現象能夠使存儲隊列的向量空間得到充分的利用判別循環隊列的空或滿不能以頭尾指針是否相等來確定一般是通過以下幾種方法一是另設一布爾變量來區別隊列的空和滿二是少用一個元素的空間每次入隊前測試入隊後頭尾指針是否會重合如果會重合就認為隊列已滿三是設置一計數器記錄隊列中元素總數不僅可判別空或滿還可以得到隊列中元素的個數

設長度為n的鏈隊用單循環鏈表表示若設頭指針則入隊出隊操作的時間為何? 若只設尾指針呢? 
答
　　當只設頭指針時出隊的時間為而入隊的時間需要n因為每次入隊均需從頭指針開始查找找到最後一個元素時方可進行入隊操作若只設尾指針則出入隊時間均為因為是循環鏈表尾指針所指的下一個元素就是頭指針所指元素所以出隊時不需要遍歷整個隊列

指出下述程序段的功能是什麼? 
() void Demo(SeqStack *S){
　　　　int i; arr[] ; n= ;
　　　　while ( StackEmpty(S)) arr[n++]=Pop(S);
　　　　for (i= i< n; i++) Push(S arr[i]);
　　　} //Demo

() SeqStack S S tmp;
　　DataType x;
　　//假設棧tmp和S已做過初始化
　　while ( ! StackEmpty (&S))
　　　{
　　　　x=Pop(&S) ;
　　　　Push(&tmpx);
　　　}
　　while ( ! StackEmpty (&tmp) )
　　　{
　　　　x=Pop( &tmp); 
　　　　Push( &Sx);
　　　　Push( &S x);
　　　}

() void Demo( SeqStack *S int m) 
　　　{ // 設DataType 為int 型
　　　　SeqStack T; int i;
　　　　InitStack (&T);
　　　　while (! StackEmpty( S))
　　　　　if(( i=Pop(S)) !=m) Push( &Ti);
　　　　while (! StackEmpty( &T))
　　　　　{
　　　　　　i=Pop(&T); Push(Si);
　　　　　}
　　　}

()void Demo( CirQueue *Q)
　　　{ // 設DataType 為int 型
　　　　int x; SeqStack S;
　　　　InitStack( &S);
　　　　while (! QueueEmpty( Q ))
　　　　　{x=DeQueue( Q); Push( &Sx);}
　　　　while (! StackEmpty( &s))
　　　　　{ x=Pop(&S); EnQueue( Qx );}
　　　}// Demo

() CirQueue Q Q; // 設DataType 為int 型
　　int x i n= ;
　　 // 設Q已有內容 Q已初始化過
　　while ( ! QueueEmpty( &Q) ) 
　　　{ x=DeQueue( &Q ) ; EnQueue(&Q x); n++;}
　　for (i=; i< n; i++) 
　　　{ x=DeQueue(&Q) ; 
　　EnQueue( &Q x) ; EnQueue( &Q x);} 


答
　　()程序段的功能是將一棧中的元素按反序重新排列也就是原來在棧頂的元素放到棧底棧底的元素放到棧頂此棧中元素個數限制在個以內
　　()程序段的功能是利用tmp棧將一個非空棧s的所有元素按原樣復制到一個棧s當中去
　　()程序段的功能是利用棧T將一個非空棧S中值等於m的元素全部刪去
　　()程序段的功能是將一個循環隊列Q經過S棧的處理反向排列原來的隊頭變成隊尾原來的隊尾變成隊頭
　　()這段程序的功能是將隊列的所有元素復制到隊列中去但其執行過程是先把隊列的元素全部出隊進入隊列然後再把隊列的元素復制到隊列中

回文是指正讀反讀均相同的字符序列如abba和abdba均是回文但good不是回文試寫一個算法判定給定的字符向量是否為回文(提示將一半字符入棧) 

解
　　根據提示算法可設計為
　//以下為順序棧的存儲結構定義
　#define StackSize //假定預分配的棧空間最多為個元素
　typedef char DataType;//假定棧元素的數據類型為字符
　typedef struct{
　　DataType data[StackSize];
　　int top;
　}SeqStack; 

　int IsHuiwen( char *t)
　　{//判斷t字符向量是否為回文若是返回否則返回
　　　SeqStack s;
　　　int i len;
　　　char temp;
　　　InitStack( &s);
　　　len=strlen(t); //求向量長度
　　　for ( i=; i<len/; i++)//將一半字符入棧
　　　　Push( &s t[i]);
　　　while( !EmptyStack( &s))
　　　　{// 每彈出一個字符與相應字符比較
　　　　　temp=Pop (&s);
　　　　　if( temp!=S[i])  return ;// 不等則返回
　　　　　else i++;
　　　　} 
　　　return ; // 比較完畢均相等則返回
　　}

利用棧的基本操作寫一個將棧S中所有結點均刪去的算法void ClearStack( SeqStack *S)並說明S為何要作為指針參數? 
解 
　算法如下
　　void ClearStack (SeqStack *S)
　　　{ // 刪除棧中所有結點
　　　　S>Top = ; //其實只是將棧置空
　　　} 
　　因為要置空的是棧S如果不用指針來做參數傳遞那麼函數進行的操作不能對原來的棧產生影響系統將會在內存中開辟另外的單元來對形參進行函數操作結果等於什麼也沒有做所以想要把函數操作的結果返回給實參的話就只能用指針來做參數傳遞了

利用棧的基本操作 寫一個返回S中結點個數的算法 int StackSize( SeqStack S)並說明S為何不作為指針參數? 
解
　算法如下
　　int StackSize (SeqStack S)
　　　{//計算棧中結點個數
　　　　int n=;
　　　　if(!EmptyStack(&S))
　　　　　{
　　　　　　Pop(&S);
　　　　　　n++;
　　　　　}
　　　　return n;
　　　}
　　上述算法的目的只要得到S棧的結點個數就可以了並不能改變棧的結構所以S不用指針做參數以避免對原來的棧中元素進行任何改變系統會把原來的棧按值傳遞給形參函數只對形參進行操作最後返回元素個數

設計算法判斷一個算術表達式的圓括號是否正確配對 (提示 對表達式進行掃描凡遇到(就進棧遇)就退掉棧頂的(表達式被掃描完畢棧應為空 
解
　　根據提示可以設計算法如下
　int PairBracket( char *SR)
　　{//檢查表達式ST中括號是否配對
　　　int i;
　　　SeqStack S; //定義一個棧
　　　InitStack (&s);
　　　for (i=; i<strlen(SR) ; i++)
　　　　{ 
　　　　　if ( S[i]==( ) Push(&S SR[i]); //遇(時進棧
　　　　　if ( S[i]==) ) //遇)
　　　　　　if (!StackEmpty(S))//棧不為空時將棧頂元素出棧
　　　　　　　Pop(&s);
　　　　　　else return ;//不匹配返回
　　　　}
　　　if EmptyStack(&s) return ;// 匹配返回
　　　else return ;//不匹配返回
　　}

一個雙向棧S是在同一向量空間內實現的兩個棧它們的棧底分別設在向量空間的兩端 試為此雙向棧設計初始化InitStack ( S ) 入棧Push( S i x) 和出棧Pop( S i )等算法 其中i為 或 用以表示棧號 
解
　　雙向棧其實和單向棧原理相同只是在一個向量空間內好比是兩個頭對頭的棧放在一起中間的空間可以充分利用雙向棧的算法設計如下
　//雙向棧的棧結構類型與以前定義略有不同
　#define StackSize
From:http://tw.wingwit.com/Article/program/sjjg/201311/23985.html