改寫順序棧的進(jìn)棧成員函數(shù)Push

1、4-1 改寫順序棧的進(jìn)棧成員函數(shù)Push (x )，要求當(dāng)棧滿時(shí)執(zhí)行一個(gè)stackFull ( )操作進(jìn)行棧滿處理。其功能是：動(dòng)態(tài)創(chuàng)建一個(gè)比原來的棧數(shù)組大二倍的新數(shù)組，代替原來的棧數(shù)組，原來?xiàng)?shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置?！窘獯稹縯emplate<class Type>void stack<Type> : push ( const Type & item ) if ( isFull ( ) ) stackFull ( );/棧滿，做溢出處理elements +top = item;/進(jìn)棧template<class Type> voi

2、d stack<Type> : stackFull ( ) Type * temp = new Type 3 * maxSize ;/創(chuàng)建體積大二倍的數(shù)組for ( int i = 0; i <= top; i+ ) /傳送原數(shù)組的數(shù)據(jù)tempi = elementsi;delete elements; /刪去原數(shù)組maxSize *= 3; /數(shù)組最大體積增長二倍elements = temp;/新數(shù)組成為棧的數(shù)組空間4-2 鐵路進(jìn)行列車調(diào)度時(shí), 常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，如右圖所示。試問：(1) 設(shè)有編號(hào)為1,2,3,4,5,6的六輛列車, 順序開入棧式結(jié)構(gòu)的站臺(tái),

3、則可能的出棧序列有多少種?(2) 若進(jìn)站的六輛列車順序如上所述, 那么是否能夠得到435612, 325641, 154623和135426的出站序列, 如果不能, 說明為什么不能; 如果能, 說明如何得到(即寫出"進(jìn)棧"或"出棧"的序列)?！窘獯稹?1) 可能的不同出棧序列有 種。(2) 不能得到435612和154623這樣的出棧序列。因?yàn)槿粼?, 3, 5, 6之后再將1, 2出棧，則1, 2必須一直在棧中，此時(shí)1先進(jìn)棧，2后進(jìn)棧，2應(yīng)壓在1上面，不可能1先于2出棧。154623也是這種情況。出棧序列325641和135426可以得到。356224

4、4 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 1354264-3 試證明：若借助?？捎奢斎胄蛄?, 2, 3, , n得到一個(gè)輸出序列p1, p2, p3, , pn (它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i < j < k，使得pj < pk < pi。(提示：用反證法)【解答】因?yàn)榻柚鷹Ｓ奢斎胄蛄?, 2, 3, , n，可得到輸出序列p1, p2, p3, , pn ，如果存在下標(biāo)i, j, k，滿足i <

5、; j < k，那么在輸出序列中，可能出現(xiàn)如下5種情況： i進(jìn)棧，i出棧，j進(jìn)棧，j出棧，k進(jìn)棧，k出棧。此時(shí)具有最小值的排在最前面pi位置，具有中間值的排在其后pj位置，具有最大值的排在pk位置，有pi < pj < pk, 不可能出現(xiàn)pj < pk < pi的情形； i進(jìn)棧，i出棧，j進(jìn)棧，k進(jìn)棧，k出棧，j出棧。此時(shí)具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中間值的排在最后pk位置，有pi < pk < pj , 不可能出現(xiàn)pj < pk < pi的情形； i進(jìn)棧，j進(jìn)棧，j出棧，i出棧，k進(jìn)棧，k出棧。此時(shí)具有中

6、間值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj < pi < pk, 不可能出現(xiàn)pj < pk < pi的情形； i進(jìn)棧，j進(jìn)棧，j出棧，k進(jìn)棧，k出棧，i出棧。此時(shí)具有中間值的排在最前面pi 位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk < pi < pj, 也不可能出現(xiàn)pj < pk < pi的情形； i進(jìn)棧，j進(jìn)棧，k進(jìn)棧，k出棧，j出棧，i出棧。此時(shí)具有最大值的排在最前面pi 位置，具有中間值的排在其后pj位置，具有最小值的排在pk位置，有pk < pj < pi, 也不可能出現(xiàn)pj &

