隊(duì)列ADT,實(shí)現(xiàn)與使用接口

周立功教授數(shù)年之心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》以及《面向AMetal框架與接口的編程（上）》，電子版已無(wú)償性分享到電子工程師與高校群體，在公眾號(hào)回復(fù)【編程】即可在線(xiàn)閱讀。書(shū)本內(nèi)容公開(kāi)后，在電子行業(yè)掀起一片學(xué)習(xí)熱潮。經(jīng)周立功教授授權(quán)，本公眾號(hào)特對(duì)《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》一書(shū)內(nèi)容進(jìn)行連載，愿共勉之。

第三章為算法與數(shù)據(jù)結(jié)構(gòu)，本文為3.6 隊(duì)列ADT。

>>>3.6.1建立抽象

隊(duì)列可以簡(jiǎn)單的描述為：隊(duì)列是一種特殊的容器，其限制插入位置在容器的尾部（隊(duì)尾），刪除位置在容器的頭部（隊(duì)頭），是一種“先進(jìn)先出”（First In-First Out，F(xiàn)IFO）的線(xiàn)性結(jié)構(gòu)。比如，排隊(duì)買(mǎi)票，人們從隊(duì)尾加入隊(duì)列，買(mǎi)完票后從隊(duì)頭離開(kāi)（假定沒(méi)有人插隊(duì)），示意圖詳見(jiàn)圖 3.28。

圖 3.28 隊(duì)列示意圖

其抽象定義如下：

• 類(lèi)型名：隊(duì)列（Queue）

• 類(lèi)型屬性：存儲(chǔ)一系列項(xiàng)

• 類(lèi)型操作：從隊(duì)尾添加項(xiàng)，從隊(duì)頭刪除項(xiàng)，確定隊(duì)列是否為空，確定隊(duì)列是否已滿(mǎn)，確定隊(duì)列中的項(xiàng)數(shù)。

>>>3.6.2 建立接口

接口是通過(guò)頭文件向用戶(hù)提供的。首先創(chuàng)建一個(gè)頭文件，命名為queue.h。在接口文件中，需要包含兩部分內(nèi)容：其一，抽象類(lèi)型queueADT的定義；其二，聲明各隊(duì)列ADT的操作函數(shù)。

1、定義抽象類(lèi)型queueADT

與棧類(lèi)似，使用結(jié)構(gòu)體類(lèi)型來(lái)表示一個(gè)隊(duì)列，在頭文件中，只需要定義一個(gè)該結(jié)構(gòu)體指針類(lèi)型即可。結(jié)構(gòu)體實(shí)際定義的細(xì)節(jié)、包含的具體成員無(wú)需在頭文件中定義，交由具體實(shí)現(xiàn)完成對(duì)其的定義。定義抽象類(lèi)型queueADT如下：

2、接口函數(shù)聲明

• 創(chuàng)建隊(duì)列

在使用隊(duì)列前，必須正確的創(chuàng)建一個(gè)隊(duì)列，因此需要提供一個(gè)用于創(chuàng)建新的queueADT的函數(shù)。其函數(shù)原型如下：

后置條件：返回隊(duì)列。

其調(diào)用形式如下：

• 銷(xiāo)毀隊(duì)列

在創(chuàng)建隊(duì)列時(shí)，具體實(shí)現(xiàn)會(huì)根據(jù)實(shí)際情況分配隊(duì)列相關(guān)的存儲(chǔ)空間，如隊(duì)列對(duì)象本身的存儲(chǔ)空間，隊(duì)列項(xiàng)的存儲(chǔ)空間等。因此，當(dāng)一個(gè)隊(duì)列不在使用時(shí)，應(yīng)該釋放掉隊(duì)列相關(guān)的內(nèi)存空間，以銷(xiāo)毀一個(gè)隊(duì)列，銷(xiāo)毀后的隊(duì)列不再存在，無(wú)法繼續(xù)使用。其函數(shù)原型如下：

前置條件：queue為之前創(chuàng)建的隊(duì)列；

后置條件：釋放隊(duì)列相關(guān)的所有內(nèi)存，隊(duì)列被銷(xiāo)毀，不再有效。

其調(diào)用形式如下：

• 從隊(duì)尾添加項(xiàng)（入隊(duì)列）

