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

“隊(duì)列”這個(gè)單詞是英國(guó)人說(shuō)的“排”。在英國(guó)“排隊(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í)間來(lái)讀取它。利用隊(duì)列保證了鍵入內(nèi)容在處理時(shí)其順序不會(huì)改變。

隊(duì)列的基本操作

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

棧中的插入和移除數(shù)據(jù)項(xiàng)方法的命名是很標(biāo)準(zhǔn)，稱為push和pop。隊(duì)列的方法至今沒(méi)有標(biāo)準(zhǔn)化的命名?！安迦搿笨梢苑Q為put、add或 enque，而“刪除”可以叫delete、get或deque。插入數(shù)據(jù)項(xiàng)的隊(duì)尾，也可以叫作back、tail或end。而移除數(shù)據(jù)項(xiàng)的隊(duì)頭，也可以叫head。下面將使用insert、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)存中，只是它不能被訪問(wèn)了，因?yàn)殛?duì)頭指針已經(jīng)移到它的下一個(gè)位置了。

和棧中的情況不同，隊(duì)列中的數(shù)據(jù)項(xiàng)不總是從數(shù)組的0下標(biāo)處開(kāi)始。移除了一些數(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ì)可能和人們直觀察覺(jué)相反，因?yàn)槿藗冊(cè)谫I電影票排隊(duì)時(shí)，隊(duì)伍總是向前移動(dòng)的，當(dāng)前面的人買完票離開(kāi)隊(duì)伍后，其他人都向前移動(dòng)。計(jì)算機(jī)中在隊(duì)列里刪除一個(gè)數(shù)據(jù)項(xiàng)后，也可以將其他數(shù)據(jù)項(xiàng)都向前移動(dòng)，但這樣做的效率很差。相反，我們通過(guò)隊(duì)列中隊(duì)頭和隊(duì)尾指針的移動(dòng)保持所有數(shù)據(jù)項(xiàng)的位置不變。

這樣設(shè)計(jì)的問(wèn)題是隊(duì)尾指針很快就會(huì)移到數(shù)組的末端。雖然在數(shù)組的開(kāi)始部分有空的數(shù)據(jù)項(xiàng)單元，這是移除的數(shù)據(jù)項(xiàng)的位置，但是由于因?yàn)殛?duì)尾指針不能再向后移動(dòng)了，因此也不能再插入新的數(shù)據(jù)項(xiàng)，這該怎么辦？

環(huán)繞式處理

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

指針回繞的過(guò)程：在隊(duì)列中插入足夠多的數(shù)據(jù)項(xiàng)，使隊(duì)尾指針指向數(shù)組的未端。再刪除幾個(gè)數(shù)組前端的數(shù)據(jù)項(xiàng)?，F(xiàn)在插入一個(gè)新的數(shù)據(jù)項(xiàng)。就會(huì)看到隊(duì)尾指針從未端回繞到開(kāi)始處的位置。新的數(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類，它有insert()、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 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(隊(duì)頭)和rear(隊(duì)尾)字段，還有隊(duì)列中當(dāng)前數(shù)據(jù)項(xiàng)的個(gè)數(shù)：nItems。

Insert()方法運(yùn)行的前提條件是隊(duì)列不滿。在Main()中沒(méi)有顯示這個(gè)方法，不過(guò)通常應(yīng)該先調(diào)用isFull()方法并且返回false 后，才調(diào)用insert()方法。（更通用的做法是在insert()方法中加入檢查隊(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的值超過(guò)數(shù)組的頂端，front就必須繞回到數(shù)組下標(biāo)為0的位置上。作這種檢驗(yàn)的同時(shí)，先將返回值臨時(shí)存儲(chǔ)起來(lái)。最后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ì)使insert()和remove()方法增加一點(diǎn)額外的操作，因?yàn)閕nsert()和 remove()方法必須分別遞增和遞減這個(gè)變量值。這可能算不上額外的開(kāi)銷，但是如果處理大量的插入和移除操作，這就可能會(huì)影響性能了。

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

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

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

最新評(píng)論