7、lt; pk < pi的情形；0 m-14-4 將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間Vm中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top0等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top1等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長。當(dāng)向第0號(hào)棧插入一個(gè)新元素時(shí)，使top0增1得到新的棧頂位置，當(dāng)向第1號(hào)棧插入一個(gè)新元素時(shí)，使top1減1得到新的棧頂位置。當(dāng)top0+1 = top1時(shí)或top0 = top1-1時(shí)，?？臻g滿，此時(shí)不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結(jié)構(gòu)的類定義，并實(shí)現(xiàn)判?？?、判棧滿、插入、刪除算法?！窘獯稹縝ot0 top0 to

8、p1 bot1雙棧的類定義如下：#include <assert.h>template <class Type> class DblStack /雙棧的類定義 private: int top2, bot2;/雙棧的棧頂指針和棧底指針 Type *elements;/棧數(shù)組 int m;/棧最大可容納元素個(gè)數(shù) public: DblStack ( int sz =10 );/初始化雙棧, 總體積m的默認(rèn)值為10 DblStack ( ) delete elements; /析構(gòu)函數(shù) void DblPush ( const Type& x, int i );/把

9、x插入到棧i的棧頂 int DblPop ( int i );/退掉位于棧i棧頂?shù)脑?Type * DblGetTop ( int i );/返回棧i棧頂元素的值 int IsEmpty ( int i ) const return topi = boti; /判棧i空否, 空則返回1, 否則返回0 int IsFull ( ) const return top0+1 = top1; /判棧滿否, 滿則返回1, 否則返回0 void MakeEmpty ( int i ); /清空棧i的內(nèi)容template <class Type> DblStack<Type> :

10、DblStack ( int sz ) : m(sz), top0 (-1), bot0(-1), top1(sz), bot1(sz) /建立一個(gè)最大尺寸為sz的空棧, 若分配不成功則錯(cuò)誤處理。 elements = new Typem;/創(chuàng)建棧的數(shù)組空間 assert ( elements != NULL );/斷言: 動(dòng)態(tài)存儲(chǔ)分配成功與否template <class Type> void DblStack<Type> : DblPush ( const Type& x, int i ) /如果IsFull ( )，則報(bào)錯(cuò)；否則把x插入到棧i的棧頂 ass

11、ert ( !IsFull ( ) );/斷言: 棧滿則出錯(cuò)處理，停止執(zhí)行 if ( i = 0 ) elements +top0 = x;/棧0情形：棧頂指針先加1, 然后按此地址進(jìn)棧 else elements-top1 = x;/棧1情形：棧頂指針先減1, 然后按此地址進(jìn)棧template <class Type> int DblStack<Type> : DblPop ( int i ) /如果IsEmpty ( i )，則不執(zhí)行退棧，返回0；否則退掉位于棧i棧頂?shù)脑?，返? if ( IsEmpty ( i ) ) return 0;/判?？辗? 若?？談t函

12、數(shù)返回0 if ( i = 0 ) top0-;/棧0情形：棧頂指針減1 else top1+; /棧1情形：棧頂指針加1 return 1;template <class Type> Type * DblStack<Type> : DblGetTop ( int i ) /若棧不空則函數(shù)返回該棧棧頂元素的地址。 if ( IsEmpty ( int i ) ) return NULL;/判棧i空否, 若?？談t函數(shù)返回空指針 return& elements topi ;/返回棧頂元素的值template <class Type> void Make

13、Empty ( int i ) if ( i = 0 ) top0 = bot0 = -1; else top1 = bot1 = m; 4-5 寫出下列中綴表達(dá)式的后綴形式：(1) A * B * C(2) - A + B - C + D(3) A* - B + C(4) (A + B) * D + E / (F + A * D) + C(5) A && B| ! (E > F) /*注：按C+的優(yōu)先級(jí)*/(6) !(A && !( (B < C)|(C > D) ) )|(C < E) 【解答】(1) A B * C *(2) A -

14、 B + C - D +(3) A B - * C +(4) A B + D * E F A D * + / + C +(5) A B && E F > ! |(6) A B C < C D > | ! && ! C E < | 4-6 根據(jù)課文中給出的優(yōu)先級(jí)，回答以下問題：(1) 在函數(shù)postfix中，如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符，問棧中最多可存入多少個(gè)元素？(2) 如果表達(dá)式e含有n個(gè)運(yùn)算符，且括號(hào)嵌套的最大深度為6層，問棧中最多可存入多少個(gè)元素？【解答】(1) 在函數(shù)postfix中，如果表達(dá)式e含有n個(gè)運(yùn)算符和分界符，則可

