1、第3章 特殊線性表?xiàng)！㈥?duì)列和串本章的基本內(nèi)容是：三種特殊的線性表?xiàng)！㈥?duì)列、串從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限的線性表，他們的邏輯結(jié)構(gòu)相同。串是重要的非數(shù)值處理對(duì)象，它是以字符作為數(shù)據(jù)元素的線性表。 1 特殊線性表?xiàng)５倪壿嫿Y(jié)構(gòu)空棧：不含任何數(shù)據(jù)元素的棧。 （a1, a2, , an）棧：限定僅在表尾進(jìn)行插入和刪除操作的線性表。棧頂棧底允許插入和刪除的一端稱為棧頂，另一端稱為棧底。 2a1a2a3入棧出棧棧底棧頂 特殊線性表?xiàng)２迦耄喝霔！⑦M(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖3棧的操作特性：后進(jìn)先出a1a2a3入棧出棧棧底棧頂 特殊線性表?xiàng)２迦耄喝霔！⑦M(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧的

2、示意圖4例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？ 特殊線性表?xiàng)５讞ｍ攁b棧頂c棧頂 情況1：棧的邏輯結(jié)構(gòu)5 特殊線性表?xiàng)５讞ｍ攁b棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu) 情況1：6 特殊線性表?xiàng)５讞ｍ攁b棧頂出棧序列：b 情況2：例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)7 特殊線性表?xiàng)５譨出棧序列：b出棧序列：b、c出棧序列： b、 c、ac棧

3、頂棧頂注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒(méi)有限定插入和刪除操作進(jìn)行的時(shí)間。例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu) 情況2：8例題解析習(xí)題2（1）（3）9棧的抽象數(shù)據(jù)類型定義 特殊線性表?xiàng)DT StackData 棧中元素具有相同類型及后進(jìn)先出特性， 相鄰元素具有前驅(qū)和后繼關(guān)系Operation InitStack 前置條件：棧不存在 輸入：無(wú) 功能：棧的初始化 輸出：無(wú) 后置條件：構(gòu)造一個(gè)空棧 10DestroyStack 前置條件：棧已存在 輸入：無(wú) 功能：銷毀棧 輸出：無(wú) 后置條件：釋放棧所占用的存儲(chǔ)空間

4、Push 前置條件：棧已存在 輸入：元素值x 功能：在棧頂插入一個(gè)元素x 輸出：如果插入不成功，拋出異常 后置條件：如果插入成功，棧頂增加了一個(gè)元素棧的抽象數(shù)據(jù)類型定義 特殊線性表?xiàng)?1Pop 前置條件：棧已存在 輸入：無(wú) 功能：刪除棧頂元素 輸出：如果刪除成功，返回被刪元素值，否則，拋出異常 后置條件：如果刪除成功，棧減少了一個(gè)元素GetTop 前置條件：棧已存在 輸入：無(wú) 功能：讀取當(dāng)前的棧頂元素 輸出：若棧不空，返回當(dāng)前的棧頂元素值 后置條件：棧不變棧的抽象數(shù)據(jù)類型定義 特殊線性表?xiàng)?2Empty 前置條件：棧已存在 輸入：無(wú) 功能：判斷棧是否為空 輸出：如果棧為空，返回1，否則，返回0

5、 后置條件：棧不變endADT棧的抽象數(shù)據(jù)類型定義 特殊線性表?xiàng)?3棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序棧棧的順序存儲(chǔ)結(jié)構(gòu)如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？ 0 1 2 3 4 5 6 7 8a1確定用數(shù)組的哪一端表示棧底。 特殊線性表?xiàng)８皆O(shè)指針top指示棧頂元素在數(shù)組中的位置。 top14出棧：top減1進(jìn)棧：top加1棧空：top= -1 0 1 2 3 4 5 6 7 8 特殊線性表?xiàng)1topa2topa3top棧滿：top= MAX_SIZE-1棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 15 順序棧類的聲明const int MAX_SIZE=100;template class seqStack public:

6、 seqStack ( ) ; seqStack ( ); void Push ( T x ); T Pop ( ); T GetTop ( ); bool Empty ( ); private: T dataMAX_SIZE; int top; 特殊線性表?xiàng)?6順序棧的實(shí)現(xiàn)入棧template void seqStack:Push ( T x) if (top=MAX_SIZE-1) throw “溢出”; top+; datatop=x; 特殊線性表?xiàng)２僮鹘涌冢?void Push( T x );時(shí)間復(fù)雜度？17順序棧的實(shí)現(xiàn)出棧template T seqStack: Pop ( ) if

