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

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

>>>3.6.1建立抽象

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

圖 3.28 隊列示意圖

其抽象定義如下：

• 類型名：隊列（Queue）

• 類型屬性：存儲一系列項

• 類型操作：從隊尾添加項，從隊頭刪除項，確定隊列是否為空，確定隊列是否已滿，確定隊列中的項數(shù)。

>>>3.6.2 建立接口

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

1、定義抽象類型queueADT

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

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

• 創(chuàng)建隊列

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

后置條件：返回隊列。

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

• 銷毀隊列

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

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

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

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

• 從隊尾添加項（入隊列）

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

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

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

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

• 從隊頭移除項（出隊列）

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

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

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

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

• 判斷隊列是否為空

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

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

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

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

• 判斷隊列是否已滿

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

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

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

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

• 確定隊列中元素的個數(shù)

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

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

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

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

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

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

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

1、順序隊列

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

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

圖3.29 隊列示意圖——入隊列

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

圖3.30 隊列示意圖——出隊列

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

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

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

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

圖3.32 循環(huán)隊列

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

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

圖3.33 data8~data11依次入隊列

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

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

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

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

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

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

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

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

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

2、鏈隊列

在鏈隊列中，各個數(shù)據(jù)的存儲空間可以不連續(xù)，基于鏈表的隊列（假定數(shù)據(jù)域為int類型）示意圖詳見圖3.36。

圖3.36 鏈隊列示意圖

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

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

若隊列中各個結(jié)點的數(shù)據(jù)類型為int類型，則對應(yīng)的鏈表結(jié)點類型為：

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

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

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

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

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

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

程序清單3.73 使用隊列接口的范例程序