Java 隊列實(shí)現(xiàn)原理

“隊列”這個單詞是英國人說的“排”。在英國“排隊”的意思就是站到一排當(dāng)中去。計算機(jī)科學(xué)中，隊列是一種數(shù)據(jù)結(jié)構(gòu)，有點(diǎn)類似棧，只是在隊列中第一個插入的數(shù)據(jù)項(xiàng)也會最先被移除，而在棧中，最后插入的數(shù)據(jù)項(xiàng)最先移除。隊列的作用就像電影院前的人們站成的排一樣：第一個進(jìn)入附屬的人將最先到達(dá)隊頭買票。最后排隊的人最后才能買到票。

隊列和棧一樣也被用作程序員的工具。它也可以用于模擬真實(shí)世界的環(huán)境，例如模擬人們在銀行里排隊等待，飛機(jī)等待起飛，或者因特網(wǎng)絡(luò)上數(shù)據(jù)包等待傳送。

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

隊列的基本操作

隊列的兩個基本操作是inserting(插入)一個數(shù)據(jù)項(xiàng)，即把一個數(shù)據(jù)項(xiàng)放入隊尾，另一個是removing(移除)一個數(shù)據(jù)項(xiàng)，即移除隊頭的數(shù)據(jù)項(xiàng)。這類似于電影愛好者排隊買票時先排到隊尾，然后到達(dá)隊頭買票后離開隊列。

棧中的插入和移除數(shù)據(jù)項(xiàng)方法的命名是很標(biāo)準(zhǔn)，稱為push和pop。隊列的方法至今沒有標(biāo)準(zhǔn)化的命名?！安迦搿笨梢苑Q為put、add或 enque，而“刪除”可以叫delete、get或deque。插入數(shù)據(jù)項(xiàng)的隊尾，也可以叫作back、tail或end。而移除數(shù)據(jù)項(xiàng)的隊頭，也可以叫head。下面將使用insert、remove、front和rear。

插入將值插入隊尾，同時隊尾箭頭增加一，指向新的數(shù)據(jù)項(xiàng)。

數(shù)據(jù)項(xiàng)被移除后，同時隊頭指針增加一。通常實(shí)現(xiàn)隊列時，刪除的數(shù)據(jù)項(xiàng)還會保存在內(nèi)存中，只是它不能被訪問了，因?yàn)殛狀^指針已經(jīng)移到它的下一個位置了。

和棧中的情況不同，隊列中的數(shù)據(jù)項(xiàng)不總是從數(shù)組的0下標(biāo)處開始。移除了一些數(shù)據(jù)項(xiàng)后，隊頭指針會指向一個較高的下標(biāo)位置。

查看操作返回隊頭數(shù)據(jù)項(xiàng)的值，然而并不從隊中刪除這個數(shù)據(jù)項(xiàng)。

要是想從空隊列中移除一個數(shù)據(jù)項(xiàng)或想在已經(jīng)滿的隊列中插入一個數(shù)據(jù)項(xiàng)，應(yīng)用程序都要提示出錯消息。

循環(huán)隊列

當(dāng)在隊列中插入一個新數(shù)據(jù)項(xiàng)，隊頭的Rear箭頭向上移動，移向數(shù)組下標(biāo)大的位置。移除數(shù)據(jù)項(xiàng)時，隊尾Front指針也會向上移動。這種設(shè)計可能和人們直觀察覺相反，因?yàn)槿藗冊谫I電影票排隊時，隊伍總是向前移動的，當(dāng)前面的人買完票離開隊伍后，其他人都向前移動。計算機(jī)中在隊列里刪除一個數(shù)據(jù)項(xiàng)后，也可以將其他數(shù)據(jù)項(xiàng)都向前移動，但這樣做的效率很差。相反，我們通過隊列中隊頭和隊尾指針的移動保持所有數(shù)據(jù)項(xiàng)的位置不變。

這樣設(shè)計的問題是隊尾指針很快就會移到數(shù)組的末端。雖然在數(shù)組的開始部分有空的數(shù)據(jù)項(xiàng)單元，這是移除的數(shù)據(jù)項(xiàng)的位置，但是由于因?yàn)殛犖仓羔槻荒茉傧蚝笠苿恿耍虼艘膊荒茉俨迦胄碌臄?shù)據(jù)項(xiàng)，這該怎么辦？

環(huán)繞式處理

為了避免隊列不滿卻不能插入新數(shù)據(jù)項(xiàng)的問題，可以讓隊頭隊尾指針繞回到數(shù)組開始的位置。這就是循環(huán)隊列（有時也稱為“緩沖環(huán)”）。

