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

1、數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社第第3章章 棧和隊列棧和隊列 本章要點：棧和隊列兩種抽象數(shù)據(jù)類型的特點。棧用兩種存儲結(jié)構(gòu)表示時的基本操作算法的實現(xiàn)。棧和隊列的應(yīng)用。數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社 線性表的操作允計在表的任何位置進行。線性表的操作允計在表的任何位置進行。 本章介紹的兩種特殊的線性表，是操作本章介紹的兩種特殊的線性表，是操作受限制的特殊線性表受限制的特殊線性表棧棧(Stack)(Stack)和隊列和隊列(Queue)(Queue)，其特殊性在于限制了插入和刪除等，其特殊性在于限制了插入和刪除等運算的位置。運算的位置。數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1 棧棧 棧是用來保存

2、一些尚未處理而又等待處理的數(shù)據(jù)項這些數(shù)據(jù)項的處理是依據(jù)后進先出的規(guī)則。因此，經(jīng)常把棧叫做后進先出線性表。 棧在日常生活中幾乎到處可見，如火車進庫時，庫的一端是堵死的，那么最后入庫的火車必須先出來，否則前面的列車都被堵住，無法倒出。棧是這種事務(wù)的一種抽象。 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.1 棧的意義及抽象數(shù)據(jù)類型棧的意義及抽象數(shù)據(jù)類型 棧棧是將線性表的插入和刪除運算限制為僅在表的一端進行的線性表。通常將表中允許進行插入、刪除操作的一端稱為棧頂棧頂(Top)。棧頂?shù)漠?dāng)前位置是動態(tài)變化的，表的另一端稱為棧底棧底(Bottom)。當(dāng)棧中沒有元素時稱為空?？諚?。棧的插入操作被形象地稱為進棧或

3、入棧，刪除操作稱為出?；蛲藯?。不含元素的棧稱為空棧。 假設(shè)棧s=（a1，a2，an），a1元素所在的位子稱為棧底，an元素所在的位子稱為棧頂，如圖3.1所示。數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社 進棧順序是進棧順序是a1，a2an，退棧的第一個，退棧的第一個元素是元素是an，最后一個元，最后一個元素是素是a a1 1是按是按“后進先出后進先出”的原則進行的，因此棧的原則進行的，因此棧又稱為后進先出（又稱為后進先出（Last Last In First OutIn First Out），縮寫），縮寫為（為（LIFO）的線性表。）的線性表。圖圖3.1 3.1 棧棧bottomtop ana3a2a1

4、3.1.1 棧的意義及抽象數(shù)據(jù)類型（續(xù)）棧的意義及抽象數(shù)據(jù)類型（續(xù)） 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社進棧進棧出棧出棧圖圖3.23.2鐵路調(diào)度棧示意圖鐵路調(diào)度棧示意圖 圖圖3.23.2為鐵路調(diào)度中棧為鐵路調(diào)度中棧的應(yīng)用。在日常生活中還的應(yīng)用。在日常生活中還有一些類似棧的例子。例有一些類似棧的例子。例如：往箱子里放衣物，這如：往箱子里放衣物，這相當(dāng)于進棧最先放的衣服相當(dāng)于進棧最先放的衣服在箱底（棧底），最后放在箱底（棧底），最后放的在箱頂（棧頂），取時的在箱頂（棧頂），取時應(yīng)先從箱頂開始拿，這相應(yīng)先從箱頂開始拿，這相當(dāng)于出棧操作。當(dāng)于出棧操作。 3.1.1 棧的意義及抽象數(shù)據(jù)類型（續(xù)）棧的意義

5、及抽象數(shù)據(jù)類型（續(xù)） 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.1 棧的意義及抽象數(shù)據(jù)類型（續(xù)）棧的意義及抽象數(shù)據(jù)類型（續(xù)） 棧的基本操作除了在棧頂進行插入或刪除外，還有棧的初棧的基本操作除了在棧頂進行插入或刪除外，還有棧的初始化、清空及取棧頂元素等，下面給出棧的抽象數(shù)據(jù)類型定始化、清空及取棧頂元素等，下面給出棧的抽象數(shù)據(jù)類型定義：義：ADT ADT stack 數(shù)據(jù)元素數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象。對象。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系。：棧中數(shù)據(jù)元素之間是線性關(guān)系。 基本操作基本操作： InitStack

6、(SInitStack(S) )：將：將S S初始化為空棧。初始化為空棧。 ClearStack(SClearStack(S) )：棧：棧S S已經(jīng)存在，將棧已經(jīng)存在，將棧S S置成空棧。置成空棧。 EmptyStack(SEmptyStack(S) )：棧：棧S S已經(jīng)存在，判斷若已經(jīng)存在，判斷若S S為空，函數(shù)值返回為空，函數(shù)值返回TRUETRUE，否則返，否則返FALSEFALSE。數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社 DestroyStack(S DestroyStack(S) )：棧：棧S S已經(jīng)存在，銷毀棧并釋放空間。已經(jīng)存在，銷毀棧并釋放空間。 Push(S,x) Push(S,x

7、)：棧：棧S S已經(jīng)存在，若已經(jīng)存在，若S S棧未滿，將棧未滿，將x x插入插入S S棧的棧頂位棧的棧頂位置，函數(shù)返回置，函數(shù)返回TRUETRUE；若；若S S棧已滿，則返回棧已滿，則返回FALSEFALSE，表示操作失敗。，表示操作失敗。 Pop(S, x) Pop(S, x)：棧：棧S S已經(jīng)存在，在棧已經(jīng)存在，在棧S S的頂部彈出棧頂元素，并用的頂部彈出棧頂元素，并用x x帶回該值；若棧為空，返回值為帶回該值；若棧為空，返回值為FALSEFALSE，表示操作失敗，否則，表示操作失敗，否則返回返回TRUETRUE。 GetTop(S GetTop(S, x), x)：棧：棧S S已經(jīng)存在，