用戶(hù)通過(guò)該函數(shù)可以從隊(duì)列尾部向隊(duì)列中添加新元素，其函數(shù)原型如下：

前置條件：queue為之前創(chuàng)建的隊(duì)列，value是待加入隊(duì)尾的數(shù)據(jù)；

后置條件：如果隊(duì)列不滿(mǎn)，將value添加至隊(duì)尾，該函數(shù)返回true；否則，隊(duì)列已滿(mǎn)，隊(duì)列保持不變，該函數(shù)返回false。

其調(diào)用形式如下：

• 從隊(duì)頭移除項(xiàng)（出隊(duì)列）

用戶(hù)通過(guò)該函數(shù)可以從隊(duì)列頭部移除一個(gè)元素，其函數(shù)原型如下：

前置條件：queue為之前創(chuàng)建的隊(duì)列，p_value為指向存儲(chǔ)“移出隊(duì)列的值”的變量的指針；

后置條件：如果隊(duì)列不空，將隊(duì)頭的值拷貝到*p_value，同時(shí)刪除當(dāng)前隊(duì)頭，該函數(shù)返回true；否則，隊(duì)列為空，該函數(shù)返回false。

其調(diào)用形式如下：

• 判斷隊(duì)列是否為空

判斷隊(duì)列是否為空的函數(shù)原型如下：

前置條件：queue為之前創(chuàng)建的隊(duì)列；

后置條件：如果隊(duì)列為空，則返回true，否則返回false。

其調(diào)用形式如下：

• 判斷隊(duì)列是否已滿(mǎn)

判斷隊(duì)列是否已滿(mǎn)的函數(shù)原型如下：

前置條件：queue為之前創(chuàng)建的隊(duì)列；

后置條件：如果隊(duì)列為空，則返回true，否則返回false。

其調(diào)用形式如下：

• 確定隊(duì)列中元素的個(gè)數(shù)

確定棧中元素的個(gè)數(shù)的函數(shù)原型如下：

前置條件：queue為之前創(chuàng)建的隊(duì)列；

后置條件：返回隊(duì)列中元素的個(gè)數(shù)。

其調(diào)用形式如下：

程序清單 3.70 抽象隊(duì)列接口（queue.h）

>>>3.6.3 實(shí)現(xiàn)與使用接口

在實(shí)現(xiàn)隊(duì)列之前，首先需要確定使用何種數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。一般來(lái)說(shuō)，可以使用地址連續(xù)的內(nèi)存空間存儲(chǔ)數(shù)據(jù)，比如，使用數(shù)組或動(dòng)態(tài)分配一段內(nèi)存空間；也可以使用地址非連續(xù)的鏈表結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)。

1、順序隊(duì)列

在實(shí)現(xiàn)隊(duì)列之前，我們先來(lái)分析一下順序隊(duì)列的原理。順序隊(duì)列采用連續(xù)的內(nèi)存空間，假定使用front和rear兩個(gè)變量來(lái)分別表示隊(duì)頭和隊(duì)尾的位置，初始時(shí)，隊(duì)列為空，隊(duì)頭和隊(duì)尾都在為0，詳見(jiàn)圖3.29 (a)。

當(dāng)從隊(duì)尾增加數(shù)據(jù)時(shí)，rear增大向后移動(dòng)，如data0入隊(duì)列后，示意圖詳見(jiàn)圖3.29 (b)，此時(shí)，隊(duì)頭front保持不變，隊(duì)尾rear增加1，繼續(xù)入隊(duì)列，data1、data2、data3入隊(duì)列后的示意圖詳見(jiàn)圖3.29 (c)。

圖3.29 隊(duì)列示意圖——入隊(duì)列

當(dāng)從隊(duì)頭移除數(shù)據(jù)時(shí)，例如，移除data0后，隊(duì)頭front指向的數(shù)據(jù)必須更新為data1，這就有兩種方式：一是front保持不動(dòng)，將所有數(shù)據(jù)向前移動(dòng)一格，如圖3.30(a)；二是數(shù)據(jù)保持不動(dòng)，front增加1，使其指向data1。顯然，將所有數(shù)據(jù)向前移動(dòng)一格存在大量的數(shù)據(jù)拷貝，隊(duì)列中數(shù)據(jù)越多，數(shù)據(jù)拷貝操作就越多，效率也就越低，而將front的值加1是非常簡(jiǎn)單快捷的，因此，一般來(lái)講，都是選擇第二種處理方式。

