- 相關(guān)推薦
Java 隊列實現(xiàn)原理及簡單實現(xiàn)代碼
Java 隊列實現(xiàn)原理
“隊列”這個單詞是英國人說的“排”。在英國“排隊”的意思就是站到一排當中去。計算機科學中，隊列是一種數(shù)據(jù)結(jié)構(gòu)，有點類似棧，只是在隊列中第一個插入的數(shù)據(jù)項也會最先被移除，而在棧中，最后插入的數(shù)據(jù)項最先移除。隊列的作用就像電影院前的人們站成的排一樣：第一個進入附屬的人將最先到達隊頭買票。最后排隊的人最后才能買到票。
隊列和棧一樣也被用作程序員的工具。它也可以用于模擬真實世界的環(huán)境，例如模擬人們在銀行里排隊等待，飛機等待起飛，或者因特網(wǎng)絡(luò)上數(shù)據(jù)包等待傳送。
在計算機操作系統(tǒng)里，有各種隊列在安靜地工作著。打印作業(yè)在打印隊列中等待打印。當在鍵盤上敲擊時，也有一個存儲鍵入內(nèi)容的隊列。同樣，如果使用文字處理程序敲擊一個鍵，而計算機又暫時要做其它的事，敲擊的內(nèi)容不會丟失，它會排在隊列中等待，直到文字處理程序有時間來讀取它。利用隊列保證了鍵入內(nèi)容在處理時其順序不會改變。
隊列的基本操作
隊列的兩個基本操作是ing(插入)一個數(shù)據(jù)項，即把一個數(shù)據(jù)項放入隊尾，另一個是removing(移除)一個數(shù)據(jù)項，即移除隊頭的數(shù)據(jù)項。這類似于電影愛好者排隊買票時先排到隊尾，然后到達隊頭買票后離開隊列。
棧中的插入和移除數(shù)據(jù)項方法的命名是很標準，稱為push和pop。隊列的方法至今沒有標準化的命名。“插入”可以稱為put、add或 enque，而“刪除”可以叫、get或deque。插入數(shù)據(jù)項的隊尾，也可以叫作back、tail或end。而移除數(shù)據(jù)項的隊頭，也可以叫head。下面將使用、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ù)項，應(yīng)用程序都要提示出錯消息。
循環(huán)隊列
當在隊列中插入一個新數(shù)據(jù)項，隊頭的Rear箭頭向上移動，移向數(shù)組下標大的位置。移除數(shù)據(jù)項時，隊尾Front指針也會向上移動。這種設(shè)計可能和人們直觀察覺相反，因為人們在買電影票排隊時，隊伍總是向前移動的，當前面的人買完票離開隊伍后，其他人都向前移動。計算機中在隊列里刪除一個數(shù)據(jù)項后，也可以將其他數(shù)據(jù)項都向前移動，但這樣做的效率很差。相反，我們通過隊列中隊頭和隊尾指針的移動保持所有數(shù)據(jù)項的位置不變。
這樣設(shè)計的問題是隊尾指針很快就會移到數(shù)組的末端。雖然在數(shù)組的開始部分有空的數(shù)據(jù)項單元，這是移除的數(shù)據(jù)項的位置，但是由于因為隊尾指針不能再向后移動了，因此也不能再插入新的數(shù)據(jù)項，這該怎么辦？
環(huán)繞式處理
為了避免隊列不滿卻不能插入新數(shù)據(jù)項的問題，可以讓隊頭隊尾指針繞回到數(shù)組開始的位置。這就是循環(huán)隊列（有時也稱為“緩沖環(huán)”）。
指針回繞的過程：在隊列中插入足夠多的數(shù)據(jù)項，使隊尾指針指向數(shù)組的未端。再刪除幾個數(shù)組前端的數(shù)據(jù)項�，F(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類，它有()、remove()、peek()、isEmpty()和size()方法。
package 棧和隊列;
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 (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()中沒有顯示這個方法，不過通常應(yīng)該先調(diào)用isFull()方法并且返回false 后，才調(diào)用()方法。（更通用的做法是在()方法中加入檢查隊列是否滿的判定，如果出現(xiàn)向已滿隊列里插入數(shù)據(jù)項的情況就拋出異常。）
一般情況，插入操作是rear（隊尾指針）加一后，在隊尾指針所指的位置處插入新的數(shù)據(jù)。但是，當rear指針指向數(shù)組的頂端，即 maxSize-1位置的時候，在插入數(shù)據(jù)項之前，它必須回繞到數(shù)組的底端。回繞操作把rear設(shè)置為-1，因此當rear加1后，它等于0，是數(shù)組底端的下標值，最后nItem加一。
Remove()方法運行的前提條件是隊列不空，在調(diào)用這個方法之前應(yīng)該調(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會使()和remove()方法增加一點額外的操作，因為()和 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ù)的最大值學要大一。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
【Java 隊列實現(xiàn)原理及簡單實現(xiàn)代碼】相關(guān)文章：
java構(gòu)造函數(shù)實現(xiàn)代碼示例08-23
JavaScript簡單實現(xiàn)放大鏡效果代碼09-24
Java實現(xiàn)在不同線程中運行的代碼實例詳解06-11
用canvas就可以實現(xiàn)圖片的濾鏡轉(zhuǎn)化代碼實現(xiàn)07-19
關(guān)于Java動態(tài)實現(xiàn)的方法08-23
使用python實現(xiàn)Linux異步epoll的代碼10-27
PHP實現(xiàn)大文件上傳源代碼10-21
實現(xiàn)java屏幕抓屏的方法08-24
java通用組合算法如何實現(xiàn)09-12