8、取棧已經(jīng)存在，取棧S S的棧頂元素，其余不變。的棧頂元素，其余不變。(8)Stacklenth(S)(8)Stacklenth(S)棧棧S S已經(jīng)存在，返回棧中元素個數(shù)。已經(jīng)存在，返回棧中元素個數(shù)。 ADT ADT stack3.1.1 棧的意義及抽象數(shù)據(jù)類型（續(xù)）棧的意義及抽象數(shù)據(jù)類型（續(xù)） 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)棧操作的實現(xiàn) 與線性表一樣，棧的存儲方式也有兩種：順序存儲和鏈表存與線性表一樣，棧的存儲方式也有兩種：順序存儲和鏈表存儲方式。儲方式。 3.1.2.1 棧的順序存儲結(jié)構(gòu)棧的順序存儲結(jié)構(gòu) 棧的順序存儲結(jié)構(gòu)即順序棧是分配一塊連續(xù)的存儲區(qū)域棧的順序存儲

9、結(jié)構(gòu)即順序棧是分配一塊連續(xù)的存儲區(qū)域依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時設(shè)指針依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時設(shè)指針toptop來動態(tài)來動態(tài)地指示棧頂元素的當(dāng)前位置?？諚５刂甘緱ｍ斣氐漠?dāng)前位置?？諚op=0top=0或或 top=-1top=-1表示。下表示。下面的順序棧，采用的是面的順序棧，采用的是toptop指向棧頂元素的后一個元素位置指向棧頂元素的后一個元素位置的方式來描述，當(dāng)空棧時的方式來描述，當(dāng)空棧時top=0top=0。順序棧的存儲結(jié)構(gòu)可以用。順序棧的存儲結(jié)構(gòu)可以用C C語言中的一維數(shù)組來表示。棧的順序存儲結(jié)構(gòu)定義如下：語言中的一維數(shù)組來表示。棧的順序存儲結(jié)構(gòu)定義如下：數(shù)據(jù)

10、結(jié)構(gòu)C語言描述出出 版版 社社define Stack-Size 50define Stack-Size 50typedef structtypedef struct elemtype elemStackelemtype elemStack-Size-Size； /*存放棧元素的一維數(shù)組*/intint top top； /*存放棧頂元素的下標(biāo)*/ SeqStack SeqStack； 若若s s為為SeqStackSeqStack類型變量，則類型變量，則s.elem0s.elem0存放棧中第一個元素，存放棧中第一個元素，s.elems.top-1s.elems.top-1為最后一個元素（棧頂

11、元素）。當(dāng)為最后一個元素（棧頂元素）。當(dāng)s.top=s.top= Stack-SizeStack-Size時為時為棧滿，此時若再有元素入棧則將產(chǎn)生越界的錯誤，稱為棧上溢棧滿，此時若再有元素入棧則將產(chǎn)生越界的錯誤，稱為棧上溢(overflow)(overflow)，反之反之,top=0 ,top=0 時為?？?，這時若執(zhí)行出棧操作則產(chǎn)生下溢的錯誤時為?？?，這時若執(zhí)行出棧操作則產(chǎn)生下溢的錯誤(underflow)(underflow)。圖圖3.33.3表示了順序棧中數(shù)據(jù)元素和棧頂指針之間的對應(yīng)關(guān)系。表示了順序棧中數(shù)據(jù)元素和棧頂指針之間的對應(yīng)關(guān)系。 3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 數(shù)

12、據(jù)結(jié)構(gòu)C語言描述出出 版版 社社(a) (a) 空?？諚?(b) A(b) A進棧進棧 (c) B(c) B進棧進棧 (d) C(d) C、D D、E E、進棧、進棧 圖圖3.3 3.3 棧頂指針和棧中元素之間的關(guān)系棧頂指針和棧中元素之間的關(guān)系top=0top=1top=2top=5ABABAEDC3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社順序棧中幾種操作算法的實現(xiàn)。順序棧中幾種操作算法的實現(xiàn)。進棧進棧/ /* *在在S S棧中插入元素棧中插入元素x x，成功返回真失敗返回假，成功返回真失敗返回假* */ /int Push(SeqStack int

13、Push(SeqStack * *S, elemtypeS, elemtype x) x) if(S-top = Stack-Size)if(S-top = Stack-Size) return FALSE return FALSE ； / /* *棧滿不能插入元素返回假值棧滿不能插入元素返回假值* */ / S-elem S-elemS-topS-top=x=x； S-top+S-top+； return TRUEreturn TRUE； / /* *成功將元素入棧，返回真值成功將元素入棧，返回真值* */ / 3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版

14、社社出棧出棧/ /* * 將棧將棧S S的棧頂元素彈出，放到的棧頂元素彈出，放到x x所指的存儲空間中所指的存儲空間中 * */ / int Pop(SeqStack int Pop(SeqStack * * S, elemtype S, elemtype * *x)x) if(S-top=0) return FALSE if(S-top=0) return FALSE； / /* *棧為空返回假值棧為空返回假值* */ / elseelse S-top-S-top-； / /* *修改棧頂指針修改棧頂指針* */ / * *x= S-elemSx= S-elemS-top-top； retu