圖3.30 隊(duì)列示意圖——出隊(duì)列

按照方式2，繼續(xù)將data1、data2、data3出隊(duì)列，示意圖詳見(jiàn)圖3.31(a)，此時(shí)，隊(duì)列中不存在任何有效數(shù)據(jù)，rear與front相等，隊(duì)列為空。

若繼續(xù)進(jìn)行數(shù)據(jù)入隊(duì)列操作，data4、data5、data6、data7依次進(jìn)入隊(duì)列后的示意圖詳見(jiàn)圖3.31(b)，由于隊(duì)列元素已經(jīng)存儲(chǔ)至最高地址的存儲(chǔ)空間，rear已經(jīng)指向了無(wú)效的地址，這種狀態(tài)時(shí)，不能再簡(jiǎn)單的按照之前的方式，繼續(xù)向隊(duì)尾添加數(shù)據(jù)，否則會(huì)因?yàn)閿?shù)組越界而導(dǎo)致程序異常。

圖3.31 繼續(xù)進(jìn)行出隊(duì)列、入隊(duì)列操作

那么，在圖3.31(b)所示的情況下，就不能再添加新元素了嗎？顯然，此時(shí)還有一半的空間沒(méi)有填充數(shù)據(jù)，一個(gè)將空閑空間利用起來(lái)的巧妙方法是：當(dāng)rear或front的值超過(guò)最大值后，自動(dòng)回滾到0。在圖3.31(b)，rear已經(jīng)超過(guò)了最大地址，因此，將其回滾到0，詳見(jiàn)圖3.32(a)。即在邏輯上，將順序隊(duì)列視為一個(gè)環(huán)狀的空間，詳見(jiàn)圖3.32(b)。入隊(duì)列后，不再是簡(jiǎn)單的將rear值加1，而是當(dāng)加1后，判斷是否超過(guò)了最大地址空間，若超過(guò)了，則重新將rear的值設(shè)置為0。

圖3.32 循環(huán)隊(duì)列

將存儲(chǔ)空間視為一個(gè)環(huán)狀后，將更加方便的理解入隊(duì)列和出隊(duì)列操作。入隊(duì)列時(shí)，僅需將數(shù)據(jù)存儲(chǔ)值rear指向的空間中，存儲(chǔ)完畢后，將rear的值更新為指向下一個(gè)存儲(chǔ)單元。出隊(duì)列時(shí)，將front指向的空間中的數(shù)據(jù)取出，并將front的值更新為指向下一個(gè)存儲(chǔ)單元。

特別地，當(dāng)front與rear相等時(shí)，表示隊(duì)列為空，無(wú)法進(jìn)行出隊(duì)列操作，與之對(duì)應(yīng)的，什么時(shí)候隊(duì)列視已滿(mǎn)呢？在圖3.32(b)的基礎(chǔ)上，繼續(xù)將data8、data9、data10、data11加入隊(duì)列，使所有空閑單元都存儲(chǔ)數(shù)據(jù)，可以看到加入各個(gè)數(shù)據(jù)后的示意圖詳見(jiàn)圖3.33。

圖3.33 data8~data11依次入隊(duì)列

當(dāng)data11加入隊(duì)列后，所有存儲(chǔ)單元都存儲(chǔ)了數(shù)據(jù)，此時(shí)隊(duì)列已滿(mǎn)，可以看到，當(dāng)前的front與rear相等，而隊(duì)列為空時(shí)，front與rear也相等。由此可見(jiàn)，只憑front與rear是否相等，無(wú)法判斷隊(duì)列是“滿(mǎn)”還是“空”。如何解決呢？最簡(jiǎn)單的方法是增加一個(gè)標(biāo)志，當(dāng)數(shù)據(jù)入隊(duì)列后，出現(xiàn)front與rear相等時(shí)，設(shè)置該標(biāo)志位1，以標(biāo)志當(dāng)前是“滿(mǎn)”狀態(tài)。而還有一種巧妙的方法，就是實(shí)際少用一個(gè)存儲(chǔ)單元，當(dāng)front在rear的下一位置時(shí)，即圖3.33(c)所示狀態(tài)，就視為隊(duì)列已滿(mǎn)，不再允許新元素加入隊(duì)列，這種方法的優(yōu)點(diǎn)是無(wú)需增加額外標(biāo)志，只是將判定隊(duì)列是否已滿(mǎn)的方式修改一下，但其缺點(diǎn)也是很明顯的，會(huì)浪費(fèi)一個(gè)數(shù)據(jù)的存儲(chǔ)空間。實(shí)際上，額外增加標(biāo)志時(shí)，增加的標(biāo)志也同樣需要占用內(nèi)存空間。

