數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列

1、國(guó)家教學(xué)資源庫(kù)建設(shè)項(xiàng)目國(guó)家教學(xué)資源庫(kù)建設(shè)項(xiàng)目單元單元3 3 棧和隊(duì)列棧和隊(duì)列2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 教學(xué)目標(biāo)教學(xué)目標(biāo) 【知識(shí)目標(biāo)知識(shí)目標(biāo)】l 掌握棧的定義及基本運(yùn)算l 掌握順序棧、鏈?；具\(yùn)算的實(shí)現(xiàn)算法l 掌握隊(duì)列的定義及基本運(yùn)算l 掌握循環(huán)隊(duì)列、鏈隊(duì)列基本運(yùn)算的實(shí)現(xiàn)算法【能力目標(biāo)能力目標(biāo)】l 具有恰當(dāng)?shù)倪x擇?；蜿?duì)列作為數(shù)據(jù)的邏輯結(jié)構(gòu)，順序棧（隊(duì)列）、鏈棧（隊(duì)列）作為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的能力l 具有應(yīng)用棧、隊(duì)列解決實(shí)際問題的能力單元單元3 3 棧和隊(duì)列棧和隊(duì)列3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 引例描述引例描述數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 將十進(jìn)制數(shù)F轉(zhuǎn)換為B進(jìn)制數(shù)。輸入任意一個(gè)十進(jìn)制數(shù)，可以是整數(shù)，也可以是小數(shù)，輸出對(duì)應(yīng)進(jìn)制的

2、數(shù)。 演示執(zhí)行演示執(zhí)行 單元單元3 3 棧和隊(duì)列棧和隊(duì)列4數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 一、棧的定義及基本操作一、棧的定義及基本操作1.定義定義 棧（Stack）是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。向棧中插入元素稱為進(jìn)（入）棧，從棧中刪除元素稱為出（退）棧。 通常插入、刪除的這一端稱為棧頂（Stack Top），由于元素的進(jìn)棧和退棧，使得棧頂?shù)奈恢媒?jīng)常是變動(dòng)的，因此需要用一個(gè)整型量Top指示棧頂?shù)奈恢?，通常稱Top 為棧頂指針；另一端稱為棧底。當(dāng)表中沒有元素時(shí)稱為空棧，即Top=-1。 棧為后進(jìn)先出（Last In First Out）的線性表，簡(jiǎn)稱為L(zhǎng)IFO表。3.1 棧棧 知識(shí)儲(chǔ)備知識(shí)儲(chǔ)備單

3、元單元3 3 棧和隊(duì)列棧和隊(duì)列5數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 2棧的基本運(yùn)算棧的基本運(yùn)算（1）置空棧：InitStack (S) 構(gòu)造一個(gè)空棧S。（2）判?？眨篠tackEmpty (S) 若S為空棧，則返回1，否則返回0。（3）判棧滿：StackFull (S) 若S為滿棧，則返回1，否則返回0。（4）進(jìn)棧：Push(S，x) 若棧S不滿，則將元素x插入S的棧頂。（5）退棧：Pop (S) 若棧S非空，則將S的棧頂元素刪去，并返回該元素。（6）取棧頂元素：StackTop (S) 若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列6數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 二、順序棧及基本操作的實(shí)

4、現(xiàn)二、順序棧及基本操作的實(shí)現(xiàn) 1順序棧（順序棧（Sequence Stack） 棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，它是運(yùn)算受限的順序表。2順序棧的描述順序棧的描述#define StackSize 100 /假定棧空間最多為100個(gè)元素typedef char DataType;/假定棧元素的類型為字符類型typedef structDataType dataStackSize;/棧元素定義int top;/棧指針定義SeqStack; SeqStack *S;/棧定義單元單元3 3 棧和隊(duì)列棧和隊(duì)列7數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 注意：注意：有元素x進(jìn)棧時(shí)，需要先將S-top加1，然后再將元素進(jìn)棧，即依次完

5、成下列操作：+S-top;S-dataS- top=x;；當(dāng)棧頂元素做退棧操作后，需要將S-top減1，即完成操作：S-top-;；條件S-top=StackSize-1表示棧滿；S-top=-1表示?？眨划?dāng)棧滿時(shí)，再做進(jìn)棧運(yùn)算所產(chǎn)生的空間溢出現(xiàn)象稱為上溢。上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免；當(dāng)棧空時(shí)，做退棧運(yùn)算所產(chǎn)生的溢出現(xiàn)象稱為下溢。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列8數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3順序棧上基本運(yùn)算的算法順序棧上基本運(yùn)算的算法（1）置?？眨┲脳？眨?）判?？眨┡袟？?如果棧S為空，則S-top=-1，此時(shí)應(yīng)該返回1，而關(guān)系表達(dá)式S-top=-1的值為1；如果棧S為非空，則S-top!=-