15、能的運(yùn)算對象有n+1個(gè)。因此在利用后綴表達(dá)式求值時(shí)所用到的運(yùn)算對象棧中最多可存入n+1個(gè)元素。(2) 同上。4-7 設(shè)表達(dá)式的中綴表示為a * x - b / x2，試?yán)脳⑺臑楹缶Y表示ax * bx2/ -。寫出轉(zhuǎn)換過程中棧的變化?！窘獯稹咳粼O(shè)當(dāng)前掃描到的運(yùn)算符ch的優(yōu)先級(jí)為icp(ch)，該運(yùn)算符進(jìn)棧后的優(yōu)先級(jí)為isp(ch)，則可規(guī)定各個(gè)算術(shù)運(yùn)算符的優(yōu)先級(jí)如下表所示。 運(yùn)算符 ; ( *,/, % +, - ) isp 0 1 7 5 3 8 icp 0 8 6 4 2 1isp也叫做棧內(nèi)(in stack priority)優(yōu)先數(shù)，icp也叫做棧外(in coming priori

16、ty)優(yōu)先數(shù)。當(dāng)剛掃描到的運(yùn)算符ch的icp(ch)大于isp(stack)時(shí)，則ch進(jìn)棧；當(dāng)剛掃描到的運(yùn)算符ch的icp(ch)小于isp(stack)時(shí)，則位于棧頂?shù)倪\(yùn)算符退棧并輸出。從表中可知，icp(“(”)最高，但當(dāng)“(”進(jìn)棧后，isp(“(”)變得極低。其它運(yùn)算符進(jìn)入棧中后優(yōu)先數(shù)都升1，這樣可體現(xiàn)在中綴表達(dá)式中相同優(yōu)先級(jí)的運(yùn)算符自左向右計(jì)算的要求。運(yùn)算符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對“)”或棧底的“;”號(hào)與輸入流最后的“;”號(hào)配對時(shí)。前者將連續(xù)退出位于棧頂?shù)倪\(yùn)算符，直到遇到“(”為止。然后將“(”退棧以對消括號(hào)，后者將結(jié)束算法。步序掃描項(xiàng)項(xiàng)類型 動(dòng) 作棧的變化 輸 出 0F &#

17、39;' 進(jìn)棧, 讀下一符號(hào); 1 a操作數(shù)F 直接輸出, 讀下一符號(hào);A 2 *操作符F isp ( ' ; ' ) < icp ( ' * ' ), 進(jìn)棧, 讀下一符號(hào); *A 3 x操作數(shù)F 直接輸出, 讀下一符號(hào); *a x 4 -操作符F isp ( ' * ' ) > icp ( ' - ' ), 退棧輸出; a x * F isp ( ' ; ' ) < icp ( ' - ' ), 進(jìn)棧, 讀下一符號(hào); -a x * 5 b操作數(shù)F 直接輸出, 讀下一符號(hào);

18、 -a x * b 6 /操作符F isp ( ' - ' ) < icp ( '/' ), 進(jìn)棧, 讀下一符號(hào) ; -/a x * b 7 x操作數(shù)F 直接輸出, 讀下一符號(hào); -/a x * b x 8 操作符F isp ( ' / ' ) < icp ( '' ), 進(jìn)棧, 讀下一符號(hào); -/a x * b x 9 2操作數(shù)F 直接輸出, 讀下一符號(hào); -/a x * b x 2 10 ;操作符F isp ( '' ) > icp ( ' ; ' ), 退棧輸出; -/a x

19、 * b x 2 F isp ( ' / ' ) > icp ( ' ; ' ), 退棧輸出; -a x * b x 2/ F isp ( ' - ' ) > icp ( ' ; ' ), 退棧輸出; a x * b x 2/ - F 結(jié)束4-8 試?yán)眠\(yùn)算符優(yōu)先數(shù)法，畫出對如下中綴算術(shù)表達(dá)式求值時(shí)運(yùn)算符棧和運(yùn)算對象棧的變化。a + b * (c - d) - ef / g 【解答】設(shè)在表達(dá)式計(jì)算時(shí)各運(yùn)算符的優(yōu)先規(guī)則如上一題所示。因?yàn)橹苯訉χ芯Y算術(shù)表達(dá)式求值時(shí)必須使用兩個(gè)棧，分別對運(yùn)算符和運(yùn)算對象進(jìn)行處理，假設(shè)命名運(yùn)算

20、符棧為OPTR (operator的縮寫)，運(yùn)算對象棧為OPND(operand的縮寫)，下面給出對中綴表達(dá)式求值的一般規(guī)則：(1) 建立并初始化OPTR棧和OPND棧，然后在OPTR棧中壓入一個(gè)“;”(2) 從頭掃描中綴表達(dá)式，取一字符送入ch。(3) 當(dāng)ch不等于“;”時(shí)，執(zhí)行以下工作，否則結(jié)束算法。此時(shí)在OPND棧的棧頂?shù)玫竭\(yùn)算結(jié)果。 如果ch是運(yùn)算對象，進(jìn)OPND棧，從中綴表達(dá)式取下一字符送入ch； 如果ch是運(yùn)算符，比較ch的優(yōu)先級(jí)icp(ch)和OPTR棧頂運(yùn)算符isp(OPTR)的優(yōu)先級(jí)： F 若icp(ch) > isp(OPTR)，則ch進(jìn)OPTR棧，從中綴表達(dá)式取下一