至此，分析了入隊(duì)列、出隊(duì)列、判定隊(duì)列是否為空、判定隊(duì)列是否為滿(mǎn)的實(shí)現(xiàn)方法，還剩下最后一個(gè)操作沒(méi)有提及，即確定隊(duì)列中元素的個(gè)數(shù)。

而本質(zhì)上求取元素個(gè)數(shù)非常簡(jiǎn)單，只需要將隊(duì)尾值rear減去隊(duì)頭值front即可，得到的差值即表示隊(duì)頭與隊(duì)尾之間的數(shù)據(jù)個(gè)數(shù)。但需要考慮特殊情況，因?yàn)樵谘h(huán)隊(duì)列中，隊(duì)尾的值可能小于隊(duì)頭的值，如圖3.34(a)、(b)、(c)所示。此時(shí)，它們的差值即為負(fù)值，如在圖3.35(a)中：rear = 1，front = 4，它們的差值為 -3，而實(shí)際元素的個(gè)數(shù)為5?？梢?jiàn)，當(dāng)值為負(fù)數(shù)時(shí)，只需要將其加上存儲(chǔ)空間的大?。ㄊ纠袨?）即可。

上面分析了循環(huán)隊(duì)列的原理，接下來(lái)使用程序來(lái)實(shí)現(xiàn)隊(duì)列的各個(gè)接口，將實(shí)現(xiàn)代碼全部存放在queue.c文件中。在建立接口時(shí)，首先在頭文件中定義了抽象隊(duì)列的類(lèi)型為：

這里的結(jié)構(gòu)體類(lèi)型struct queueCDT只有聲明，還沒(méi)有具體的定義。因此無(wú)論何種實(shí)現(xiàn)方式，都需要先實(shí)現(xiàn)struct queueCDT類(lèi)型的定義。

假定使用的連續(xù)空間通過(guò)malloc動(dòng)態(tài)分配得到，則在結(jié)構(gòu)體中需要包含一個(gè)指向連續(xù)空間首地址的指針，以便使用這片內(nèi)存空間。此外，在上面原理的分析中，需要使用front和rear分別表示隊(duì)頭和隊(duì)尾的位置，因此隊(duì)列結(jié)構(gòu)體中需要包含這兩個(gè)成員，定義隊(duì)列結(jié)構(gòu)體類(lèi)型為：

理解了隊(duì)列各種操作的原理后，則實(shí)現(xiàn)起來(lái)就較為容易了，詳見(jiàn)程序清單 2.34。

程序清單3.71 順序隊(duì)列的實(shí)現(xiàn)（queue.c）

在getQueueLength()函數(shù)的實(shí)現(xiàn)中，巧妙地避免了使用if語(yǔ)句判斷rear和front的差值是否為負(fù)值，差值無(wú)論正負(fù)，都加上了MAXQSIZE（隊(duì)列的容量大?。４藭r(shí)，若差值為負(fù)值，則可以得到正確的結(jié)果，但若差值為正值，則結(jié)果會(huì)恰好多出MAXQSIZE，因此最后需要將結(jié)果對(duì)MAXQSIZE取余，以丟棄可能多出的MAXQSIZE，確保了結(jié)果的正確性。

2、鏈隊(duì)列

在鏈隊(duì)列中，各個(gè)數(shù)據(jù)的存儲(chǔ)空間可以不連續(xù)，基于鏈表的隊(duì)列（假定數(shù)據(jù)域?yàn)閕nt類(lèi)型）示意圖詳見(jiàn)圖3.36。

圖3.36 鏈隊(duì)列示意圖