7、 (top=-1) throw “溢出”; x=datatop-; return x; 特殊線性表?xiàng)２僮鹘涌冢?T Pop( );時(shí)間復(fù)雜度？18進(jìn)制轉(zhuǎn)換 void Dec_to_Ocx(int a,int d) int div,x; SeqStack s; while(a!=0) div=a%d; s.Push(div); a=a/d; cout轉(zhuǎn)換后的數(shù)為：; while(!s.Empty() x=s.GetTop(); coutx; s.Pop(); coutendl; 19兩棧共享空間 解決方案1：直接解決：為每個(gè)棧開(kāi)辟一個(gè)數(shù)組空間。 解決方案2： 順序棧單向延伸使用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)

8、棧 特殊線性表?xiàng)Ｔ谝粋€(gè)程序中需要同時(shí)使用具有相同數(shù)據(jù)類型的兩個(gè)棧，如何順序存儲(chǔ)這兩個(gè)棧？會(huì)出現(xiàn)什么問(wèn)題？如何解決？20兩棧共享空間：使用一個(gè)數(shù)組來(lái)存儲(chǔ)兩個(gè)棧，讓一個(gè)棧的棧底為該數(shù)組的始端，另一個(gè)棧的棧底為該數(shù)組的末端，兩個(gè)棧從各自的端點(diǎn)向中間延伸。 特殊線性表?xiàng)蓷９蚕砜臻g 21棧1的底固定在下標(biāo)為0的一端；棧2的底固定在下標(biāo)為StackSize-1的一端。 top1和top2分別為棧1和棧2的棧頂指針；Stack_Size為整個(gè)數(shù)組空間的大小（圖中用S表示）；a1 a2 aitop10 1 2 S-1兩棧共享空間兩棧共享空間 top2bj b2 b1棧1底棧2底22兩棧共享空間top1= -

9、1什么時(shí)候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1top123兩棧共享空間top1= -1什么時(shí)候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1什么時(shí)候棧2為空？top2top2= Stack_Size24兩棧共享空間top1= -1什么時(shí)候棧1為空？a1 a2 aitop10 1 2 S-1兩棧共享空間 top2bj b2 b1什么時(shí)候棧2為空？top2= Stack_Size什么時(shí)候棧滿？top2= top1+125const int Stack_Size=100; template class

10、BothStack public: BothStack( ); BothStack( ); void Push(int i, T x); T Pop(int i); T GetTop(int i); bool Empty(int i); private: T dataStack_Size; int top1, top2; ;兩棧共享空間類的聲明兩棧共享空間261. 如果棧滿，則拋出上溢異常；2. 判斷是插在棧1還是棧2； 2.1 若在棧1插入，則 2.1.1 top1加1; 2.1.2 在top1處填入x； 2.2 若在棧2插入，則 2.2.1 top2減1; 2.2.2 在top2處填入x；

11、兩棧共享空間兩棧共享空間的實(shí)現(xiàn)插入 操作接口：void Push(int i, T x) ;271. 若是在棧1刪除，則 1.1 若棧1為空棧，拋出下溢異常； 1.2 刪除并返回棧1的棧頂元素；2. 若是在棧2刪除，則 2.1 若棧2為空棧，拋出下溢異常； 2.2 刪除并返回棧2的棧頂元素；兩棧共享空間兩棧共享空間的實(shí)現(xiàn)刪除 操作接口：T Pop(int i) ;28括號(hào)匹配問(wèn)題int Bracket_Test(char *str)/判別表達(dá)式中三種括號(hào)是否匹配SeqStack s;char *p,c;for(p=str;*p;p+)if(*p=(|*p=|*p=)s.Push(*p);els

12、e if(*p=)|*p=|*p=) if(s.Empty() return 0; c=s.Pop(); if(*p=)&c!=() return 0; if(*p=&c!=) return 0;if(*p=&c!=) return 0; /必須與當(dāng)前棧頂括號(hào)匹配/forif(!s.Empty() return 0; return 1;29棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu) 特殊線性表?xiàng)irsta1a2anai鏈棧需要加頭結(jié)點(diǎn)嗎？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲(chǔ)？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。30棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 棧頂棧底鏈棧：棧的鏈接存儲(chǔ)結(jié)