6、1，此時(shí)應(yīng)該返回0，而關(guān)系表達(dá)式S-top=-1的值為0，因此，無論怎樣只需返回S-top=-1的值。（3）判棧滿）判棧滿 與判棧空的道理相同，只需返回S-top=StackSize-1。（4）進(jìn)棧）進(jìn)棧（5）出棧）出棧（6）取棧頂元素）取棧頂元素（1）置?？眨┲脳？誺oid InitStack(SeqStack *S)/將順序棧置空S-top=-1;（2）判棧空）判?？読nt StackEmpty(SeqStack *S)/判?？誶eturn S-top=-1;（3）判棧滿）判棧滿int StackFull(SeqStack *S)/判棧滿return S-top=StackSize-1;（

7、4）進(jìn)棧）進(jìn)棧int Push(SeqStack *S,DataType x)/進(jìn)棧if (StackFull(S)puts(棧滿); return 0; S-data+S-top=x; return 1;（5）出棧）出棧int Pop(SeqStack *S, DataType *x)/出棧if(StackEmpty(S)puts(?？?; return 0; *x=S-dataS-top-;return 1;（6）取棧頂元素）取棧頂元素int StackTop(SeqStack *S, DataType *x)if(StackEmpty(S)puts(?？?; return 0;*x=S-

8、dataS-top; return 1;單元單元3 3 棧和隊(duì)列棧和隊(duì)列9數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 【例例3-1】元素a1，a2，a3，a4依次進(jìn)入順序棧，則下列不可能的出棧序列是Aa4, a3, a2, a1Ba3, a2, a4, a1Ca3, a4, a2, a1Da3, a1, a4, a2分析：分析：對(duì)于A，由于元素a1，a2，a3，a4依次進(jìn)棧，而a4先出棧，說明a1，a2，a3已經(jīng)入棧，所以出棧順序只能是a4，a3，a2，a1，因此A是正確的出棧序列；對(duì)于B，C，D，由于都是a3先出棧，說明a1，a2已經(jīng)入棧，所以a1，a2的相對(duì)位置一定是不變的，這就是a2一定在a1之前出棧，比較上述三

9、個(gè)答案，只有D中的a1出現(xiàn)在a2的前面，這顯然是錯(cuò)誤的。因此，答案為D。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列10數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 【課堂實(shí)踐【課堂實(shí)踐3-1】 設(shè)計(jì)一個(gè)選擇菜單，根據(jù)用戶的選擇決定對(duì)順序棧進(jìn)行置空棧、進(jìn)棧、退棧、取棧頂元素和退出程序的操作。 做做一一做做單元單元3 3 棧和隊(duì)列棧和隊(duì)列11數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 三、鏈棧及基本操作的實(shí)現(xiàn)三、鏈棧及基本操作的實(shí)現(xiàn) 1鏈棧（鏈棧（Linked Stack） 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧，棧頂指針就是鏈表的頭指針。 2鏈棧的描述鏈棧的描述typedef char DataType;/假定棧元素的類型為字符類型typedef struct stac

10、knode/結(jié)點(diǎn)的描述DataType data;struct stacknode *next;StackNode;typedef struct/棧的描述StackNode *top; /棧頂指針LinkStack; 單元單元3 3 棧和隊(duì)列棧和隊(duì)列12數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 注意：注意：LinkStack結(jié)構(gòu)類型的定義是為了方便在函數(shù)體中修改top指針本身；若要記錄棧中元素個(gè)數(shù)，可將元素個(gè)數(shù)屬性作為L(zhǎng)inkStack類型中的成員定義； 條件S-top= NULL表示空棧，鏈棧沒有棧滿的情況。 3鏈棧上基本運(yùn)算的算法鏈棧上基本運(yùn)算的算法（1）置?？眨┲脳？眨?）判?？眨┡袟？眨?）進(jìn)棧）進(jìn)棧（4）出

11、棧）出棧（5）取棧頂元素）取棧頂元素（1）置?？眨┲脳？誺oid InitStack(LinkStack *S)/將鏈棧置空S-top=NULL; （2）判棧空）判?？読nt StackEmpty(LinkStack *S)return S-top=NULL; （3）進(jìn)棧）進(jìn)棧int Push(LinkStack *S,DataType x)/將元素x插入鏈棧頭部StackNode *p=(StackNode *)malloc(sizeof(StackNode);if(p=NULL) puts (內(nèi)存申請(qǐng)不成功!);return 0;p-data=x;p-next=S-top;/將新結(jié)點(diǎn)*p插

12、入鏈棧頭部S-top=p; /棧頂指針指向新結(jié)點(diǎn)return 1; （4）出棧）出棧int Pop(LinkStack *S, DataType *x)/出棧StackNode *p=S-top;/保存棧頂指針if(StackEmpty(S)puts(?？?; return 0;*x=p-data; /保存棧頂結(jié)點(diǎn)數(shù)據(jù)S-top=p-next; /將棧頂結(jié)點(diǎn)從鏈上摘下free(p);return 1; （5）取棧頂元素）取棧頂元素int StackTop(LinkStack *S, DataType *x)/取棧頂元素if(StackEmpty(S)puts(棧空); return 0; *x

13、 =S-top-data;return 1; 單元單元3 3 棧和隊(duì)列棧和隊(duì)列13數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 【課堂實(shí)踐【課堂實(shí)踐3-2】 設(shè)計(jì)一個(gè)選擇菜單，根據(jù)用戶的選擇決定對(duì)鏈棧進(jìn)行置空棧、進(jìn)棧、出棧、取棧頂元素和退出程序的操作。 做做一一做做單元單元3 3 棧和隊(duì)列棧和隊(duì)列14數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3.2 隊(duì)列隊(duì)列一、隊(duì)列的定義及基本操作一、隊(duì)列的定義及基本操作1隊(duì)列的定義隊(duì)列的定義 隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。向隊(duì)列中插入元素稱為入隊(duì)，從隊(duì)列中刪除元素稱為出隊(duì)。(1)允許刪除的一端稱為隊(duì)頭（Front）。 (2)允許插入的一端稱為隊(duì)尾（Rear）。

14、(3)當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。(4)隊(duì)列亦稱作先進(jìn)先出（First In First Out）的線性表，簡(jiǎn)稱為FIFO表。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列15數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 2隊(duì)列的基本運(yùn)算隊(duì)列的基本運(yùn)算（1）置空隊(duì)：InitQueue (Q)構(gòu)造一個(gè)空隊(duì)列Q。（2）判隊(duì)空：QueueEmpty (Q)若隊(duì)列Q為空，則返回1，否則返回0。（3）判隊(duì)滿：QueueFull (Q)若隊(duì)列Q為滿，則返回1，否則返回0。（4）入隊(duì)：EnQueue(Q，x)若隊(duì)列Q非滿，則將元素x插入Q的隊(duì)尾。（5）出隊(duì)：DeQueue (Q)若隊(duì)列Q非空，則刪去Q的隊(duì)頭元素，并返回該元素。 08順序隊(duì)列操作

15、.swf（6） 取隊(duì)頭元素：QueueFront (Q)若隊(duì)列Q非空，則返回隊(duì)頭元素，但不改變隊(duì)列Q的狀態(tài)。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列16數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 二、順序隊(duì)列及基本操作二、順序隊(duì)列及基本操作1順序隊(duì)列（順序隊(duì)列（Sequence Queue） 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，它是運(yùn)算受限的順序表。2順序隊(duì)列的表示順序隊(duì)列的表示 （1）和順序表一樣，順序隊(duì)列用一個(gè)數(shù)組（向量空間）來存放當(dāng)前隊(duì)列中的元素。（2）由于隨著入隊(duì)和出隊(duì)操作的變化，隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變動(dòng)的，所以應(yīng)設(shè)置兩個(gè)整型量front和rear分別指示隊(duì)頭和隊(duì)尾在向量空間中的位置，它們的初值在隊(duì)列初始化時(shí)均應(yīng)置為

16、0。通常稱front為隊(duì)頭指針，稱rear為隊(duì)尾指針。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列17數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3順序隊(duì)列的基本操作順序隊(duì)列的基本操作（1）入隊(duì)：入隊(duì)時(shí)將新元素插入rear所指的位置，然后將rear加1。（2）出隊(duì)：出隊(duì)時(shí)刪去front所指的元素，然后將front加1并返回被刪元素。注意：注意：（1）當(dāng)頭尾指針相等時(shí)，隊(duì)列為空。（2）在非空隊(duì)列里，隊(duì)頭指針始終指向隊(duì)頭元素，尾指針始終指向隊(duì)尾元素的下一位置。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列18數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 4順序隊(duì)列中的溢出現(xiàn)象順序隊(duì)列中的溢出現(xiàn)象（1）“下溢”現(xiàn)象：當(dāng)隊(duì)列為空時(shí)，做出隊(duì)操作產(chǎn)生的溢出現(xiàn)象。（2）“真上溢”現(xiàn)

17、象：當(dāng)隊(duì)列滿時(shí)，做入隊(duì)操作產(chǎn)生空間溢出的現(xiàn)象?！罢嫔弦纭笔且环N出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。（3）“假上溢”現(xiàn)象：由于入隊(duì)和出隊(duì)操作中，頭尾指針只增加不減少，致使被刪元素的空間永遠(yuǎn)無法重新利用。當(dāng)隊(duì)列中實(shí)際元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模時(shí)，也可能由于尾指針已超越向量空間的上界而不能做入隊(duì)操作。該現(xiàn)象稱為“假上溢”現(xiàn)象。 5解決解決“假上溢假上溢”現(xiàn)象的方法現(xiàn)象的方法（1）當(dāng)出現(xiàn)“假上溢”現(xiàn)象時(shí)，把所有的元素向低位移動(dòng)，使得空位從低位區(qū)移向高位區(qū)，顯然這種方法很浪費(fèi)時(shí)間。（2）把隊(duì)列的向量空間的元素位置0Queuesize-1看成一個(gè)首尾相接的環(huán)形，當(dāng)進(jìn)隊(duì)的隊(duì)尾指針等于最大容量，即rear=Queues

18、ize時(shí)，使rear=0。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列19數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 三、循環(huán)隊(duì)列三、循環(huán)隊(duì)列1循環(huán)隊(duì)列（循環(huán)隊(duì)列（Cirular Queue） 把向量空間的元素位置首尾相接的順序隊(duì)列稱為循環(huán)隊(duì)列。 2循環(huán)隊(duì)列頭尾指針的操作循環(huán)隊(duì)列頭尾指針的操作 循環(huán)隊(duì)列Q進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1。當(dāng)頭尾指針指向向量上界（QueueSize-1）時(shí)，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為： （1）利用選擇結(jié)構(gòu)）利用選擇結(jié)構(gòu)（2）利用模運(yùn)算）利用模運(yùn)算 我們將采用此方法實(shí)現(xiàn)循環(huán)意義下的隊(duì)頭、隊(duì)尾指針的加1操作。 （1）利用選擇結(jié)構(gòu)）利用選擇結(jié)構(gòu)if(i+

19、1=QueueSize)/i為Q-front或Q-reari=0;elsei+; （2）利用模運(yùn)算）利用模運(yùn)算i=(i+1)%QueueSize;/i為Q-front或Q-rear單元單元3 3 棧和隊(duì)列棧和隊(duì)列20數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3循環(huán)隊(duì)列邊界條件的處理方法循環(huán)隊(duì)列邊界條件的處理方法 由于循環(huán)隊(duì)列Q中，無法通過條件Q-front= Q-rear來判別隊(duì)列是“空”還是“滿”。解決這個(gè)問題的方法至少有三種：（1）另設(shè)一標(biāo)志變量flag以區(qū)別隊(duì)列的空和滿，比如當(dāng)條件Q-front= Q-rear成立，且 flag 為0時(shí)表示隊(duì)列空，而為1時(shí)表示隊(duì)列滿。（2）少用一個(gè)元素的空間。約定入隊(duì)前，測(cè)試尾

20、指針在循環(huán)意義下加1后是否等于隊(duì)頭指針，若相等則認(rèn)為隊(duì)滿，此時(shí)隊(duì)空的條件是Q-front= Q-rear，隊(duì)滿的條件是(Q-rear+1)%QueueSize= Q-front。（3）使用一個(gè)計(jì)數(shù)器count記錄隊(duì)列中元素的總數(shù)，當(dāng)Q-count =0時(shí)表示隊(duì)列空；當(dāng)Q-count =QueueSize時(shí)表示隊(duì)列滿。 我們將使用此方法。 單元單元3 3 棧和隊(duì)列棧和隊(duì)列21數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 4循環(huán)隊(duì)列的描述循環(huán)隊(duì)列的描述#define QueueSize 100 /定義隊(duì)列最大容量typedef char DataType; /定義隊(duì)列元素類型typedef struct cirqueueDa

21、taType dataQueueSize;/隊(duì)列元素定義int front;/隊(duì)頭指針定義int rear;/隊(duì)尾指針定義int count;/計(jì)數(shù)器定義CirQueue; CirQueue *Q; /定義循環(huán)隊(duì)列Q 單元單元3 3 棧和隊(duì)列棧和隊(duì)列22數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 5循環(huán)隊(duì)列的基本運(yùn)算的算法循環(huán)隊(duì)列的基本運(yùn)算的算法（1） 置隊(duì)空置隊(duì)空（2）判隊(duì)空）判隊(duì)空（3）判隊(duì)滿）判隊(duì)滿（4）入隊(duì)）入隊(duì) （5）出隊(duì)）出隊(duì)（6）取隊(duì)頭元素）取隊(duì)頭元素（1） 置隊(duì)空置隊(duì)空void InitQueue(CirQueue *Q)Q-front=Q-rear=0;Q-count=0;/計(jì)數(shù)器置0 （2）判隊(duì)空）

22、判隊(duì)空int QueueEmpty(CirQueue *Q)return Q-count=0; /隊(duì)列無元素為空（3）判隊(duì)滿）判隊(duì)滿int QueueFull(CirQueue *Q)return Q-count=QueueSize;（4）入隊(duì)）入隊(duì) int EnQueue(CirQueue *Q,DataType x)if(QueueFull(Q) puts(隊(duì)滿); return 0;Q-count +;/隊(duì)列元素個(gè)數(shù)加1Q-dataQ-rear=x;/新元素插入隊(duì)尾Q-rear=(Q-rear+1)%QueueSize;/循環(huán)意義下將尾指針加1return 1;（5）出隊(duì)）出隊(duì)int D

23、eQueue(CirQueue *Q ,DataType *x)if(QueueEmpty(Q)puts(隊(duì)空); return 0;*x=Q-dataQ-front;Q-count-;/隊(duì)列元素個(gè)數(shù)減1Q-front=(Q-front+1)%QueueSize;/循環(huán)意義下的頭指針加1return 1; （6）取隊(duì)頭元素）取隊(duì)頭元素 int QueueFront(CirQueue *Q ,DataType *x)if(QueueEmpty(Q)puts(隊(duì)空); return 0; *x=Q-dataQ-front; return 1; 單元單元3 3 棧和隊(duì)列棧和隊(duì)列23數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

24、【課堂實(shí)踐【課堂實(shí)踐3-3】 設(shè)計(jì)一個(gè)選擇菜單，根據(jù)用戶的選擇決定對(duì)循環(huán)隊(duì)列進(jìn)行置空隊(duì)、進(jìn)隊(duì)、退隊(duì)、取隊(duì)頭元素和退出程序的操作。 做做一一做做單元單元3 3 棧和隊(duì)列棧和隊(duì)列24數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 四、鏈隊(duì)列及基本操作的實(shí)現(xiàn)四、鏈隊(duì)列及基本操作的實(shí)現(xiàn)1鏈隊(duì)列（鏈隊(duì)列（Linked Queue） 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插入的單鏈表。由于需要在表尾進(jìn)行插入操作，所以為操作方便除頭指針外有必要再增加一個(gè)指向尾結(jié)點(diǎn)的指針。2鏈隊(duì)列的描述鏈隊(duì)列的描述 設(shè)Q是LinkQueue類型的指針變量，則Q是指向鏈隊(duì)列的指針，隊(duì)頭指針、隊(duì)尾指可分別表示為Q-front、Q- rear

25、。 設(shè)p是QueueNode類型的指針變量，則p是指向鏈隊(duì)列某結(jié)點(diǎn)的指針，該結(jié)點(diǎn)的數(shù)據(jù)域可表示為p -data，該結(jié)點(diǎn)的指針域可表示為p - next。鏈隊(duì)列如圖鏈隊(duì)列如圖3-5：2鏈隊(duì)列的描述鏈隊(duì)列的描述typedef char DataType; /定義隊(duì)列元素類型typedef struct queuenode/隊(duì)列中結(jié)點(diǎn)的類型DataType data;struct queuenode *next;QueueNode;typedef structQueueNode *front; /隊(duì)頭指針QueueNode *rear; /隊(duì)尾指針LinkQueue;LinkQueue *Q; /定

26、義鏈隊(duì)列QQ-frontQ-rear*Q(a)空鏈隊(duì)列空鏈隊(duì)列圖圖3-5 鏈隊(duì)列鏈隊(duì)列隊(duì)頭結(jié)點(diǎn)隊(duì)頭結(jié)點(diǎn)隊(duì)尾結(jié)點(diǎn)隊(duì)尾結(jié)點(diǎn)(b)非空鏈隊(duì)列非空鏈隊(duì)列Q-rearQ-front*Q單元單元3 3 棧和隊(duì)列棧和隊(duì)列25數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3鏈隊(duì)列的基本運(yùn)算鏈隊(duì)列的基本運(yùn)算 由于鏈隊(duì)列結(jié)點(diǎn)的存儲(chǔ)空間是動(dòng)態(tài)分配的，所以無須考慮判隊(duì)滿的運(yùn)算。（1）置隊(duì)空）置隊(duì)空（2）判隊(duì)空）判隊(duì)空（3）入隊(duì)）入隊(duì)（4）出隊(duì)）出隊(duì)（5）取隊(duì)頭元素）取隊(duì)頭元素注意：注意：在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針，且刪去此結(jié)點(diǎn)后隊(duì)列變空。 （1）置隊(duì)空）置隊(duì)

27、空void InitQueue(LinkQueue *Q)Q-front=Q-rear=NULL;（2）判隊(duì)空）判隊(duì)空int QueueEmpty(LinkQueue *Q)return Q-front=NULL;（3）入隊(duì)）入隊(duì)int EnQueue(LinkQueue *Q,DataType x)/將元素將元素x插入鏈隊(duì)列尾部插入鏈隊(duì)列尾部QueueNode *p;p=(QueueNode *)malloc(sizeof(QueueNode);if(p=NULL)puts (空間申請(qǐng)失敗空間申請(qǐng)失敗!);return 0;p-data=x;p-next=NULL;if(QueueEmpty

28、(Q)Q-front=Q-rear=p;/將將x插入空隊(duì)列插入空隊(duì)列else/x插入非空隊(duì)列的尾插入非空隊(duì)列的尾Q-rear-next=p;/*p鏈到原隊(duì)尾結(jié)點(diǎn)后鏈到原隊(duì)尾結(jié)點(diǎn)后Q-rear=p;/隊(duì)尾指針指向新的尾隊(duì)尾指針指向新的尾return 1;（4）出隊(duì)）出隊(duì)int DeQueue(LinkQueue *Q, DataType *x)QueueNode *p;if(QueueEmpty(Q)puts(隊(duì)空隊(duì)空); return 0;p=Q-front;/指向隊(duì)頭結(jié)點(diǎn)指向隊(duì)頭結(jié)點(diǎn)*x=p-data;/保存隊(duì)頭結(jié)點(diǎn)的數(shù)據(jù)保存隊(duì)頭結(jié)點(diǎn)的數(shù)據(jù)Q-front=p-next;/將對(duì)頭結(jié)點(diǎn)從鏈上摘下

29、將對(duì)頭結(jié)點(diǎn)從鏈上摘下if(Q-rear=p）Q-rear=NULL;free(p);/釋放被刪隊(duì)頭結(jié)點(diǎn)釋放被刪隊(duì)頭結(jié)點(diǎn)return 1; （5）取隊(duì)頭元素）取隊(duì)頭元素int QueueFront(LinkQueue *Q, DataType *x)if(QueueEmpty(Q)puts(隊(duì)空); return 0;*x=Q-front-data; return 1;單元單元3 3 棧和隊(duì)列棧和隊(duì)列26數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 【課堂實(shí)踐【課堂實(shí)踐3-4】 設(shè)計(jì)一個(gè)選擇菜單，根據(jù)用戶的選擇決定對(duì)鏈隊(duì)列進(jìn)行置空隊(duì)、進(jìn)隊(duì)、退隊(duì)、取隊(duì)頭元素和退出程序的操作。 做做一一做做單元單元3 3 棧和隊(duì)列棧和隊(duì)列27

30、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 引例分析與實(shí)現(xiàn)引例分析與實(shí)現(xiàn) 1引例分析引例分析 十進(jìn)制數(shù)F可分解為F=N+M，其中N為十進(jìn)制整數(shù)，M為十進(jìn)制純小數(shù)轉(zhuǎn)換為B進(jìn)制數(shù)，分為十進(jìn)制整數(shù)轉(zhuǎn)換為B進(jìn)制整數(shù)和十進(jìn)制純小數(shù)轉(zhuǎn)換為B進(jìn)制純小數(shù)數(shù)兩部分。（1）將十進(jìn)制整數(shù)轉(zhuǎn)換為）將十進(jìn)制整數(shù)轉(zhuǎn)換為B進(jìn)制整數(shù)進(jìn)制整數(shù) 將十進(jìn)制整數(shù)轉(zhuǎn)換為B進(jìn)制整數(shù)，通常采用的方法是“B除取余法”?！臼纠纠繉?65轉(zhuǎn)換為16進(jìn)制數(shù) 采用16除取余法，如圖3-6。 得365轉(zhuǎn)換為16進(jìn)制數(shù)為16D。365余數(shù)余數(shù)16被除數(shù)被除數(shù)/商商除數(shù)除數(shù)221310616161圖圖3-6 B 除取余法除取余法 單元單元3 3 棧和隊(duì)列棧和隊(duì)列28數(shù)據(jù)結(jié)構(gòu)數(shù)

31、據(jù)結(jié)構(gòu) 算法思路：算法思路：定義一個(gè)指向鏈棧的指針S，通過函數(shù)malloc確定S的指向，并對(duì)鏈棧進(jìn)行初始化，當(dāng)N=0時(shí)，輸出一個(gè)0，當(dāng)N!=0時(shí)，重復(fù)進(jìn)行將N被B除的余數(shù)N%B入棧S，并將所得的商N(yùn)/B作為被除數(shù)，即將N/B賦給N，直到N的值為0，這樣，得到的余數(shù)已經(jīng)全部入棧S；只要棧S不空，作出棧操作，并輸出，如果出棧元素大于等于10，通過加87輸出對(duì)應(yīng)字符（基數(shù)大于10的大于等于10的數(shù)碼用對(duì)應(yīng)字母來表示）。 引例分析與實(shí)現(xiàn)引例分析與實(shí)現(xiàn) 單元單元3 3 棧和隊(duì)列棧和隊(duì)列29數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) （2）將十進(jìn)制純小數(shù)轉(zhuǎn)換為）將十進(jìn)制純小數(shù)轉(zhuǎn)換為B進(jìn)制純小數(shù)進(jìn)制純小數(shù) 將十進(jìn)制純小數(shù)轉(zhuǎn)換為B進(jìn)制

32、純小數(shù)，通常采用的方法是“B乘取整法”?！臼纠纠繉?.618轉(zhuǎn)換為16進(jìn)制數(shù)采用16乘取整法，如圖3-7。得0.618轉(zhuǎn)換為16進(jìn)制數(shù)近似為0.9E353F。引例分析與實(shí)現(xiàn)引例分析與實(shí)現(xiàn) 圖圖3-7 B 乘取整法乘取整法 0.618整數(shù)部分整數(shù)部分16被乘數(shù)被乘數(shù)/小數(shù)部分小數(shù)部分乘數(shù)乘數(shù)914161630.8880.2080.3280.248530.9680.48815161616） 16） 16） 16） 16） 16） 16單元單元3 3 棧和隊(duì)列棧和隊(duì)列30數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 算法思路：算法思路：確定一個(gè)精度E，比如E的值為0.000001，當(dāng)M=E時(shí)，輸出一個(gè)小數(shù)點(diǎn).，并重復(fù)進(jìn)行將M被B乘的整數(shù)部分(int)(M*B)入隊(duì)Q，并將所得的小數(shù)部分M*B-(int)(M*B)作為被乘數(shù)，即將M*B-(int)(M*B)賦給M，直到M的值小于E或j值超過隊(duì)列的最大容量QueueSize，這樣，得到的整數(shù)已經(jīng)全部入隊(duì)Q；只要隊(duì)Q不空，作出隊(duì)操作，并輸出，如果出隊(duì)元素大于等于10，通過加87輸出對(duì)應(yīng)字符。 引例分析與實(shí)現(xiàn)引例分析與實(shí)現(xiàn) 單元單元3 3 棧和隊(duì)列棧和隊(duì)列31數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 2引例實(shí)現(xiàn)引例實(shí)現(xiàn)（1）將十進(jìn)制