什麼是資料結構 Queue

這篇文章中，我們將重溫一下Java中的佇列。佇列是一個線性資料結構，它的工作非常直觀且易於理解。與遵循LIFO（後進先出）原則的堆疊不同，佇列遵循FIFO（先進先出）原則。換句話說，在佇列資料結構中，我們刪除的都是最近的專案。這就好比超市排隊結賬，先排隊的人就先結完賬，先走。

佇列支援的四種基本操作：

enqueue（）：enqueue方法將一項新增到佇列中

dequeue（）：dequeue方法從佇列中刪除最近新增的項

front（）：front方法返回佇列前面的項

rear（）：該方法返回佇列末尾的項，即最近插入的項

除了這四個基本操作之外，我們當然也會受益於一些輔助方法：

size（）：返回佇列中的專案數

isFull（）：如果佇列已滿，則為True

isEmpty（）：如果佇列為空則為True

我們還需要一些私有變數，用於跟蹤佇列中的位置，以及實際佇列的內部陣列：

front：前部元素的當前位置

rear：後部元素的當前位置

size：佇列的當前大小（專案數）

array：內部陣列，包含佇列中的實際項

我們還將使我們的類具有通用性，避免使用只能將原生int“物件”插入到Queue中的一般示例，我們佇列的程式碼框架如下所示：

圖一

圖二

圖三

如果您閱讀了類註釋，您可能已經注意到引入了兩個新的術語：Ring Buffer和Circular Queue。我們希望我們的內部陣列充當環形緩衝區，這意味著如果前面或後面到達陣列的最後位置，我們將重新連線到陣列的開頭。

為了解釋為什麼我們應該建立一個迴圈佇列，我們首先要解釋如果我們只是建立一個線性佇列我們將遇到的問題。假設您有一個可以包含總共五個元素的佇列，則對佇列執行以下操作：

enqueue（1）。 Front = 0， rear = 0。

enqueue（2）。 Front = 0， rear = 1。

enqueue（3）。 Front = 0， rear = 2。

dequeue（）。 Front = 1， rear = 2。

dequeue（）。 Front = 2， rear = 2。

enqueue（4）。 Front = 2， rear = 3。

enqueue（5）。 Front = 2， rear = 4。

執行這些操作後，佇列將如下所示：

如您所見，佇列中有2個可用的點，索引0和1。但是，如果佇列不是迴圈的，如果我們試圖將數字6排隊，會發生什麼？如果您猜到佇列將報告為已滿，那麼您是對的！要解決這個問題，我們需要使佇列迴圈。 如果已達到佇列末尾（假設佇列未滿），我們希望前後都重置回位置0。

現在，讓我們完成程式碼框架並編寫一個迴圈佇列。

圖一

圖二

圖三

圖四

我還在JUnit中編寫了一個簡單的單元測試。

圖一

圖二