21、字符送入ch； F 若icp(ch) < isp(OPTR)，則從OPND棧退出一個(gè)運(yùn)算符作為第2操作數(shù)a2，再退出一個(gè)運(yùn)算符作為第1操作數(shù)a1，從OPTR棧退出一個(gè)運(yùn)算符形成運(yùn)算指令 (a1)(a2)，執(zhí)行結(jié)果進(jìn)OPND棧； F 若icp(ch) = isp(OPTR) 且ch = “)”，則從OPTR棧退出棧頂?shù)摹?”，對消括號(hào)，然后從中綴表達(dá)式取下一字符送入ch；根據(jù)以上規(guī)則，給出計(jì)算a + b * (c - d) - ef / g時(shí)兩個(gè)棧的變化。步序掃描項(xiàng)項(xiàng)類型 動(dòng)作OPND棧變化OPTR棧變化0F OPTR棧與OPND棧初始化, ; 進(jìn)OPTR棧, 取第一個(gè)符號(hào);1a操作數(shù)F

22、a 進(jìn)OPND棧, 取下一符號(hào)a;2+操作符F icp ( + ) > isp ( ; ), 進(jìn)OPTR棧, 取下一符號(hào)a; +3b操作數(shù)F b 進(jìn)OPND棧, 取下一符號(hào)a b; +4*操作符F icp ( * ) > isp ( + ), 進(jìn)OPTR棧, 取下一符號(hào)a b; + *5(操作符F icp ( ( ) > isp ( * ), 進(jìn)OPTR棧, 取下一符號(hào)a b; + * (6c操作數(shù)F c 進(jìn)OPND棧, 取下一符號(hào)a b c; + * (7-操作符F icp ( - ) > isp ( ( ), 進(jìn)OPTR棧, 取下一符號(hào)a b; + * ( -8d操

23、作數(shù)F d 進(jìn)OPND棧, 取下一符號(hào)a b c d; + * ( -9)操作符F icp ( ) ) < isp ( - ), 退OPND棧 d, 退OPND 棧 c, 退OPTR棧 -, 計(jì)算 c d s1, 結(jié)果進(jìn) OPND棧a b s1; + * (10同上同上F icp ( ) ) = isp ( ( ), 退OPTR棧(, 對消括號(hào), 取下一符號(hào)a b s1; + * 11-操作符F icp ( - ) < isp ( * ), 退OPND棧 s1, 退OPND 棧 b, 退OPTR棧 *, 計(jì)算 b * s1 s2, 結(jié)果進(jìn) OPND棧a s2; + 12同上同上F

24、icp ( - ) < isp ( + ), 退OPND棧 s2, 退OPND 棧 a, 退OPTR棧 +, 計(jì)算 a * s2 s3, 結(jié)果 進(jìn)OPND棧s3; 13同上同上F icp ( - ) > isp ( ; ), 進(jìn)OPTR棧, 取下一符號(hào)s3 ; -14e操作數(shù)F e 進(jìn)OPND棧, 取下一符號(hào)s3 e; -15操作符F icp ( ) > isp ( - ), 進(jìn)OPTR棧, 取下一符號(hào)s3 e; -16f操作數(shù)F f 進(jìn)OPND棧, 取下一符號(hào)s3 e f; -17/操作符F icp ( / ) < isp ( ), 退OPND棧 f, 退OPND 棧

25、 e, 退OPTR棧 , 計(jì)算 ef s4, 結(jié)果 進(jìn)OPND棧s3 s4; -18同上同上F icp ( / ) > isp ( - ), 進(jìn)OPTR棧, 取下一符號(hào)s3 s4; - /19g操作數(shù)F g 進(jìn)OPND棧, 取下一符號(hào)s3 s4 g; - /20;操作符F icp ( ; ) < isp ( / ), 退OPND棧 g, 退OPND 棧 s4, 退OPTR棧 /, 計(jì)算 s4 / g s5, 結(jié)果 進(jìn)OPND棧s3 s5; -21同上同上F icp ( ; ) < isp ( - ), 退OPND棧 s5, 退OPND 棧 s3, 退OPTR棧 - , 計(jì)算

26、s3 s5 s6, 結(jié) 果進(jìn)OPND棧s6;22同上同上F icp ( ; ) = isp ( ; ), 退OPND棧 s6, 結(jié)束;4-9 假設(shè)以數(shù)組Qm存放循環(huán)隊(duì)列中的元素, 同時(shí)以rear和length分別指示環(huán)形隊(duì)列中的隊(duì)尾位置和隊(duì)列中所含元素的個(gè)數(shù)。試給出該循環(huán)隊(duì)列的隊(duì)空條件和隊(duì)滿條件, 并寫出相應(yīng)的插入(enqueue)和刪除(dlqueue)元素的操作?！窘獯稹垦h(huán)隊(duì)列類定義#include <assert.h>template <class Type> class Queue /循環(huán)隊(duì)列的類定義public: Queue ( int=10 ); Queu

27、e ( ) delete elements; void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) length = 0; /置空隊(duì)列 int IsEmpty ( ) const return length = 0; /判隊(duì)列空否 int IsFull ( ) const return length = maxSize; /判隊(duì)列滿否private: int rear, length;/隊(duì)尾指針和隊(duì)列長度 Type *elements;/存放隊(duì)列元素的數(shù)組 int ma

28、xSize;/隊(duì)列最大可容納元素個(gè)數(shù)構(gòu)造函數(shù)template <class Type>Queue<Type>: Queue ( int sz ) : rear (maxSize-1), length (0), maxSize (sz) /建立一個(gè)最大具有maxSize個(gè)元素的空隊(duì)列。 elements = new TypemaxSize;/創(chuàng)建隊(duì)列空間 assert ( elements != 0 );/斷言: 動(dòng)態(tài)存儲(chǔ)分配成功與否插入函數(shù)template<class Type> void Queue<Type> : EnQueue ( Type

29、 &item ) assert ( ! IsFull ( ) );/判隊(duì)列是否不滿，滿則出錯(cuò)處理length+;/長度加1rear = ( rear +1) % maxSize;/隊(duì)尾位置進(jìn)1elementsrear = item;/進(jìn)隊(duì)列刪除函數(shù)template<class Type> Type Queue<Type> : DeQueue ( ) assert ( ! IsEmpty ( ) ); /判斷隊(duì)列是否不空，空則出錯(cuò)處理length-;/隊(duì)列長度減1return elements(rear-length+maxSize) % maxSize;/返回原

30、隊(duì)頭元素值讀取隊(duì)頭元素值函數(shù)template<class Type> Type Queue<Type> : GetFront ( ) assert ( ! IsEmpty ( ) );return elements(rear-length+1+maxSize) % maxSize;/返回隊(duì)頭元素值4-10 假設(shè)以數(shù)組Qm存放循環(huán)隊(duì)列中的元素, 同時(shí)設(shè)置一個(gè)標(biāo)志tag，以tag = 0和tag = 1來區(qū)別在隊(duì)頭指針(front)和隊(duì)尾指針(rear)相等時(shí)，隊(duì)列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法?！窘獯稹垦h(huán)隊(duì)

31、列類定義#include <assert.h>template <class Type> class Queue /循環(huán)隊(duì)列的類定義public: Queue ( int=10 ); Queue ( ) delete Q; void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = rear = tag = 0; /置空隊(duì)列 int IsEmpty ( ) const return front = rear && tag

32、 = 0; /判隊(duì)列空否 int IsFull ( ) const return front = rear && tag = 1; /判隊(duì)列滿否private: int rear, front, tag;/隊(duì)尾指針、隊(duì)頭指針和隊(duì)滿標(biāo)志 Type *Q;/存放隊(duì)列元素的數(shù)組 int m;/隊(duì)列最大可容納元素個(gè)數(shù)構(gòu)造函數(shù)template <class Type>Queue<Type>: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) /建立一個(gè)最大具有m個(gè)元素的空隊(duì)列。 Q = new Typem

33、;/創(chuàng)建隊(duì)列空間 assert ( Q != 0 );/斷言: 動(dòng)態(tài)存儲(chǔ)分配成功與否插入函數(shù)template<class Type> void Queue<Type> : EnQueue ( Type &item ) assert ( ! IsFull ( ) );/判隊(duì)列是否不滿，滿則出錯(cuò)處理rear = ( rear + 1 ) % m;/隊(duì)尾位置進(jìn)1, 隊(duì)尾指針指示實(shí)際隊(duì)尾位置Qrear = item;/進(jìn)隊(duì)列tag = 1;/標(biāo)志改1，表示隊(duì)列不空刪除函數(shù)template<class Type> Type Queue<Type>

34、: DeQueue ( ) assert ( ! IsEmpty ( ) );/判斷隊(duì)列是否不空，空則出錯(cuò)處理front = ( front + 1 ) % m;/隊(duì)頭位置進(jìn)1, 隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置tag = 0;/標(biāo)志改0, 表示棧不滿return Qfront;/返回原隊(duì)頭元素的值讀取隊(duì)頭元素函數(shù)template<class Type> Type Queue<Type> : GetFront ( ) assert ( ! IsEmpty ( ) );/判斷隊(duì)列是否不空，空則出錯(cuò)處理return Q(front + 1) % m;/返回隊(duì)頭元素的值4-11

35、 若使用循環(huán)鏈表來表示隊(duì)列，p是鏈表中的一個(gè)指針。試基于此結(jié)構(gòu)給出隊(duì)列的插入(enqueue)和刪除(dequeue)算法，并給出p為何值時(shí)隊(duì)列空?！窘獯稹挎?zhǔn)疥?duì)列的類定義template <class Type> class Queue;/鏈?zhǔn)疥?duì)列類的前視定義template <class Type> class QueueNode /鏈?zhǔn)疥?duì)列結(jié)點(diǎn)類定義friend class Queue<Type>private: Type data;/數(shù)據(jù)域 QueueNode<Type> *link;/鏈域public: QueueNode ( Type

36、 d = 0, QueueNode *l = NULL ) : data (d), link (l) /構(gòu)造函數(shù);template <class Type> class Queue /鏈?zhǔn)疥?duì)列類定義public: Queue ( ) : p ( NULL ) /構(gòu)造函數(shù) Queue ( );/析構(gòu)函數(shù) void EnQueue ( const Type & item );/將item加入到隊(duì)列中 Type DeQueue ( );/刪除并返回隊(duì)頭元素 Type GetFront ( );/查看隊(duì)頭元素的值 void MakeEmpty ( );/置空隊(duì)列，實(shí)現(xiàn)與Queue