15、rn TRUEreturn TRUE； / /* *成功出棧，返回真值成功出棧，返回真值* */ / 3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 取棧頂元素取棧頂元素 / /* * 將棧將棧S S的棧頂元素彈出，的棧頂元素彈出， 放到放到x x所指的存儲空間中所指的存儲空間中* */ / int GetTop int GetTop（SeqStack S, elemtypeSeqStack S, elemtype * *x x） if(S-top= if(S-top=) return FALSE) retu

16、rn FALSE； / /* *棧為空，結(jié)束返回假值棧為空，結(jié)束返回假值* */ / else else * *x = S-elemSx = S-elemS-top -top - ； / /* *取棧頂數(shù)據(jù)，存放在取棧頂數(shù)據(jù)，存放在x x中中* */ / return TRUE return TRUE ； 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） (4) (4)求棧中元素個數(shù)求棧中元素個數(shù) int Stacklength(SeqStackint Stacklength(SeqStack S) S) / /* *返回棧中當(dāng)前元素的個數(shù)返回棧中當(dāng)前元素的個

17、數(shù) * */ / return S-top; return S-top; 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 在棧的共享技術(shù)中最常用的是兩個棧的共享技術(shù)：如圖在棧的共享技術(shù)中最常用的是兩個棧的共享技術(shù)：如圖3.43.4所示，兩個棧共享空間所示，兩個棧共享空間, ,它主要利用了棧它主要利用了?！皸５孜恢貌蛔儯瑮５孜恢貌蛔?，而棧頂位置動態(tài)變化而棧頂位置動態(tài)變化”的特性。的特性。 首先為兩個棧申請一個首先為兩個棧申請一個共享的一維數(shù)組空間共享的一維數(shù)組空間SMSM，將兩個棧的棧底分別放在一維數(shù)，將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是組的兩端，分別

18、是0 0，M-1M-1。由于兩個棧頂動態(tài)變化，這樣可。由于兩個棧頂動態(tài)變化，這樣可以形成互補，使得每個棧可用的最大空間與實際使用的需求以形成互補，使得每個棧可用的最大空間與實際使用的需求有關(guān)。有關(guān)。 0 top0 top1 M-1 top0 top1 M-1圖圖3.4 3.4 二棧共享空間二棧共享空間數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 由此可見，兩棧共享比兩個棧分別申請由此可見，兩棧共享比兩個棧分別申請M/2M/2的空的空間利用率高。兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義如下：間利用率高。兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義如下： define M 100define M 1

19、00 typedef structtypedef struct elemtypeelemtype StackM StackM； / /* *存儲兩個棧的數(shù)據(jù)元素存儲兩個棧的數(shù)據(jù)元素* */ / int int top2 top2； / /* *toptop數(shù)組為兩個棧頂數(shù)組為兩個棧頂* */ / DseqStack DseqStack；數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)）下面是二棧共享的一些操作算法。下面是二棧共享的一些操作算法。 初始化操作初始化操作void InitStack(DseqStackvoid InitStack(DseqStack

20、* *S)S) S-top0= 0 S-top0= 0； / /* *第一個棧的棧頂初值為第一個棧的棧頂初值為* */ / S-top1=M-1 S-top1=M-1； / /* *第二個棧的棧頂初值為第二個棧的棧頂初值為M-1M-1* */ / 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 進棧操作進棧操作/ /* *將數(shù)據(jù)元素將數(shù)據(jù)元素x x壓入壓入i i號堆棧，圖號堆棧，圖3.43.4中中 i=0 i=0 、1 1分別表示兩個棧。分別表示兩個棧。* */ /int Push(DseqStack int Push(DseqStack * *S, ele

21、mtype x, intS, elemtype x, int i) i) if(S-top0+1=S-top1-1) / if(S-top0+1=S-top1-1) /* *棧滿棧滿* */ / return FALSEreturn FALSE； switch(i) switch(i) case 0: S-Stack case 0: S-StackS-topS-top0 0=x=x； / /* *從第一個入棧從第一個入棧* */ / S-top S-top0 0+； breakbreak； case 1: S-Stackcase 1: S-StackS-topS-top1 1=x=x； / /

22、* *從第二個入棧從第二個入棧* */ / S-top1- S-top1-；breakbreak； default: return FALSEdefault: return FALSE； / /* *參數(shù)錯誤參數(shù)錯誤* */ / return TRUE return TRUE ； 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 出棧操作出棧操作int Pop(DseqStack int Pop(DseqStack * *S, elemtype S, elemtype * *x, intx, int i) i) / /* * 從從i i 號堆棧中彈出棧頂元素并

23、送到號堆棧中彈出棧頂元素并送到x x中中 * */ / switch(i)switch(i) case 0:if(S-top0= case 0:if(S-top0=) return FALSE) return FALSE； / /* *從左邊出棧從左邊出棧* */ / * *x=S-StackS-top0-1x=S-StackS-top0-1； S-top0- -S-top0- -； breakbreak； case 1:if(S-top1=M-1) return FALSEcase 1:if(S-top1=M-1) return FALSE；/ /* *從右邊出棧從右邊出棧* */ / *

24、*x=S-StackS-top1+1x=S-StackS-top1+1； S-topS-top1 1+； breakbreak； default:return FALSEdefault:return FALSE； / /* *參數(shù)錯誤參數(shù)錯誤* */ / return TRUEreturn TRUE； 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)）3.1.2.2棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖3.53.5所示，是一個單鏈表結(jié)構(gòu)。棧頂指針是鏈表的的所示，是一個單鏈表結(jié)構(gòu)。棧頂指針是鏈表的的第一個結(jié)點，棧底指針指向鏈表的最

