java佇列

“佇列”這個單詞是英國人說的“排”。在英國“排隊”的意思就是站到一排當中去。計算機科學中，佇列是一種數據結構，有點類似棧，只是在佇列中第一個插入的數據項也會最先被移除，而在棧中，最後插入的數據項最先移除。佇列的作用就像電影院前的人們站成的排一樣：第一個進入附屬的人將最先到達隊頭買票。最後排隊的人最後才能買到票。

在計算機中，佇列和棧一樣也被用作程式設計師的工具。它也可以用於模擬真實世界的環境，例如模擬人們在銀行里排隊等待，飛機等待起飛，或者網際網路絡上數據包等待傳送。

基本介紹

• 中文名：java佇列
• 性質：數據結構

基本信息

在計算機作業系統里，有各種佇列在安靜地工作著。列印作業在列印佇列中等待列印。當在鍵盤上敲擊時，也有一個存儲鍵入內容的佇列。同樣，如果使用文字處理程式敲擊一個鍵，而計算機又暫時要做其它的事，敲擊的內容不會丟失，它會排在佇列中等待，直到文字處理程式有時間來讀取它。利用佇列保證了鍵入內容在處理時其順序不會改變。

基本操作

佇列的兩個基本操作是inserting(插入)一個數據項，即把一個數據項放入隊尾，另一個是removing(移除)一個數據項，即移除隊頭的數據項。這類似於電影愛好者排隊買票時先排到隊尾，然後到達隊頭買票後離開佇列。

棧中的插入和移除數據項方法的命名是很標準，稱為push和pop。佇列的方法沒有標準化的命名。“插入”可以稱為put、add或enque，而“刪除”可以叫delete、get或deque。插入數據項的隊尾，也可以叫作back、tail或end。而移除數據項的隊頭，也可以叫head。下面將使用insert、remove、front和rear。

插入將值插入隊尾，同時隊尾箭頭增加一，指向新的數據項。

數據項被移除後，同時隊頭指針增加一。通常實現佇列時，刪除的數據項還會保存在記憶體中，只是它不能被訪問了，因為隊頭指針已經移到它的下一個位置了。

和棧中的情況不同，佇列中的數據項不總是從數組的0下標處開始。移除了一些數據項後，隊頭指針會指向一個較高的下標位置。

查看操作返回隊頭數據項的值，然而並不從隊中刪除這個數據項。

要是想從空佇列中移除一個數據項或想在已經滿的佇列中插入一個數據項，應用程式都要提示出錯訊息。

循環佇列

當在佇列中插入一個新數據項，隊頭的Rear箭頭向上移動，移向數組下標大的位置。移除數據項時，隊尾Front指針也會向上移動。這種設計可能和人們直觀察覺相反，因為人們在買電影票排隊時，隊伍總是向前移動的，當前面的人買完票離開隊伍後，其他人都向前移動。計算機中在佇列里刪除一個數據項後，也可以將其他數據項都向前移動，但這樣做的效率很差。相反，我們通過佇列中隊頭和隊尾指針的移動保持所有數據項的位置不變。

這樣設計的問題是隊尾指針很快就會移到數組的末端。雖然在數組的開始部分有空的數據項單元，這是移除的數據項的位置，但是由於因為隊尾指針不能再向後移動了，因此也不能再插入新的數據項，這該怎么辦？

環繞式處理

為了避免佇列不滿卻不能插入新數據項的問題，可以讓隊頭隊尾指針繞回到數組開始的位置。這就是循環佇列（有時也稱為“緩衝環”）。

指針迴繞的過程：在佇列中插入足夠多的數據項，使隊尾指針指向數組的未端。再刪除幾個數組前端的數據項。插入一個新的數據項。就會看到隊尾指針從未端迴繞到開始處的位置。新的數據項將插入這個位置。

插入更多的數據項。隊尾指針如預計的那樣向上移動。注意在隊尾指針迴繞之後， 它處在隊頭指針的下面，這就顛倒了初始的位置。這可以稱為“折斷的序列”：佇列中的數據項存在數組兩個不同的序列中。

刪除足夠多的數據項後，隊頭指針也迴繞。這時佇列的指針回到了初始運行時的位置狀態，隊頭指針在隊尾指針的下面。數據項也恢復為單一的連續的序列。