Java 隊列實現原理
“隊列”這個單詞是英國人說的“排”。在英國“排隊”的意思就是站到一排當中去。計算機科學中，隊列是一種數據結構，有點類似棧，只是在隊列中第一個插入的數據項也會最先被移除，而在棧中，最后插入的數據項最先移除。隊列的作用就像電影院前的人們站成的排一樣：第一個進入附屬的人將最先到達隊頭買票。最后排隊的人最后才能買到票。
隊列和棧一樣也被用作程序員的工具。它也可以用于模擬真實世界的環境，例如模擬人們在銀行里排隊等待，飛機等待起飛，或者因特網絡上數據包等待傳送。
在計算機操作系統里，有各種隊列在安靜地工作著。打印作業在打印隊列中等待打印。當在鍵盤上敲擊時，也有一個存儲鍵入內容的隊列。同樣，如果使用文字處理程序敲擊一個鍵，而計算機又暫時要做其它的事，敲擊的內容不會丟失，它會排在隊列中等待，直到文字處理程序有時間來讀取它。利用隊列保證了鍵入內容在處理時其順序不會改變。
隊列的基本操作
隊列的兩個基本操作是inserting(插入)一個數據項，即把一個數據項放入隊尾，另一個是removing(移除)一個數據項，即移除隊頭的數據項。這類似于電影愛好者排隊買票時先排到隊尾，然后到達隊頭買票后離開隊列。
棧中的插入和移除數據項方法的命名是很標準，稱為push和pop。隊列的方法至今沒有標準化的命名。“插入”可以稱為put、add或 enque，而“刪除”可以叫delete、get或deque。插入數據項的隊尾，也可以叫作back、tail或end。而移除數據項的隊頭，也可以叫head。下面將使用insert、remove、front和rear。
插入將值插入隊尾，同時隊尾箭頭增加一，指向新的數據項。
數據項被移除后，同時隊頭指針增加一。通常實現隊列時，刪除的數據項還會保存在內存中，只是它不能被訪問了，因為隊頭指針已經移到它的下一個位置了。
和棧中的情況不同，隊列中的數據項不總是從數組的0下標處開始。移除了一些數據項后，隊頭指針會指向一個較高的下標位置。
查看操作返回隊頭數據項的值，然而并不從隊中刪除這個數據項。
要是想從空隊列中移除一個數據項或想在已經滿的隊列中插入一個數據項，應用程序都要提示出錯消息。
循環隊列
當在隊列中插入一個新數據項，隊頭的Rear箭頭向上移動，移向數組下標大的位置。移除數據項時，隊尾Front指針也會向上移動。這種設計可能和人們直觀察覺相反，因為人們在買電影票排隊時，隊伍總是向前移動的，當前面的人買完票離開隊伍后，其他人都向前移動。計算機中在隊列里刪除一個數據項后，也可以將其他數據項都向前移動，但這樣做的效率很差。相反，我們通過隊列中隊頭和隊尾指針的移動保持所有數據項的位置不變。
這樣設計的問題是隊尾指針很快就會移到數組的末端。雖然在數組的開始部分有空的數據項單元，這是移除的數據項的位置，但是由于因為隊尾指針不能再向后移動了，因此也不能再插入新的數據項，這該怎么辦？
環繞式處理
為了避免隊列不滿卻不能插入新數據項的問題，可以讓隊頭隊尾指針繞回到數組開始的位置。這就是循環隊列（有時也稱為“緩沖環”）。
指針回繞的過程：在隊列中插入足夠多的數據項，使隊尾指針指向數組的未端。再刪除幾個數組前端的數據項。現在插入一個新的數據項。就會看到隊尾指針從未端回繞到開始處的位置。新的數據項將插入這個位置。
插入更多的數據項。隊尾指針如預計的那樣向上移動。注意在隊尾指針回繞之后， 它現在處在隊頭指針的下面，這就顛倒了初始的位置。這可以稱為“折斷的序列”：隊列中的數據項存在數組兩個不同的序列中。
刪除足夠多的數據項后，隊頭指針也回繞。這時隊列的指針回到了初始運行時的位置狀態，隊頭指針在隊尾指針的下面。數據項也恢復為單一的連續的序列。
隊列的Java代碼
Queue.java程序創建了一個Queue類，它有insert()、remove()、peek()、isEmpty()和size()方法。
package 棧和隊列;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
class Queue{ private int maxSize; private long[] queArray; private int front; private int rear; private int nItems; public Queue(int s){ maxSize=s; queArray=new long[maxSize]; front=0; rear=-1; nItems=0; } public void insert(long j){ if(rear==maxSize-1) rear=-1; queArray[++rear]=j; nItems++; } public long remove(){ long temp=queArray[front++]; if(front==maxSize) front=0; nItems--; return temp; } public long peekFront(){ return queArray[front]; } public boolean isEmpty(){ return (nItems==0); } public boolean ifFull(){ return (nItems==maxSize); } public int size(){ return nItems; } } |
程序實現的Queue類中不但有front(隊頭)和rear(隊尾)字段，還有隊列中當前數據項的個數：nItems。
Insert()方法運行的前提條件是隊列不滿。在Main()中沒有顯示這個方法，不過通常應該先調用isFull()方法并且返回false 后，才調用insert()方法。（更通用的做法是在insert()方法中加入檢查隊列是否滿的判定，如果出現向已滿隊列里插入數據項的情況就拋出異常。）
一般情況，插入操作是rear（隊尾指針）加一后，在隊尾指針所指的位置處插入新的數據。但是，當rear指針指向數組的頂端，即 maxSize-1位置的時候，在插入數據項之前，它必須回繞到數組的底端。回繞操作把rear設置為-1，因此當rear加1后，它等于0，是數組底端的下標值，最后nItem加一。
Remove()方法運行的前提條件是隊列不空，在調用這個方法之前應該調用isEmpty()方法確保隊列不空，或者在remove()方法里加入這種出錯檢查的機制。
移除（remove）操作總是由front指針得到隊頭數據項的值，然后將front加一。但是，如果這樣做使front的值超過數組的頂端，front就必須繞回到數組下標為0的位置上。作這種檢驗的同時，先將返回值臨時存儲起來。最后nItem減一。
Peek()方法簡單易懂：它返回front指針所指數據項的值。有些隊列的實現也允許查看隊列隊尾數據項的值；比如這些方法可稱為peekFront()、peekRear()、或者只是front()和rear()。
isEmpty()、isFull()和size()方法的實現都依賴于nItems字段，它們分別返回nItems是否等于0，是否等于maxSize，或者返回它本身值。
在Queue類中包含數據項計數字段nItems會使insert()和remove()方法增加一點額外的操作，因為insert()和 remove()方法必須分別遞增和遞減這個變量值。這可能算不上額外的開銷，但是如果處理大量的插入和移除操作，這就可能會影響性能了。
因為，一些隊列的實現不使用數據項計數的字段，而是通過front和rear來計算出隊列是否空或者滿以及數據項的個數。如果這樣做，isEmpty()、ifFull()和size()例程會相當復雜，因為就像前面講過的那樣，數據項的序列或者被折成兩段，或者是連續的一段。
而且，一個奇怪的問題出現了。當隊列滿的時候，front和rear指針取一定的位置，但是當隊列為空時，也可能呈現相同的位置關系。于是在同一時間，隊列似乎可能是滿的，也可能是空的。這個問題的解決方法是：讓數組容量比隊列數據項個數的最大值學要大一。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://www.cnblogs.com/key2012/archive/2012/12/18/2822939.html