25、后一個結(jié)點。類型說明如下：第一個結(jié)點，棧底指針指向鏈表的最后一個結(jié)點。類型說明如下：typedef structtypedef struct node node elemtypeelemtype data data； / /* *數(shù)據(jù)域數(shù)據(jù)域 * */ / struct struct node node * *nextnext；/ /* *指針域指針域 * */ / * *LinkStackLinkStack； 棧頂棧頂 S1 S2 Sn 圖圖3.5 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)棧底棧底數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 對于鏈?zhǔn)浇Y(jié)構(gòu)一般不會

26、有溢出，只有內(nèi)存可用空間都被占滿，對于鏈?zhǔn)浇Y(jié)構(gòu)一般不會有溢出，只有內(nèi)存可用空間都被占滿，mallocmalloc()()過程無法實現(xiàn)才會產(chǎn)生上溢。因此過程無法實現(xiàn)才會產(chǎn)生上溢。因此, ,多個鏈棧共享空間很容易。多個鏈棧共享空間很容易。下面給出鏈鏈?zhǔn)綏５幕静僮魉惴ǎ合旅娼o出鏈鏈?zhǔn)綏５幕静僮魉惴ǎ?進棧操作進棧操作int Push(LinkStack top, elemtypeint Push(LinkStack top, elemtype x) x) / /* * 將數(shù)據(jù)元素將數(shù)據(jù)元素x x壓入棧頂為壓入棧頂為toptop的鏈?zhǔn)綏Ｖ械逆準(zhǔn)綏Ｖ?* */ / temp=(LinkStack)m

27、alloc(sizeof(struct temp=(LinkStack)malloc(sizeof(struct node) node)；/ /* *創(chuàng)建結(jié)點創(chuàng)建結(jié)點* */ / if(temp=NULL) return FALSE if(temp=NULL) return FALSE；/ /* *申請空間失敗結(jié)束，返回假值申請空間失敗結(jié)束，返回假值* */ / temp-data=x temp-data=x； temp-next=toptemp-next=top； / /* * 新結(jié)點壓入棧頂新結(jié)點壓入棧頂 * */ / top=temp top=temp； / /* * 修改當(dāng)前棧頂指針修

28、改當(dāng)前棧頂指針 * */ / return TRUEreturn TRUE； 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 出棧操作出棧操作int Pop(LinkStack top, elemtypeint Pop(LinkStack top, elemtype * *x)x) / /* *將鏈棧的棧頂將鏈棧的棧頂toptop元素彈出，存儲到元素彈出，存儲到x x* */ / temp=top temp=top； / /* * 將棧頂指針存入將棧頂指針存入temptemp中中* */ / if(temp=NULL) return FALSE if(tem

29、p=NULL) return FALSE；/ /* *?？?，返回假值棧空，返回假值* */ / top=temp-nexttop=temp-next； / /* *棧頂指針下移棧頂指針下移* */ / * *x=temp-datax=temp-data； / /* *棧頂元素賦值給棧頂元素賦值給x x* */ / free temp free temp； / /* * 釋放存儲空間釋放存儲空間 * */ / return TRUE return TRUE； 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.1.2 棧操作的實現(xiàn)（續(xù)）棧操作的實現(xiàn)（續(xù)） 棧是一種操作上受限制的線性表，插入棧是一種操作上受限制

30、的線性表，插入和刪除不能隨機進行（只能在一端）。從線和刪除不能隨機進行（只能在一端）。從線性表順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點看，棧的順性表順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點看，棧的順序存儲結(jié)構(gòu)的操作與實現(xiàn)比鏈?zhǔn)酱鎯Y(jié)構(gòu)有序存儲結(jié)構(gòu)的操作與實現(xiàn)比鏈?zhǔn)酱鎯Y(jié)構(gòu)有較大的優(yōu)勢。當(dāng)多棧共享空間時，可以使用較大的優(yōu)勢。當(dāng)多棧共享空間時，可以使用靜態(tài)鏈表結(jié)構(gòu)，能較好地解決問題。讀者可靜態(tài)鏈表結(jié)構(gòu)，能較好地解決問題。讀者可以自己分析。以自己分析。 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2 隊列隊列 在我們的生活中經(jīng)常有這樣的數(shù)據(jù)一端作為進端，在我們的生活中經(jīng)常有這樣的數(shù)據(jù)一端作為進端，另一端作為出端，如另一端作為出端，如:排

31、隊等車。這種數(shù)據(jù)也是一種排隊等車。這種數(shù)據(jù)也是一種線性結(jié)構(gòu)，但操作上不同于線性表，下面我們介紹線性結(jié)構(gòu)，但操作上不同于線性表，下面我們介紹這種數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)。3.2.1 3.2.1 隊列及其抽象數(shù)據(jù)類型隊列及其抽象數(shù)據(jù)類型 隊列隊列是一種操作受限的線性表，所有的插入都在是一種操作受限的線性表，所有的插入都在表的一端進行，所有的刪除都在表的另一端進行。表的一端進行，所有的刪除都在表的另一端進行。進行刪除的一端叫隊列的頭（進行刪除的一端叫隊列的頭（front）稱為）稱為隊頭隊頭，進，進行插入的一端叫隊列的尾（行插入的一端叫隊列的尾（rear）稱為）稱為隊尾隊尾。 ，如，如圖圖3.8數(shù)據(jù)結(jié)構(gòu)