13、構(gòu) 特殊線性表?xiàng)opanan-1a1firsta1a2anai兩種示意圖在內(nèi)存中對(duì)應(yīng)同一種狀態(tài)topa1an-1an棧頂棧底31鏈棧的類聲明template class LinkStack public: LinkStack( ); LinkStack( ); void Push(T x); T Pop( ); T GetTop( ); bool Empty( ); private: Node *top; 特殊線性表?xiàng)?2算法描述：template void LinkStack:Push(T x) s=new Node; s-data=x; s-next=top; top=s; 特殊線性表?xiàng)?/p>

14、topanan-1a1鏈棧的實(shí)現(xiàn)插入 xstop操作接口： void Push(T x); 為什么沒(méi)有判斷棧滿 ？33算法描述：template T LinkStack:Pop( ) if (top=NULL) throw 下溢; x=top-data; p=top; top=top-next; delete p; return x; 特殊線性表?xiàng)ｆ湕５膶?shí)現(xiàn)插入操作接口： T Pop( ); topanan-1a1topp top+可以嗎？34順序棧和鏈棧的比較時(shí)間性能：相同，都是常數(shù)時(shí)間O(1)。空間性能：順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問(wèn)題。鏈棧：沒(méi)有棧滿的問(wèn)題，只有當(dāng)內(nèi)存沒(méi)有可用空間

15、時(shí)才會(huì)出現(xiàn)棧滿，但是每個(gè)元素都需要一個(gè)指針域，從而產(chǎn)生了結(jié)構(gòu)性開(kāi)銷。 特殊線性表?xiàng)？傊?dāng)棧的使用過(guò)程中元素個(gè)數(shù)變化較大時(shí)，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。35棧的應(yīng)用舉例遞歸1 遞歸的定義子程序（或函數(shù)）直接調(diào)用自己或通過(guò)一系列調(diào)用語(yǔ)句間接調(diào)用自己，是一種描述問(wèn)題和解決問(wèn)題的基本方法。 2 遞歸的基本思想問(wèn)題分解：把一個(gè)不能或不好解決的大問(wèn)題轉(zhuǎn)化為一個(gè)或幾個(gè)小問(wèn)題，再把這些小問(wèn)題進(jìn)一步分解成更小的小問(wèn)題，直至每個(gè)小問(wèn)題都可以直接解決。 363 遞歸的要素 遞歸邊界條件：確定遞歸到何時(shí)終止，也稱為遞歸出口； 遞歸模式：大問(wèn)題是如何分解為小問(wèn)題的，也稱為遞歸體。 棧的應(yīng)用舉例遞歸37例1

16、階乘函數(shù)遞歸算法int fact ( int n ) if ( n = 0 ) return 1; else return n * fact (n-1);-*=時(shí)當(dāng)時(shí)當(dāng))!1(1!n1n1nnn棧的應(yīng)用舉例遞歸38求解階乘 n! 的過(guò)程計(jì)算 fact(4)計(jì)算 4*fact(3)計(jì)算 3*fact(2)計(jì)算 2*fact(1)計(jì)算 fact(1)遞歸調(diào)用回歸求值返回 24返回 6返回 2返回1棧的應(yīng)用舉例遞歸39遞歸過(guò)程與遞歸工作棧遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，返回次序正好相反： 遞歸調(diào)用 n! (n-1)! (n-2)! 1!=1 返回次序棧的應(yīng)用舉例遞歸40遞歸函數(shù)的內(nèi)

17、部執(zhí)行過(guò)程每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量等另外分配存儲(chǔ)空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。 局部變量返回地址值 參活動(dòng)記錄框架遞歸工作記錄 運(yùn)行開(kāi)始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址； 每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧； 每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。棧的應(yīng)用舉例遞歸41特殊線性表隊(duì)列隊(duì)列的邏輯結(jié)構(gòu)空隊(duì)列：不含任何數(shù)據(jù)元素的隊(duì)列。 隊(duì)列：只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操

18、作的線性表。允許插入（也稱入隊(duì)、進(jìn)隊(duì)）的一端稱為隊(duì)尾，允許刪除（也稱出隊(duì)）的一端稱為隊(duì)頭。 （a1, a2, , an）隊(duì)尾隊(duì)頭42隊(duì)列的操作特性：先進(jìn)先出a1a2a3入隊(duì)隊(duì)尾隊(duì)頭出隊(duì)特殊線性表隊(duì)列隊(duì)頭隊(duì)列的邏輯結(jié)構(gòu)43隊(duì)列的抽象數(shù)據(jù)類型定義 ADT Queue Data 隊(duì)列中元素具有相同類型及先進(jìn)先出特性， 相鄰元素具有前驅(qū)和后繼關(guān)系Operation InitQueue 前置條件：隊(duì)列不存在 輸入：無(wú) 功能：初始化隊(duì)列 輸出：無(wú) 后置條件：創(chuàng)建一個(gè)空隊(duì)列特殊線性表隊(duì)列44 DestroyQueue 前置條件：隊(duì)列已存在 輸入：無(wú) 功能：銷毀隊(duì)列 輸出：無(wú) 后置條件：釋放隊(duì)列所占用的存儲(chǔ)空

19、間 EnQueue 前置條件：隊(duì)列已存在 輸入：元素值x 功能：在隊(duì)尾插入一個(gè)元素 輸出：如果插入不成功，拋出異常 后置條件：如果插入成功，隊(duì)尾增加了一個(gè)元素隊(duì)列的抽象數(shù)據(jù)類型定義 特殊線性表隊(duì)列45 DeQueue 前置條件：隊(duì)列已存在 輸入：無(wú) 功能：刪除隊(duì)頭元素 輸出：如果刪除成功，返回被刪元素值 后置條件：如果刪除成功，隊(duì)頭減少了一個(gè)元素 GetQueue 前置條件：隊(duì)列已存在 輸入：無(wú) 功能：讀取隊(duì)頭元素 輸出：若隊(duì)列不空，返回隊(duì)頭元素 后置條件：隊(duì)列不變隊(duì)列的抽象數(shù)據(jù)類型定義 特殊線性表隊(duì)列46Empty 前置條件：隊(duì)列已存在 輸入：無(wú) 功能：判斷隊(duì)列是否為空 輸出：如果隊(duì)列為空，

20、返回1，否則，返回0 后置條件：隊(duì)列不變endADT隊(duì)列的抽象數(shù)據(jù)類型定義 特殊線性表隊(duì)列470 1 2 3 4 入隊(duì)出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 順序隊(duì)列：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)特殊線性表隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：a1a2a3a4依次入隊(duì)a1a2a3a4rearrearrearrear入隊(duì)操作時(shí)間性能為O(1)48特殊線性表隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a1a2a3a4rear49特殊線性表隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a2

