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