32、C語言描述出出 版版 社社3.2.1 3.2.1 隊列及其抽象數(shù)據(jù)類型（續(xù)）隊列及其抽象數(shù)據(jù)類型（續(xù)） 隊列同現(xiàn)實生活中買東西排隊相仿。后來的總是加入到隊尾，每次離開的總是在隊列頭進行的。因此隊列也稱“先進先出線性表（First In First Out）。 隊頭隊頭 隊尾隊尾 a1 a2 an 出隊出隊 入隊入隊 圖圖3.8 3.8 隊列示意圖隊列示意圖 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.1 3.2.1 隊列及其抽象數(shù)據(jù)類型（續(xù)）隊列及其抽象數(shù)據(jù)類型（續(xù)） 隊列在程序設(shè)計中也經(jīng)常出現(xiàn)。一個最隊列在程序設(shè)計中也經(jīng)常出現(xiàn)。一個最典型的例子就是操作系統(tǒng)中的作業(yè)排隊。在典型的例子就是操作系統(tǒng)

33、中的作業(yè)排隊。在多道程序運行的計算機系統(tǒng)中，同時有幾個多道程序運行的計算機系統(tǒng)中，同時有幾個作業(yè)運行。如果運行結(jié)果都需要通過通道輸作業(yè)運行。如果運行結(jié)果都需要通過通道輸出，那就要按請求輸出的先后次序排隊。凡出，那就要按請求輸出的先后次序排隊。凡是請求輸出的作業(yè)都是從隊尾進入隊列的。是請求輸出的作業(yè)都是從隊尾進入隊列的。 隊列的操作與棧的操作類似，下面給出隊列的操作與棧的操作類似，下面給出隊列的抽象數(shù)據(jù)類型定義：隊列的抽象數(shù)據(jù)類型定義：數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社ADT Queue數(shù)據(jù)元素數(shù)據(jù)元素D：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù) 對

34、象。對象。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：隊列中數(shù)據(jù)元素之間是線性關(guān)系。：隊列中數(shù)據(jù)元素之間是線性關(guān)系。 基本操作基本操作： (1)(1) InitQueue(QInitQueue(Q) )：初始化操作。：初始化操作。 設(shè)置一個空隊列。設(shè)置一個空隊列。(2)(2) EmptyQueue(QEmptyQueue(Q) )：判空操作。若隊列為空則返：判空操作。若隊列為空則返TRUETRUE，否則，否則 FALSEFALSE。(3)(3) ClearQueue(QClearQueue(Q) )：隊列置空操作。將隊列：隊列置空操作。將隊列Q Q置為空隊列。置為空隊列。(4) DestroyQueue(Q(4) D

35、estroyQueue(Q) )：隊列銷毀操作。釋放隊列的空間。：隊列銷毀操作。釋放隊列的空間。(5)(5) GetHeadGetHead（Q, xQ, x）：取隊頭元素操作。用）：取隊頭元素操作。用x x取得隊元素的值。取得隊元素的值。 操作成功，返回值為操作成功，返回值為TRUETRUE，否則返回值為，否則返回值為FALSEFALSE。數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.1 3.2.1 隊列及其抽象數(shù)據(jù)類型（續(xù)）隊列及其抽象數(shù)據(jù)類型（續(xù)）(6)(6) QueueLengthQueueLength (Q): (Q): 隊列隊列Q Q已經(jīng)存在，隊列返回中元素個數(shù)。已經(jīng)存在，隊列返回中元素

36、個數(shù)。(7)(7) EnterQueue(QEnterQueue(Q，x)x)：進隊操作。在隊列：進隊操作。在隊列Q Q的隊尾插入的隊尾插入x x。 操作成功，返回值為操作成功，返回值為TRUETRUE， 否則返回值為否則返回值為FALSEFALSE。 (8)(8) DeleteQueue(QDeleteQueue(Q, x), x)：出隊操作，并用：出隊操作，并用x x返回值。成功，返返回值。成功，返TRUETRUE，否則，否則FALSEFALSE。 ADT Queue 隊列也可以有兩種存儲形式，即順序存儲表示和鏈?zhǔn)酱骊犃幸部梢杂袃煞N存儲形式，即順序存儲表示和鏈?zhǔn)酱鎯Ρ硎荆旅嫦葋砜搓犃械逆?/p>

37、式存儲結(jié)構(gòu)的形式及操作。儲表示，下面先來看隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)的形式及操作。 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.2 3.2.2 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) 我們知道，對于使用中數(shù)據(jù)元素變動較大的數(shù)據(jù)結(jié)構(gòu)，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)更有利。鏈隊列就是這樣一種數(shù)據(jù)結(jié)構(gòu)。 用鏈表表示的隊列需要兩個指針，分別指示隊頭和隊尾。如圖3.9所示。 隊頭 Q1 Q2 Q n 隊尾 圖圖3.9 鏈隊列示意圖鏈隊列示意圖數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.2 3.2.2 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)）隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)） 為了操作方便，和單鏈表一樣，我們也給鏈隊列添加一個哨兵結(jié)點，為了操作

38、方便，和單鏈表一樣，我們也給鏈隊列添加一個哨兵結(jié)點，并令隊頭指針指向哨兵結(jié)點。隊尾指針指向當(dāng)前最后一個元素。由此，并令隊頭指針指向哨兵結(jié)點。隊尾指針指向當(dāng)前最后一個元素。由此，空的隊列的判別條件為頭指針和尾指針均指向哨兵結(jié)點。下面給出鏈隊空的隊列的判別條件為頭指針和尾指針均指向哨兵結(jié)點。下面給出鏈隊列數(shù)據(jù)類型：列數(shù)據(jù)類型：typedef structtypedef struct Node Node elemtypeelemtype data; / data; /* *數(shù)據(jù)域數(shù)據(jù)域* */ / structstruct Node next; / Node next; /* *指針域指針域* */

