2.6　隊列結構

在程序設計中，隊列結構也是一種常用的數據結構。隊列結構和棧結構類似，其在現實生活中都有對應的例子，可以說隊列結構是來源于生活的數據結構。

2.6.1　什么是隊列結構

隊列結構是從數據的運算來分類的，也就是說隊列結構具有特殊的運算規則。而從數據的邏輯結構來看，隊列結構其實就是一種線性結構。如果從數據的存儲結構來進一步劃分，隊列結構包括兩類。

?順序隊列結構：即使用一組地址連續的內存單元依次保存隊列中的數據。在程序中，可以定義一個指定大小的結構數組作為隊列。

?鏈式隊列結構：即使用鏈表形式保存隊列中各元素的值。

典型的隊列結構，如圖2-11所示。從圖中可以看出，在隊列結構中允許對兩端進行操作，但是兩端的操作不同。在表的一端只能進行刪除操作，稱為隊頭；在表的另一端只能進行插入操作，稱為隊尾。如果隊列中沒有數據元素，則稱為空隊列。

從數據的運算角度來分析，隊列結構是按照“先進先出”（First In First Out，FIFO）的原則處理結點數據的。

其實，隊列結構在日常生活中有很多生動的例子。例如，銀行的電子排號系統，先來的人取的號靠前，后來的人取的號靠后。這樣，先來的人將最先得到服務，后來的人將后得到服務，一切按照“先來先服務”的原則。

在硬件的存儲類芯片中，有一類根據隊列結構構造的芯片，即FIFO芯片。這類芯片具有一定的容量，保留了一端作為數據的存入，另一端作為數據的讀出。先存入的數據將先被讀出。

在隊列結構中，數據運算非常簡單。一般隊列結構的基本操作只有兩個。

?入隊列：將一個元素添加到隊尾（相當于到隊列最后排隊等候）。

?出隊列：將隊頭的元素取出，同時刪除該元素，使后一個元素成為隊頭。

除此之外，還需要有初始化隊列、獲取隊列長度等簡單的操作。下面分析如何在Java語言中建立順序隊列結構，并完成順序隊列結構的基本運算。

2.6.2　準備數據

學習了前面的理論知識后，下面就開始隊列結構的程序設計。首先需要準備數據，即準備在隊列操作中需要用到的變量及數據結構等。示例代碼如下：

在上述代碼中，定義了隊列結構的最大長度QUEUELEN，隊列結構數據元素的類DATA4及隊列結構的類SQType。在類SQType中，data為數據元素，head為隊頭的序號，tail為隊尾的序號。當head=0時表示隊列為空，當tail=QUEUELEN時表示隊列已滿。

2.6.3　初始化隊列結構

在使用順序隊列之前，首先要創建一個空的順序隊列，即初始化順序隊列。順序隊列的初始化操作步驟如下：

（1）按符號常量QUEUELEN指定的大小申請一片內存空間，用來保存隊列中的數據。

（2）設置head=0和tail=0，表示一個空棧。

初始化順序隊列的代碼示例如下：

在上述代碼中，首先使用new關鍵字申請內存，申請成功后設置隊頭和隊尾，然后返回申請內存的首地址。如果申請內存失敗，將返回null。

2.6.4　判斷空隊列

判斷空隊列即判斷一個隊列結構是否為空。如果是空隊列，則表示該隊列結構中沒有數據。此時可以進行入隊列操作，但不可以進行出隊列操作。

判斷空隊列的代碼示例如下：

在上述代碼中，輸入參數q是一個指向操作的隊列的引用。在程序中，根據隊列head是否等于tail，判斷隊列是否為空。

2.6.5　判斷滿隊列

判斷滿隊列即判斷一個隊列結構是否為滿。如果是滿隊列，則表示該隊列結構中沒有多余的空間來保存額外數據。此時不可以進行入隊列操作，但是可以進行出隊列操作。

判斷滿隊列的代碼示例如下：

