Java 隊列實現(xiàn)原理
“隊列”這個單詞是英國人說的“排”。在英國“排隊”的意思就是站到一排當中去。計算機科學中，隊列是一種數(shù)據(jù)結(jié)構(gòu)，有點類似棧，只是在隊列中第一個插入的數(shù)據(jù)項也會最先被移除，而在棧中，最后插入的數(shù)據(jù)項最先移除。隊列的作用就像電影院前的人們站成的排一樣：第一個進入附屬的人將最先到達隊頭買票。最后排隊的人最后才能買到票。
隊列和棧一樣也被用作程序員的工具。它也可以用于模擬真實世界的環(huán)境，例如模擬人們在銀行里排隊等待，飛機等待起飛，或者因特網(wǎng)絡上數(shù)據(jù)包等待傳送。
在計算機操作系統(tǒng)里，有各種隊列在安靜地工作著。打印作業(yè)在打印隊列中等待打印。當在鍵盤上敲擊時，也有一個存儲鍵入內(nèi)容的隊列。同樣，如果使用文字處理程序敲擊一個鍵，而計算機又暫時要做其它的事，敲擊的內(nèi)容不會丟失，它會排在隊列中等待，直到文字處理程序有時間來讀取它。利用隊列保證了鍵入內(nèi)容在處理時其順序不會改變。
隊列的基本操作
隊列的兩個基本操作是inserting(插入)一個數(shù)據(jù)項，即把一個數(shù)據(jù)項放入隊尾，另一個是removing(移除)一個數(shù)據(jù)項，即移除隊頭的數(shù)據(jù)項。這類似于電影愛好者排隊買票時先排到隊尾，然后到達隊頭買票后離開隊列。
棧中的插入和移除數(shù)據(jù)項方法的命名是很標準，稱為push和pop。隊列的方法至今沒有標準化的命名。“插入”可以稱為put、add或 enque，而“刪除”可以叫delete、get或deque。插入數(shù)據(jù)項的隊尾，也可以叫作back、tail或end。而移除數(shù)據(jù)項的隊頭，也可以叫head。下面將使用insert、remove、front和rear。
插入將值插入隊尾，同時隊尾箭頭增加一，指向新的數(shù)據(jù)項。
數(shù)據(jù)項被移除后，同時隊頭指針增加一。通常實現(xiàn)隊列時，刪除的數(shù)據(jù)項還會保存在內(nèi)存中，只是它不能被訪問了，因為隊頭指針已經(jīng)移到它的下一個位置了。
和棧中的情況不同，隊列中的數(shù)據(jù)項不總是從數(shù)組的0下標處開始。移除了一些數(shù)據(jù)項后，隊頭指針會指向一個較高的下標位置。
查看操作返回隊頭數(shù)據(jù)項的值，然而并不從隊中刪除這個數(shù)據(jù)項。
要是想從空隊列中移除一個數(shù)據(jù)項或想在已經(jīng)滿的隊列中插入一個數(shù)據(jù)項，應用程序都要提示出錯消息。
循環(huán)隊列
當在隊列中插入一個新數(shù)據(jù)項，隊頭的Rear箭頭向上移動，移向數(shù)組下標大的位置。移除數(shù)據(jù)項時，隊尾Front指針也會向上移動。這種設計可能和人們直觀察覺相反，因為人們在買電影票排隊時，隊伍總是向前移動的，當前面的人買完票離開隊伍后，其他人都向前移動。計算機中在隊列里刪除一個數(shù)據(jù)項后，也可以將其他數(shù)據(jù)項都向前移動，但這樣做的效率很差。相反，我們通過隊列中隊頭和隊尾指針的移動保持所有數(shù)據(jù)項的位置不變。
這樣設計的問題是隊尾指針很快就會移到數(shù)組的末端。雖然在數(shù)組的開始部分有空的數(shù)據(jù)項單元，這是移除的數(shù)據(jù)項的位置，但是由于因為隊尾指針不能再向后移動了，因此也不能再插入新的數(shù)據(jù)項，這該怎么辦？
環(huán)繞式處理
為了避免隊列不滿卻不能插入新數(shù)據(jù)項的問題，可以讓隊頭隊尾指針繞回到數(shù)組開始的位置。這就是循環(huán)隊列（有時也稱為“緩沖環(huán)”）。
指針回繞的過程：在隊列中插入足夠多的數(shù)據(jù)項，使隊尾指針指向數(shù)組的未端。再刪除幾個數(shù)組前端的數(shù)據(jù)項。現(xiàn)在插入一個新的數(shù)據(jù)項。就會看到隊尾指針從未端回繞到開始處的位置。新的數(shù)據(jù)項將插入這個位置。
插入更多的數(shù)據(jù)項。隊尾指針如預計的那樣向上移動。注意在隊尾指針回繞之后， 它現(xiàn)在處在隊頭指針的下面，這就顛倒了初始的位置。這可以稱為“折斷的序列”：隊列中的數(shù)據(jù)項存在數(shù)組兩個不同的序列中。
刪除足夠多的數(shù)據(jù)項后，隊頭指針也回繞。這時隊列的指針回到了初始運行時的位置狀態(tài)，隊頭指針在隊尾指針的下面。數(shù)據(jù)項也恢復為單一的連續(xù)的序列。
隊列的Java代碼
Queue.java程序創(chuàng)建了一個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; } } |
程序?qū)崿F(xiàn)的Queue類中不但有front(隊頭)和rear(隊尾)字段，還有隊列中當前數(shù)據(jù)項的個數(shù)：nItems。
Insert()方法運行的前提條件是隊列不滿。在Main()中沒有顯示這個方法，不過通常應該先調(diào)用isFull()方法并且返回false 后，才調(diào)用insert()方法。（更通用的做法是在insert()方法中加入檢查隊列是否滿的判定，如果出現(xiàn)向已滿隊列里插入數(shù)據(jù)項的情況就拋出異常。）
一般情況，插入操作是rear（隊尾指針）加一后，在隊尾指針所指的位置處插入新的數(shù)據(jù)。但是，當rear指針指向數(shù)組的頂端，即 maxSize-1位置的時候，在插入數(shù)據(jù)項之前，它必須回繞到數(shù)組的底端。回繞操作把rear設置為-1，因此當rear加1后，它等于0，是數(shù)組底端的下標值，最后nItem加一。
Remove()方法運行的前提條件是隊列不空，在調(diào)用這個方法之前應該調(diào)用isEmpty()方法確保隊列不空，或者在remove()方法里加入這種出錯檢查的機制。
移除（remove）操作總是由front指針得到隊頭數(shù)據(jù)項的值，然后將front加一。但是，如果這樣做使front的值超過數(shù)組的頂端，front就必須繞回到數(shù)組下標為0的位置上。作這種檢驗的同時，先將返回值臨時存儲起來。最后nItem減一。
Peek()方法簡單易懂：它返回front指針所指數(shù)據(jù)項的值。有些隊列的實現(xiàn)也允許查看隊列隊尾數(shù)據(jù)項的值；比如這些方法可稱為peekFront()、peekRear()、或者只是front()和rear()。
isEmpty()、isFull()和size()方法的實現(xiàn)都依賴于nItems字段，它們分別返回nItems是否等于0，是否等于maxSize，或者返回它本身值。
在Queue類中包含數(shù)據(jù)項計數(shù)字段nItems會使insert()和remove()方法增加一點額外的操作，因為insert()和 remove()方法必須分別遞增和遞減這個變量值。這可能算不上額外的開銷，但是如果處理大量的插入和移除操作，這就可能會影響性能了。
因為，一些隊列的實現(xiàn)不使用數(shù)據(jù)項計數(shù)的字段，而是通過front和rear來計算出隊列是否空或者滿以及數(shù)據(jù)項的個數(shù)。如果這樣做，isEmpty()、ifFull()和size()例程會相當復雜，因為就像前面講過的那樣，數(shù)據(jù)項的序列或者被折成兩段，或者是連續(xù)的一段。
而且，一個奇怪的問題出現(xiàn)了。當隊列滿的時候，front和rear指針取一定的位置，但是當隊列為空時，也可能呈現(xiàn)相同的位置關(guān)系。于是在同一時間，隊列似乎可能是滿的，也可能是空的。這個問題的解決方法是：讓數(shù)組容量比隊列數(shù)據(jù)項個數(shù)的最大值學要大一。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://www.cnblogs.com/key2012/archive/2012/12/18/2822939.html