39、 / LinkQueueNodeLinkQueueNode; ; typedef structtypedef struct LinkQueueNodeLinkQueueNode * *front;front; LinkQueueNodeLinkQueueNode * *rear;rear; * *LinkQueueLinkQueue; ; 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.2 3.2.2 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)）隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)） 鏈隊列的操作與單鏈表操作極為相似，只是插入、刪除鏈隊列的操作與單鏈表操作極為相似，只是插入、刪除分別修改頭指針、尾指針。一般來說，只要可用空間不被占分

40、別修改頭指針、尾指針。一般來說，只要可用空間不被占滿，鏈隊列不會發(fā)生上溢情況。圖滿，鏈隊列不會發(fā)生上溢情況。圖3.10所示描述了一個帶哨所示描述了一個帶哨兵結(jié)點隊列的創(chuàng)建、插入、刪除操作過程。兵結(jié)點隊列的創(chuàng)建、插入、刪除操作過程。(a)初始化帶哨兵空隊初始化帶哨兵空隊 (b)申請新結(jié)點申請新結(jié)點 (c)在空隊列中插入元素在空隊列中插入元素e 3.10 建隊操作過程建隊操作過程front rearQesfront front rearrearesQ數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.2 3.2.2 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)）隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)）隊列基本操作算法如下：隊列基本操作算法如下：

41、(1).(1).初始化操作。初始化操作。 int InitQueue(LinkQueueint InitQueue(LinkQueue * *Q)Q)/ /* * 將將Q Q初始化為一個帶哨兵的空鏈隊初始化為一個帶哨兵的空鏈隊 * */ / * *Q-front=(LinkQueueNode Q-front=(LinkQueueNode * *)malloc(sizeof(LinkQueueNode)malloc(sizeof(LinkQueueNode);); / /* *開辟哨兵開辟哨兵* */ / if( if(* *Q-front!=NULL)Q-front!=NULL) * *Q-r

42、ear=Q-rear=* *Q-front;Q-front; / /* *隊頭、隊尾都指向哨兵結(jié)點！隊頭、隊尾都指向哨兵結(jié)點！* */ / * *Q-front-next=NULL;Q-front-next=NULL; return OK;return OK; else return FALSE ; /else return FALSE ; /* *哨兵結(jié)點開辟失?。∩诒Y(jié)點開辟失?。? */ / 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.2 3.2.2 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)）隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)）(2). 入隊操作入隊操作 int EnterQueue(LinkQueue int Ent

43、erQueue(LinkQueue * *Q, elemtypeQ, elemtype e) e) / /* * 將數(shù)據(jù)元素將數(shù)據(jù)元素e e插入到帶哨兵隊列插入到帶哨兵隊列Q Q中中 * */ / NewNode=(LinkQueueNode NewNode=(LinkQueueNode * * )malloc(sizeof(LinkQueueNode )malloc(sizeof(LinkQueueNode);); / /* *開辟新結(jié)點開辟新結(jié)點* */ / if(NewNode if(NewNode!= NULL)!= NULL) NewNodeNewNode-data=e;-data=

44、e; / /* *將新結(jié)點中賦將新結(jié)點中賦e e值值* */ / NewNodeNewNode-next=NULL;-next=NULL; * *Q-rear-next=NewNodeQ-rear-next=NewNode; ; / /* * 插入隊尾插入隊尾 * */ / * *Q-rear=NewNodeQ-rear=NewNode; ; return TRUE ;return TRUE ; else return FALSE ; /else return FALSE ; /* * 沒開辟出新結(jié)點沒開辟出新結(jié)點* */ / 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.2 3.2.2 隊列的鏈

45、式存儲結(jié)構(gòu)（續(xù)）隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（續(xù)） (3).(3). 出隊操作出隊操作 int DeleteQueue(LinkQueue int DeleteQueue(LinkQueue * * Q, Elemtype Q, Elemtype * *e)e) / /* * 將隊列將隊列Q Q的隊頭元素出隊，的隊頭元素出隊， 并存放到并存放到e e所指的存儲空間中所指的存儲空間中 * */ / LinkQueueNode LinkQueueNode * *p;p; if(if(* *Q-front=Q-front=* *Q-rear) Q-rear) return FALSE; / return FA

46、LSE; /* *空隊列取隊尾失敗空隊列取隊尾失敗* */ / p= p= * *Q-front-next;Q-front-next; / /* * 從隊頭取出結(jié)點從隊頭取出結(jié)點p p * */ / * *Q-front-next=p-next; /Q-front-next=p-next; /* * 隊頭元素隊頭元素p p出隊出隊 * */ / if(if(* *Q-rear=p) /Q-rear=p) /* *如果隊中只有一個元素如果隊中只有一個元素p p，則，則p p出隊后成為空隊出隊后成為空隊* */ / * *Q-rear=Q-rear=* *Q-front;Q-front; * *e

47、=p-data;e=p-data; / /* * 結(jié)果作為變參返回結(jié)果作為變參返回* */ / free(p); return TRUE; free(p); return TRUE; 其他算法，如隊列的長度、取隊頭元素等，如何實現(xiàn)？。其他算法，如隊列的長度、取隊頭元素等，如何實現(xiàn)？。數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.3 3.2.3 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)-循環(huán)隊列循環(huán)隊列 雖然鏈隊列很方便，但由于每個結(jié)點都有指針域，因此比雖然鏈隊列很方便，但由于每個結(jié)點都有指針域，因此比順序存儲多占用內(nèi)存空間。所以在有些情況下仍需要用順序順序存儲多占用內(nèi)存空間。所以在有些情況下仍需要用順

48、序存儲結(jié)構(gòu)來表示隊列。存儲結(jié)構(gòu)來表示隊列。 在隊列的順序存儲結(jié)構(gòu)中，可以用一組地址連續(xù)的存儲單在隊列的順序存儲結(jié)構(gòu)中，可以用一組地址連續(xù)的存儲單元依次存放從隊頭到隊尾的元素，還要設(shè)置兩個指針分別指元依次存放從隊頭到隊尾的元素，還要設(shè)置兩個指針分別指向隊頭元素和隊尾元素的位置，并約定隊頭指針指示隊列中向隊頭元素和隊尾元素的位置，并約定隊頭指針指示隊列中第一個元素的位置，尾指針指示隊尾元素位置的后一個位置。第一個元素的位置，尾指針指示隊尾元素位置的后一個位置。如圖如圖3.11所示。由于隊列中隊頭和隊尾的位置都是動態(tài)變化所示。由于隊列中隊頭和隊尾的位置都是動態(tài)變化的，如果不加以約束，隊頭和隊尾在數(shù)組

49、中的位置是不斷移的，如果不加以約束，隊頭和隊尾在數(shù)組中的位置是不斷移動的如圖動的如圖3.11(b)、3.11(c)。圖。圖3.11(d)當(dāng)隊尾移動到最后位置當(dāng)隊尾移動到最后位置時，不能再入隊。但隊頭為時，不能再入隊。但隊頭為3前面還有單元是空的。如果將前面還有單元是空的。如果將順序的數(shù)組看成一個環(huán)狀的空間，即最后一個單元的后繼為順序的數(shù)組看成一個環(huán)狀的空間，即最后一個單元的后繼為第一個單元。因此順序存儲的隊列中，將所開辟空間地址的第一個單元。因此順序存儲的隊列中，將所開辟空間地址的首、尾位置是連接起來形成一個環(huán)狀結(jié)構(gòu)稱為循環(huán)隊列，如首、尾位置是連接起來形成一個環(huán)狀結(jié)構(gòu)稱為循環(huán)隊列，如圖圖3.1

50、23.12所示。所示。 數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.2.3 3.2.3 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)-循環(huán)隊列（續(xù)）循環(huán)隊列（續(xù)）(a) 空隊列空隊列 (b) a b c d 依次依次入隊入隊 (c) a b c 出隊出隊 (d) e f 進隊進隊圖圖3.11 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)q.rearq.front543210q.rearq.front543 d2 c1 b0 aq.rearq.front543 d2 1 0 q.rearq.front5 f 4 e3 d2 1 0 (a) 空隊列空隊列(b) 隊列滿隊列滿(c) 一般情況一般情況圖圖3.12 循環(huán)隊列