需要注意的是，鏈表頭結(jié)點(diǎn)代表的是鏈表頭，為了方便添加結(jié)點(diǎn)操作而定義的，不攜帶有效的應(yīng)用數(shù)據(jù)。其后的結(jié)點(diǎn)才是有效結(jié)點(diǎn)，因此隊(duì)頭是第一個(gè)有效的數(shù)據(jù)結(jié)點(diǎn)，隊(duì)尾是最后一個(gè)有效的數(shù)據(jù)結(jié)點(diǎn)。

入隊(duì)列即將新元素添加至鏈表尾部，出隊(duì)列就是移除第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。這些操作在鏈表程序中都已經(jīng)有相應(yīng)的接口。因此基于之前的鏈表程序，實(shí)現(xiàn)鏈隊(duì)列非常容易。在隊(duì)列結(jié)構(gòu)體中，僅需包含鏈表頭結(jié)點(diǎn)，無(wú)需front、rear等成員。定義隊(duì)列結(jié)構(gòu)體類(lèi)型為：

若隊(duì)列中各個(gè)結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型為int類(lèi)型，則對(duì)應(yīng)的鏈表結(jié)點(diǎn)類(lèi)型為：

如程序清單3.72所示為一種鏈隊(duì)列的實(shí)現(xiàn)范例。

程序清單3.72 鏈隊(duì)列的實(shí)現(xiàn)（queue_list.c）

對(duì)于大多數(shù)操作而言，鏈表都已經(jīng)提供了相應(yīng)的接口，因此入隊(duì)列、出隊(duì)列、判斷滿(mǎn)或空都非常容易。稍微復(fù)雜點(diǎn)的是得到隊(duì)列中的元素個(gè)數(shù)，其需要遍歷整個(gè)鏈表，每遍歷到一個(gè)結(jié)點(diǎn)時(shí)，都將計(jì)數(shù)器count的值加1（count的地址通過(guò)遍歷函數(shù)的p_arg參數(shù)傳遞），遍歷結(jié)束后，計(jì)數(shù)器的值即為隊(duì)列中的元素個(gè)數(shù)。

在入隊(duì)列函數(shù)的實(shí)現(xiàn)中，每次都需要將新的結(jié)點(diǎn)添加至鏈表尾部，而對(duì)于單向鏈表，直接將結(jié)點(diǎn)添加至鏈表尾部的效率是非常低的，每次都需要從頭開(kāi)始遍歷，直到找到最后一個(gè)結(jié)點(diǎn)，才能執(zhí)行實(shí)際的添加操作。如何解決這個(gè)問(wèn)題呢？最簡(jiǎn)單的辦法是使用雙向鏈表，但雙向鏈表需要占用更多內(nèi)存，同時(shí)，在隊(duì)列的實(shí)現(xiàn)中，并不需要雙向鏈表那么靈活，不需要隨意的尋找上一個(gè)結(jié)點(diǎn)，顯然，這里使用雙向鏈表有點(diǎn)“小題大做”了。把握到一個(gè)核心的問(wèn)題，就是需要將新結(jié)點(diǎn)添加至鏈表尾部，如果使用一個(gè)指針p_rear來(lái)指向尾結(jié)點(diǎn)，那么，添加結(jié)點(diǎn)至鏈表尾部時(shí)，可以直接將結(jié)點(diǎn)添加至p_rear指向的結(jié)點(diǎn)后面，無(wú)需再?gòu)念^開(kāi)始遍歷鏈表，即“slist_add (p_head, p_rear, p_node);”。

添加結(jié)束后，新的p_node結(jié)點(diǎn)為新的尾結(jié)點(diǎn)，因此需要更新p_rear的值，使其指向新的尾結(jié)點(diǎn)，即“p_rear = p_node;”。p_rear可以作為隊(duì)列結(jié)構(gòu)體的一個(gè)成員，以便使用。讀者可以按照這種方式，自行嘗試修改入隊(duì)列函數(shù)，提升入隊(duì)列的效率。

對(duì)于使用者來(lái)講，無(wú)需關(guān)心隊(duì)列的具體實(shí)現(xiàn)方式。只要正確把握接口的使用方法（前置條件和后置條件），就可以編寫(xiě)使用隊(duì)列的應(yīng)用程序。將整數(shù)入隊(duì)列，再出隊(duì)列的范例程序詳見(jiàn)程序清單 2.35。

程序清單3.73 使用隊(duì)列接口的范例程序