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

第三章為算法與數據結構，本文為3.6 隊列ADT。

>>>3.6.1建立抽象

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

圖 3.28 隊列示意圖

其抽象定義如下：

• 類型名：隊列（Queue）

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

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

>>>3.6.2 建立接口

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

1、定義抽象類型queueADT

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

2、接口函數聲明

• 創建隊列

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

后置條件：返回隊列。

其調用形式如下：

• 銷毀隊列

在創建隊列時，具體實現會根據實際情況分配隊列相關的存儲空間，如隊列對象本身的存儲空間，隊列項的存儲空間等。因此，當一個隊列不在使用時，應該釋放掉隊列相關的內存空間，以銷毀一個隊列，銷毀后的隊列不再存在，無法繼續使用。其函數原型如下：

前置條件：queue為之前創建的隊列；

后置條件：釋放隊列相關的所有內存，隊列被銷毀，不再有效。

其調用形式如下：

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

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

前置條件：queue為之前創建的隊列，value是待加入隊尾的數據；

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

其調用形式如下：

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

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

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

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

其調用形式如下：

• 判斷隊列是否為空

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

前置條件：queue為之前創建的隊列；

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

其調用形式如下：

• 判斷隊列是否已滿

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

前置條件：queue為之前創建的隊列；

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

其調用形式如下：

• 確定隊列中元素的個數

確定棧中元素的個數的函數原型如下：

前置條件：queue為之前創建的隊列；

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

其調用形式如下：

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

>>>3.6.3 實現與使用接口

在實現隊列之前，首先需要確定使用何種數據存儲結構。一般來說，可以使用地址連續的內存空間存儲數據，比如，使用數組或動態分配一段內存空間；也可以使用地址非連續的鏈表結構存儲數據。

1、順序隊列

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

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

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

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

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

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

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

圖3.31 繼續進行出隊列、入隊列操作

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

圖3.32 循環隊列

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

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

圖3.33 data8~data11依次入隊列

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

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

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

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

這里的結構體類型struct queueCDT只有聲明，還沒有具體的定義。因此無論何種實現方式，都需要先實現struct queueCDT類型的定義。

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

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

程序清單3.71 順序隊列的實現（queue.c）

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

2、鏈隊列

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

圖3.36 鏈隊列示意圖

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

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

若隊列中各個結點的數據類型為int類型，則對應的鏈表結點類型為：

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

程序清單3.72 鏈隊列的實現（queue_list.c）

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

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

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

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

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