37、( ) 相同 int IsEmpty ( ) const return p = NULL; /判隊(duì)列空否private: QueueNode<Type> *p;/隊(duì)尾指針（在循環(huán)鏈表中）;隊(duì)列的析構(gòu)函數(shù)template <class Type> Queue<Type>:Queue ( ) /隊(duì)列的析構(gòu)函數(shù) QueueNode<Type> *s; while ( p != NULL ) s = p; p = p->link; delete s; /逐個(gè)刪除隊(duì)列中的結(jié)點(diǎn)隊(duì)列的插入函數(shù)template <class Type> voi

38、d Queue<Type>:EnQueue ( const Type & item ) if ( p = NULL ) /隊(duì)列空, 新結(jié)點(diǎn)成為第一個(gè)結(jié)點(diǎn)p = new QueueNode<Type> ( item, NULL ); p->link = p; else /隊(duì)列不空, 新結(jié)點(diǎn)鏈入p之后QueueNode<Type> *s = new QueueNode<Type> ( item, NULL );s->link = p->link; p = p->link = s;/結(jié)點(diǎn)p指向新的隊(duì)尾隊(duì)列的刪除函數(shù)tem

39、plate <class Type> Type Queue<Type>:DeQueue ( ) if ( p = NULL ) cout << "隊(duì)列空, 不能刪除！" << endl; return 0; QueueNode<Type> *s = p;/隊(duì)頭結(jié)點(diǎn)為p后一個(gè)結(jié)點(diǎn) p->link = s->link;/重新鏈接, 將結(jié)點(diǎn)s從鏈中摘下 Type retvalue = s->data; delete s;/保存原隊(duì)頭結(jié)點(diǎn)中的值, 釋放原隊(duì)頭結(jié)點(diǎn)return retvalue;/返回?cái)?shù)據(jù)存