指針回繞的過程：在隊列中插入足夠多的數(shù)據(jù)項(xiàng)，使隊尾指針指向數(shù)組的未端。再刪除幾個數(shù)組前端的數(shù)據(jù)項(xiàng)?，F(xiàn)在插入一個新的數(shù)據(jù)項(xiàng)。就會看到隊尾指針從未端回繞到開始處的位置。新的數(shù)據(jù)項(xiàng)將插入這個位置。

插入更多的數(shù)據(jù)項(xiàng)。隊尾指針如預(yù)計的那樣向上移動。注意在隊尾指針回繞之后， 它現(xiàn)在處在隊頭指針的下面，這就顛倒了初始的位置。這可以稱為“折斷的序列”：隊列中的數(shù)據(jù)項(xiàng)存在數(shù)組兩個不同的序列中。

刪除足夠多的數(shù)據(jù)項(xiàng)后，隊頭指針也回繞。這時隊列的指針回到了初始運(yùn)行時的位置狀態(tài)，隊頭指針在隊尾指針的下面。數(shù)據(jù)項(xiàng)也恢復(fù)為單一的連續(xù)的序列。

隊列的Java代碼

Queue.java程序創(chuàng)建了一個Queue類，它有insert()、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 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(隊尾)字段，還有隊列中當(dāng)前數(shù)據(jù)項(xiàng)的個數(shù)：nItems。

Insert()方法運(yùn)行的前提條件是隊列不滿。在Main()中沒有顯示這個方法，不過通常應(yīng)該先調(diào)用isFull()方法并且返回false 后，才調(diào)用insert()方法。（更通用的做法是在insert()方法中加入檢查隊列是否滿的判定，如果出現(xiàn)向已滿隊列里插入數(shù)據(jù)項(xiàng)的情況就拋出異常。） 

一般情況，插入操作是rear（隊尾指針）加一后，在隊尾指針?biāo)傅奈恢锰幉迦胄碌臄?shù)據(jù)。但是，當(dāng)rear指針指向數(shù)組的頂端，即 maxSize-1位置的時候，在插入數(shù)據(jù)項(xiàng)之前，它必須回繞到數(shù)組的底端?；乩@操作把rear設(shè)置為-1，因此當(dāng)rear加1后，它等于0，是數(shù)組底端的下標(biāo)值，最后nItem加一。

Remove()方法運(yùn)行的前提條件是隊列不空，在調(diào)用這個方法之前應(yīng)該調(diào)用isEmpty()方法確保隊列不空，或者在remove()方法里加入這種出錯檢查的機(jī)制。

移除（remove）操作總是由front指針得到隊頭數(shù)據(jù)項(xiàng)的值，然后將front加一。但是，如果這樣做使front的值超過數(shù)組的頂端，front就必須繞回到數(shù)組下標(biāo)為0的位置上。作這種檢驗(yàn)的同時，先將返回值臨時存儲起來。最后nItem減一。

Peek()方法簡單易懂：它返回front指針?biāo)笖?shù)據(jù)項(xiàng)的值。有些隊列的實(shí)現(xiàn)也允許查看隊列隊尾數(shù)據(jù)項(xiàng)的值；比如這些方法可稱為peekFront()、peekRear()、或者只是front()和rear()。

isEmpty()、isFull()和size()方法的實(shí)現(xiàn)都依賴于nItems字段，它們分別返回nItems是否等于0，是否等于maxSize，或者返回它本身值。

在Queue類中包含數(shù)據(jù)項(xiàng)計數(shù)字段nItems會使insert()和remove()方法增加一點(diǎn)額外的操作，因?yàn)閕nsert()和 remove()方法必須分別遞增和遞減這個變量值。這可能算不上額外的開銷，但是如果處理大量的插入和移除操作，這就可能會影響性能了。

因?yàn)?，一些隊列的?shí)現(xiàn)不使用數(shù)據(jù)項(xiàng)計數(shù)的字段，而是通過front和rear來計算出隊列是否空或者滿以及數(shù)據(jù)項(xiàng)的個數(shù)。如果這樣做，isEmpty()、ifFull()和size()例程會相當(dāng)復(fù)雜，因?yàn)榫拖袂懊嬷v過的那樣，數(shù)據(jù)項(xiàng)的序列或者被折成兩段，或者是連續(xù)的一段。

而且，一個奇怪的問題出現(xiàn)了。當(dāng)隊列滿的時候，front和rear指針取一定的位置，但是當(dāng)隊列為空時，也可能呈現(xiàn)相同的位置關(guān)系。于是在同一時間，隊列似乎可能是滿的，也可能是空的。這個問題的解決方法是：讓數(shù)組容量比隊列數(shù)據(jù)項(xiàng)個數(shù)的最大值學(xué)要大一。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

最新評論