51、循環(huán)隊列012354rearfront012354e6e7e8e3e4e5012354frontreare3e4e5frontrear數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社 假設(shè)開辟了假設(shè)開辟了MAXSIZEMAXSIZE個空間個空間, ,初始化隊列時，令初始化隊列時，令frontfrontrearrear0 0；入隊時，直接將新元素送入尾指針；入隊時，直接將新元素送入尾指針rearrear所指的單元，所指的單元，然后尾指針增然后尾指針增1,1,出隊時，直接取出隊頭指針出隊時，直接取出隊頭指針frontfront所指的元素，所指的元素，然后頭指針增然后頭指針增1 1。顯然，在非空順序隊列中，隊頭指

52、針始終指。顯然，在非空順序隊列中，隊頭指針始終指向當(dāng)前的隊頭元素，而隊尾指針始終指向真正隊尾元素后面的向當(dāng)前的隊頭元素，而隊尾指針始終指向真正隊尾元素后面的單元。隨著入隊和出隊的進行當(dāng)單元。隨著入隊和出隊的進行當(dāng)frontfrontrearrear時，循環(huán)隊列有時，循環(huán)隊列有兩種情況，一種為隊滿；一種為隊空?？梢姡瑑煞N情況，一種為隊滿；一種為隊空?？梢?，frontfrontrearrear無無法判別隊列的狀態(tài)是法判別隊列的狀態(tài)是“空空”還是還是“滿滿”。 對于這個問題，有兩種處理方法：對于這個問題，有兩種處理方法： 3.2.3 3.2.3 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)-循環(huán)隊列（續(xù)）循

53、環(huán)隊列（續(xù)）數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社 一種方法是少用一個元素存儲空間。當(dāng)隊尾指針?biāo)赶虻目諉卧暮罄^單元是隊頭元素所在的單元時，則停止入隊。這樣一來，隊尾指針永遠追不上隊頭指針，所以隊滿時不會有frontrear。這時隊列“滿”的條件為(rear十1)mod MAXSIZEfront。判隊空的條件不變，仍為rearfront。 另一種方法是增設(shè)一個標(biāo)志量的方法，以區(qū)別隊列是“空”還是“滿”。3.2.3 3.2.3 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)-循環(huán)隊列（續(xù)）循環(huán)隊列（續(xù)）數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社循環(huán)隊列的類型定義如下：循環(huán)隊列的類型定義如下： define MAXS