40、放地址隊(duì)空條件 p = NULL。4-12 若將一個(gè)雙端隊(duì)列順序表示在一維數(shù)組Vm中，兩個(gè)端點(diǎn)設(shè)為end1和end2，并組織成一個(gè)循環(huán)隊(duì)列。試寫出雙端隊(duì)列所用指針end1和end2的初始化條件及隊(duì)空與隊(duì)滿條件，并編寫基于此結(jié)構(gòu)的相應(yīng)的插入(enqueue)新元素和刪除(dlqueue)算法。end2【解答】初始化條件 end1 = end2 = 0;end1隊(duì)空條件 end1 = end2;隊(duì)滿條件 ( end1 + 1 ) % m = end2; /設(shè)end1端順時(shí)針進(jìn)棧，end2端逆時(shí)針進(jìn)棧循環(huán)隊(duì)列類定義#include <assert.h>template <class

41、 Type> class DoubleQueue /循環(huán)隊(duì)列的類定義public: DoubleQueue ( int=10 ); DoubleQueue ( ) delete V; void EnQueue ( Type & item, const int end ); Type DeQueue (const int end ); Type GetFront (const int end ); void MakeEmpty ( ) end1 = end2 = 0; /置空隊(duì)列 int IsEmpty ( ) const return end1 = end2; /判兩隊(duì)列空否 i