21、a3a4rear50特殊線性表隊(duì)列如何改造數(shù)組實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ)？例：a1a2依次出隊(duì)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3a4rear出隊(duì)操作時(shí)間性能為O(n)51特殊線性表隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何改進(jìn)出隊(duì)的時(shí)間性能？放寬隊(duì)列的所有元素必須存儲(chǔ)在數(shù)組的前n個(gè)單元這一條件 ，只要求隊(duì)列的元素存儲(chǔ)在數(shù)組中連續(xù)的位置。設(shè)置隊(duì)頭、隊(duì)尾兩個(gè)指針 隊(duì)頭指針：front指向隊(duì)頭元素的前一個(gè)位置 隊(duì)尾指針：rear 指向隊(duì)尾元素52特殊線性表隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)例：a1a2a3a4依次入隊(duì)a1a2a3a4rearrearrearrear入隊(duì)

22、操作時(shí)間性能仍為O(1)front rear53例：a1a2依次出隊(duì)特殊線性表隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a1a2a3a4rearfrontfrontfront出隊(duì)操作時(shí)間性能提高為O(1)54例：a1a2依次出隊(duì)特殊線性表隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3a4rearfront隊(duì)列的移動(dòng)有什么特點(diǎn)？55例：a1a2依次出隊(duì)特殊線性表隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3a4rearfront整個(gè)隊(duì)列向數(shù)組下標(biāo)較大方向移動(dòng)單向移動(dòng)性56假溢出：當(dāng)元素被插入到數(shù)組中下標(biāo)最大的位置上之后，隊(duì)列的空間就用盡了，盡管此時(shí)

23、數(shù)組的低端還有空閑空間，這種現(xiàn)象叫做假溢出。特殊線性表隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 繼續(xù)入隊(duì)會(huì)出現(xiàn)什么情況？0 1 2 3 4 入隊(duì)出隊(duì)a3a4rearfronta5rear57循環(huán)隊(duì)列：將存儲(chǔ)隊(duì)列的數(shù)組頭尾相接。特殊線性表隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何解決假溢出？0 1 2 3 4 入隊(duì)出隊(duì)a3a4fronta5rearreara658特殊線性表隊(duì)列不存在物理的循環(huán)結(jié)構(gòu)，用軟件方法實(shí)現(xiàn)。求模：（41）mod 50隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 如何實(shí)現(xiàn)循環(huán)隊(duì)列？0 1 2 3 4 入隊(duì)出隊(duì)a3a4frontreara659如何判斷循環(huán)隊(duì)列隊(duì)空？特殊線性表隊(duì)列隊(duì)空的臨界狀態(tài)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)