在上述代碼中，輸入參數q是一個指向操作的隊列的引用。程序中，判斷隊列tail是否已等于符號常量QUEUELEN，從而判斷隊列是否已滿。

2.6.6　清空隊列

清空隊列即清除隊列中的所有數據。清空隊列的代碼示例如下：

在上述代碼中，輸入參數q是一個指向操作的隊列的引用。程序中，簡單地將隊列頂引用head和tail設置為0，表示執行清空隊列操作。

2.6.7　釋放空間

釋放空間即釋放隊列結構所占用的內存單元。由前面知道，在初始化隊列結構時，使用了new關鍵字分配內存空間。雖然可以使用清空隊列操作，但是清空隊列操作并沒有釋放內存空間，這就需要使用賦值null操作釋放所分配的內存。

釋放空間的代碼示例如下：

在上述代碼中，輸入參數q是一個指向操作的隊列的引用。在程序中，直接使用賦值null操作釋放所分配的內存。一般在不需要使用隊列結構的時候使用，特別是程序結束時。

2.6.8　入隊列

入隊列是隊列結構的基本操作，主要操作是將數據元素保存到隊列結構。入隊列操作的具體步驟如下：

（1）首先判斷隊列頂tail，如果tail等于QUEUELEN，則表示溢出，進行出錯處理；否則執行以下操作。

（2）設置tail=tail+1（隊列頂引用加1，指向入隊列地址）。

（3）將入隊列元素保存到tail指向的位置。

入隊列操作的代碼示例如下：

在上述代碼中，輸入參數q是一個指向操作的隊列的引用，輸入參數data是需要入隊列的數據元素。程序中首先判斷隊列是否溢出，如果溢出則不進行入隊列操作，否則修改隊列頂引用的值，再將元素入隊列。

2.6.9　出隊列

出隊列是隊列結構的基本操作，主要操作與入隊列相反，其操作是從隊列頂彈出一個數據元素。出隊列操作的具體步驟如下：

（1）判斷隊列head，如果head等于tail，則表示為空隊列，進行出錯處理；否則，執行下面的步驟。

（2）從隊列首部取出隊頭元素（實際是返回隊頭元素的引用）。

（3）設修改隊頭head的序號，使其指向后一個元素。

在上述代碼中，輸入參數q是一個指向操作的隊列的引用。該方法返回值是一個DATA類型的數據，返回值是指向該數據元素的引用。

2.6.10　讀結點數據

讀結點數據即讀取隊列結構中結點的數據，這里的讀操作其實就是讀取隊列頭的數據。需要注意的是，讀結點數據的操作和出隊列操作不同。讀結點數據的操作僅顯示隊列頂結點數據的內容，而出隊列操作則將隊列頂數據彈出，該數據不再存在了。

讀結點數據的代碼示例如下：

在上述代碼中，輸入參數q是一個指向操作的隊列的引用。該方法的返回值同樣是一個DATA4類型的引用數據，返回值是指向數據元素的引用。

2.6.11　計算隊列長度

計算隊列長度即統計該隊列中數據結點的個數。計算隊列長度的方法比較簡單，用隊尾序號減去隊頭序號即可。

計算隊列長度的代碼示例如下：

在上述代碼中，輸入參數q是一個指向操作的隊列的引用。該方法的返回值便是隊列的長度。

2.6.12　隊列結構操作實例

學習了前面的隊列結構的基本運算之后，便可以輕松地完成對隊列結構的各種操作。下面給出一個完整的例子，來演示隊列結構的創建、入隊列和出隊列等操作。代碼示例如下：

【程序2-4】

在上述代碼中，main（）主方法首先初始化隊列結構，然后循環進行入隊列操作，添加數據結點，當輸入全部為0時則退出結點添加的進程。接下來，用戶每按一次按鍵，則進行一次出隊列操作，顯示結點數據。當為空隊列時，退出程序。然后該程序執行結果，如圖2-12所示。