42、nt IsFull ( ) const return (end1+1) % m = end2; /判兩隊(duì)列滿否private: int end1, end2;/隊(duì)列兩端的指針 Type *V;/存放隊(duì)列元素的數(shù)組 int m;/隊(duì)列最大可容納元素個(gè)數(shù)構(gòu)造函數(shù)template <class Type>DoubleQueue<Type>: DoubleQueue ( int sz ) : end1 (0), end2 (0), m (sz) /建立一個(gè)最大具有m個(gè)元素的空隊(duì)列。 V = new Typem;/創(chuàng)建隊(duì)列空間 assert ( V != 0 );/斷言: 動(dòng)態(tài)存

43、儲(chǔ)分配成功與否插入函數(shù)template<class Type> void DoubleQueue<Type> : EnQueue ( Type &item, const int end ) assert ( !IsFull ( ) );if ( end = 1 ) end1 = ( end1 + 1 ) % m;/end1端指針先進(jìn)1, 再按指針進(jìn)棧Vend1 = item;/end1指向?qū)嶋H隊(duì)頭位置else Vend2 = item;/end2端先進(jìn)隊(duì)列, 指針再進(jìn)1end2 = ( end2 - 1 + m ) % m;/end2指向?qū)嶋H隊(duì)頭的下一位置刪除函