24、現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3rearfront60如何判斷循環(huán)隊(duì)列隊(duì)空？特殊線性表隊(duì)列執(zhí)行出隊(duì)操作隊(duì)空：front=rear隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 0 1 2 3 4 入隊(duì)出隊(duì)a3frontrearfront61如何判斷循環(huán)隊(duì)列隊(duì)滿？隊(duì)滿的臨界狀態(tài)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 特殊線性表隊(duì)列0 1 2 3 4 入隊(duì)出隊(duì)a3a4fronta5reara662如何判斷循環(huán)隊(duì)列隊(duì)滿？執(zhí)行入隊(duì)操作隊(duì)滿：front=rear隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 特殊線性表隊(duì)列0 1 2 3 4 入隊(duì)出隊(duì)a3a4fronta5reara6reara763方法一：附設(shè)一個(gè)存儲(chǔ)隊(duì)列中元素個(gè)數(shù)的變量num，當(dāng)num=

25、0時(shí)隊(duì)空，當(dāng)num=QueueSize時(shí)為隊(duì)滿；方法二：修改隊(duì)滿條件，浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)數(shù)組中只有一個(gè)空閑單元；方法三：設(shè)置標(biāo)志flag，當(dāng)front=rear且flag=0時(shí)為隊(duì)空，當(dāng)front=rear且flag=1時(shí)為隊(duì)滿。如何確定不同的隊(duì)空、隊(duì)滿的判定條件？為什么要將隊(duì)空和隊(duì)滿的判定條件分開(kāi)？特殊線性表隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 64隊(duì)滿的條件：(rear+1) mod QueueSize=front隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 特殊線性表隊(duì)列0 1 2 3 4 入隊(duì)rearfronta3a4fronta5reara6出隊(duì)65數(shù)組用來(lái)表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為

26、隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的公式為（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n66循環(huán)隊(duì)列類的聲明const int QueueSize=100; template class CirQueue public: CirQueue( )； CirQueue( )； void EnQueue(T x); T DeQueue( ); T GetQueue( ); bool Empty( )； private: T dataQueueSize; int front, rear;特殊線性表隊(duì)列67template void CirQueue:EnQ

27、ueue(T x) if (rear+1) % QueueSize =front) throw 上溢; rear=(rear+1) % QueueSize; datarear=x; 特殊線性表隊(duì)列循環(huán)隊(duì)列的實(shí)現(xiàn)入隊(duì)0 1 2 3 4 入隊(duì)出隊(duì)a3a4rearfronta5rear680 1 2 3 4 入隊(duì)a4a5a6出隊(duì)template T CirQueue:DeQueue( ) if (rear=front) throw 下溢; front=(front+1) % QueueSize; return datafront; 特殊線性表隊(duì)列循環(huán)隊(duì)列的實(shí)現(xiàn)出隊(duì)frontrearfronta369

28、template T CirQueue:GetQueue( ) if (rear=front) throw 下溢; i=(front+1) % QueueSize; return datai;特殊線性表隊(duì)列循環(huán)隊(duì)列的實(shí)現(xiàn)讀隊(duì)頭元素0 1 2 3 4 入隊(duì)a4a5a6出隊(duì)frontreara3 i70隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 鏈隊(duì)列：隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu) 隊(duì)頭指針即為鏈表的頭指針特殊線性表隊(duì)列firsta1a2an如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)？rearfront71隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 特殊線性表隊(duì)列非空鏈隊(duì)列fronta1a2anrear空鏈隊(duì)列frontrear72鏈隊(duì)列類的聲明tem

29、plate class LinkQueue public: LinkQueue( ); LinkQueue( ); void EnQueue(T x); T DeQueue( ); T GetQueue( )； bool Empty( )； private: Node *front, *rear;特殊線性表隊(duì)列73操作接口： LinkQueue( ); 算法描述：template LinkQueue:LinkQueue( ) front=new Node; front-next=NULL; rear=front;特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)構(gòu)造函數(shù)frontrear74 xs特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)入隊(duì)操作接口： void EnQueue(T x);fronta1anrearrearfront xsrearrear算法描述：s-next=NULL;rear-next=s; rear=s;如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？75 xs特殊線性表隊(duì)列鏈隊(duì)列的實(shí)現(xiàn)入隊(duì)操作接口： void EnQueue(T x);fronta2anrearrear算法描述：s-next=NULL;rear-next=s; rear=s;如何沒(méi)有頭結(jié)點(diǎn)會(huì)怎樣？a176 x