54、IZE 50 / *隊列的最大長度隊列的最大長度* / typedef structtypedef struct elemtype elem elemtype elem MAXSIZE;/ MAXSIZE;/* *隊列的元素空間隊列的元素空間* */ / int int front,rear; / front,rear; /* *頭、尾指針頭、尾指針* */ / SeqQueueSeqQueue; ; 基本操作實現(xiàn)：基本操作實現(xiàn)： 前面我們介紹了入隊時，隊滿隊空狀態(tài)的兩種前面我們介紹了入隊時，隊滿隊空狀態(tài)的兩種處理方法，下面采用多用一個空閑空間的方法。處理方法，下面采用多用一個空閑空間的方法。

55、 3.2.3 3.2.3 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)-循環(huán)隊列（續(xù)）循環(huán)隊列（續(xù)）數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社(1)(1) 入隊操作入隊操作int EnterQueue(SeqQueue int EnterQueue(SeqQueue * *Q, elemtypeQ, elemtype e) e) / /* *將元素將元素e e加入隊列加入隊列Q Q* */ / if(Q-rear+1)%MAXSIZE=Q-front) if(Q-rear+1)%MAXSIZE=Q-front) return FALSE; / return FALSE; /* * 隊列滿，返回假值結(jié)束隊列滿，

56、返回假值結(jié)束* */ / Q-elemQ-elem Q-rearQ-rear=e; /=e; /* * 將將e e加入隊尾加入隊尾* */ / Q-rear=(Q-rear+1)%MAXSIZE; / Q-rear=(Q-rear+1)%MAXSIZE; /* * 重新設(shè)置隊尾指針重新設(shè)置隊尾指針 * */ / return TRUE ; / return TRUE ; /* * 操作成功操作成功* */ / 3.2.3 3.2.3 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)-循環(huán)隊列（續(xù)）循環(huán)隊列（續(xù)）數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社（2）出隊操作）出隊操作 int DeleteQueue(Se

57、qQueue int DeleteQueue(SeqQueue * *Q, elemtypeQ, elemtype * *e)e) / /* *隊列隊列Q Q的隊頭元素出隊，的隊頭元素出隊， 用用e e返回其值返回其值* */ / ifif（Q-front=Q-rearQ-front=Q-rear） return FALSE; /return FALSE; /* *隊列為空，返回假值結(jié)束隊列為空，返回假值結(jié)束* */ / * *e=Q-eleme=Q-elem Q-frontQ-front; ; Q-front=(Q-front+1)%MAXSIZE;/Q-front=(Q-front+1)%

58、MAXSIZE;/* *重新設(shè)置隊頭指針重新設(shè)置隊頭指針* */ /return TRUE; /return TRUE; /* *操作成功操作成功* */ / 3.2.3 3.2.3 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)-循環(huán)隊列（續(xù)）循環(huán)隊列（續(xù)）數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社除了上述隊列外，還有一種限定性數(shù)據(jù)結(jié)構(gòu)，是雙端隊列除了上述隊列外，還有一種限定性數(shù)據(jù)結(jié)構(gòu)，是雙端隊列（Deque）如圖）如圖3.13所示所示 。雙端隊列是限定插入、刪除在表的兩端進行的線性表。這兩端雙端隊列是限定插入、刪除在表的兩端進行的線性表。這兩端分別稱作端點，分別稱作端點， 記作記作end1和和end2?？梢?/p>

59、用一個鐵軌轉(zhuǎn)軌網(wǎng)?？梢杂靡粋€鐵軌轉(zhuǎn)軌網(wǎng)絡(luò)來比喻雙端隊列，如圖絡(luò)來比喻雙端隊列，如圖3.13 (a)所示。所示。端點端點1 端點端點2a1 a2 an入隊入隊 出隊出隊 出隊入隊出隊入隊 (b)(b)圖圖3.13 3.13 雙端隊列雙端隊列(a)(a) 盡管雙端隊列盡管雙端隊列看起來似乎比棧和看起來似乎比棧和隊列更靈活，但實隊列更靈活，但實際上在程序系統(tǒng)中，際上在程序系統(tǒng)中，不如棧和隊列應(yīng)用不如棧和隊列應(yīng)用廣泛，故在此不作廣泛，故在此不作詳細(xì)討論。詳細(xì)討論。 3.2.3 3.2.3 隊列的順序存儲結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)-循環(huán)隊列（續(xù)）循環(huán)隊列（續(xù)）數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社3.3 棧和隊

60、列的應(yīng)用棧和隊列的應(yīng)用1 1、數(shù)制轉(zhuǎn)換、數(shù)制轉(zhuǎn)換 假設(shè)要將十進制數(shù)假設(shè)要將十進制數(shù)N N轉(zhuǎn)換為轉(zhuǎn)換為d d進制數(shù)，一個簡單的進制數(shù)，一個簡單的轉(zhuǎn)換算法是重復(fù)下述兩步，直到轉(zhuǎn)換算法是重復(fù)下述兩步，直到N N等于零。等于零。步驟一：步驟一：X = N mod d (X = N mod d (其中其中modmod為求余運算為求余運算) )步驟二：步驟二：N = N div d (N = N div d (其中其中divdiv為整除運算為整除運算) )算法如下：算法如下：數(shù)據(jù)結(jié)構(gòu)C語言描述出出 版版 社社void Conversion(int N,intvoid Conversion(int N,int d) d)/ /* *將將N N進制數(shù)，進制數(shù)， 轉(zhuǎn)換為轉(zhuǎn)換為d d進制數(shù)進制數(shù)* */ / Stack S Stack S； intint x x； /