44、數(shù)template<class Type> Type DoubleQueue<Type> : DeQueue ( const int end ) assert ( !IsEmpty ( ) );Type& temp;if ( end = 1 ) temp = Vend1;/先保存原隊(duì)頭元素的值, end1端指針退1end1 = ( end1 + m - 1 ) % m;else end2 = ( end2 + 1 ) % m;temp = Vend2;/end2端指針先退1。再保存原隊(duì)頭元素的值return temp;讀取隊(duì)頭元素的值template<cl

45、ass Type> Type DoubleQueue<Type> : GetFront ( const int end ) assert ( !IsEmpty ( ) );Type& temp;if ( end = 1 ) return Vend1;/返回隊(duì)頭元素的值else return V(end2+1) % m;4-13 設(shè)用鏈表表示一個(gè)雙端隊(duì)列，要求可在表的兩端插入，但限制只能在表的一端刪除。試編寫基于此結(jié)構(gòu)的隊(duì)列的插入(enqueue)和刪除(dequeue)算法，并給出隊(duì)列空和隊(duì)列滿的條件?！窘獯稹挎?zhǔn)诫p端隊(duì)列的類定義template <class

46、Type> class DoubleQueue;/鏈?zhǔn)诫p端隊(duì)列類的前視定義template <class Type> class DoubleQueueNode /鏈?zhǔn)诫p端隊(duì)列結(jié)點(diǎn)類定義friend class DoubleQueue<Type>private: Type data;/數(shù)據(jù)域 DoubleQueueNode<Type> *link;/鏈域public: DoubleQueueNode (Type d = 0, DoubleQueueNode *l = NULL) : data (d), link (l) /構(gòu)造函數(shù);template &

47、lt;class Type> class DoubleQueue /鏈?zhǔn)诫p端隊(duì)列類定義public: DoubleQueue ( ); /構(gòu)造函數(shù) DoubleQueue ( );/析構(gòu)函數(shù)void EnDoubleQueue1 ( const Type& item );/從隊(duì)列end1端插入void EnDoubleQueue2 ( const Type& item );/從隊(duì)列end2端插入Type DeDoubleQueue ( );/刪除并返回隊(duì)頭end1元素 Type GetFront ( );/查看隊(duì)頭end1元素的值 void MakeEmpty ( );/

48、置空隊(duì)列 int IsEmpty ( ) const return end1 = end1->link; /判隊(duì)列空否private: QueueNode<Type> *end1, *end2;/end1在鏈頭, 可插可刪; end2在鏈尾, 可插不可刪;隊(duì)列的構(gòu)造函數(shù)template<class Type> doubleQueue<Type> : doubleQueue ( ) /構(gòu)造函數(shù)end1 = end2 = new DoubleQueueNode<Type>( ); /創(chuàng)建循環(huán)鏈表的表頭結(jié)點(diǎn)assert ( !end1 | !en

49、d2 );end1->link = end1;隊(duì)列的析構(gòu)函數(shù)template <class Type> Queue<Type> : Queue ( ) /隊(duì)列的析構(gòu)函數(shù) QueueNode<Type> *p; /逐個(gè)刪除隊(duì)列中的結(jié)點(diǎn), 包括表頭結(jié)點(diǎn) while ( end1 != NULL ) p = end1; end1 = end1->link; delete p; 隊(duì)列的插入函數(shù)template<class Type> /從隊(duì)列end1端插入void DoubleQueue<Type> : EnDoubleQueue

50、1 ( const Type& item ) if ( end1 = end1->link ) /隊(duì)列空, 新結(jié)點(diǎn)成為第一個(gè)結(jié)點(diǎn)end2 = end1->link = new DoubleQueueNode<Type> ( item, end1 );else /隊(duì)列不空, 新結(jié)點(diǎn)鏈入end1之后end1->link = new DoubleQueueNode<Type> ( item, end1->link );template <class Type> /從隊(duì)列end2端插入void DoubleQueue<Type> : EnDoubleQueue2 ( const Type& item ) end2 = end2->link = new DoubleQueueNode<Type> ( item, end1 );隊(duì)列的刪除函數(shù)template <class Type> Type DoubleQueue<Type> : DeDoubleQu