摘要：前言數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。隊(duì)列和棧類似，也是一個(gè)遵循特殊規(guī)則約束的數(shù)據(jù)結(jié)構(gòu)。將沒有元素的隊(duì)列稱之為空隊(duì)，往隊(duì)列中插入元素的過程稱之為入隊(duì)，從隊(duì)列中移除元素的過程稱之為出隊(duì)。

聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。

前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列（queue）的概念、存儲(chǔ)結(jié)構(gòu)、隊(duì)列的特點(diǎn)，文末給出java實(shí)現(xiàn)循環(huán)隊(duì)列的代碼實(shí)現(xiàn)供讀者參考學(xué)習(xí)。

隊(duì)列正如其名，隊(duì)列就像一支隊(duì)伍，有隊(duì)首(head)和隊(duì)尾(tail)以及隊(duì)列長(zhǎng)度。隊(duì)列和棧類似，也是一個(gè)遵循特殊規(guī)則約束的數(shù)據(jù)結(jié)構(gòu)。在上一篇文章java數(shù)據(jù)結(jié)構(gòu)與算法——棧中介紹棧是一個(gè)后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，隊(duì)列正好與之相反，是一個(gè)先進(jìn)先出（FIFO，F(xiàn)irst In First Out），例如我們?nèi)タ系禄抨?duì)，先排上隊(duì)的肯定先拿到餐出隊(duì)，這和我們對(duì)列認(rèn)知是一致的。

上面說到隊(duì)列是一個(gè)遵循特殊規(guī)則的數(shù)據(jù)結(jié)構(gòu)，除了先進(jìn)先出，隊(duì)列的插入只能從隊(duì)列的一端操作，我們稱這端為隊(duì)尾；對(duì)應(yīng)的，移除只能從另一端出來，我們稱之為隊(duì)首。

將沒有元素的隊(duì)列稱之為空隊(duì)，往隊(duì)列中插入元素的過程稱之為入隊(duì)，從隊(duì)列中移除元素的過程稱之為出隊(duì)。

一般而言，隊(duì)列的實(shí)現(xiàn)有兩種方式：數(shù)組實(shí)現(xiàn)和鏈表實(shí)現(xiàn)，本篇中采取數(shù)組實(shí)現(xiàn)，鏈表實(shí)現(xiàn)在后續(xù)補(bǔ)充。用數(shù)組實(shí)現(xiàn)的隊(duì)列有兩種：一種是順序隊(duì)列，另一種是循環(huán)隊(duì)列，這兩種隊(duì)列的存儲(chǔ)結(jié)構(gòu)和特點(diǎn)下文會(huì)逐一介紹。

說明：用數(shù)組實(shí)現(xiàn)隊(duì)列，若隊(duì)列中出現(xiàn)隊(duì)滿的情況（因?yàn)樵诼暶麝?duì)列時(shí)，一般會(huì)指定一個(gè)初始容量），此時(shí)如果有新元素入隊(duì)，但沒有位置怎么辦？要么丟棄，要么等待。

以下采用數(shù)組實(shí)現(xiàn)，初始化一個(gè)隊(duì)列長(zhǎng)度為6，隊(duì)列有兩個(gè)標(biāo)記，一個(gè)隊(duì)頭的位置head，一個(gè)隊(duì)尾的位置tail，初始都指向數(shù)組下標(biāo)為0的位置，如圖所示：

在插入元素時(shí)，tail標(biāo)記+1，比如入隊(duì)三個(gè)元素，依次為A，B，C（注意是有順序的），則當(dāng)前隊(duì)列存儲(chǔ)情況如圖：
當(dāng)前head為0，tail為3，接下來進(jìn)行出隊(duì)操作，此處將A元素出隊(duì)，則head+1，此時(shí)隊(duì)列的存儲(chǔ)情況如圖：

根據(jù)上面的圖例，我們可以通過tail-head獲得隊(duì)列中元素的個(gè)數(shù)。當(dāng)tail==head時(shí)，此時(shí)隊(duì)列為空，而當(dāng)tail等于數(shù)組長(zhǎng)度時(shí)，此時(shí)將無法出入元素，那么隊(duì)列是否已經(jīng)滿呢？未必！因?yàn)閔ead和tail在入隊(duì)和出隊(duì)操作中只增不減，因此head和tail都會(huì)最終指向隊(duì)列之外的存儲(chǔ)位置，此時(shí)雖然數(shù)組為空，但也無法將元素入隊(duì)。

上溢： 當(dāng)隊(duì)列中無法插入元素時(shí)，稱之為上溢；
假上溢： 在順序隊(duì)列中，數(shù)組還有空間（不一定全空）但無法入隊(duì)稱之為假上溢；
真上溢： 如果head為0，tail指向數(shù)組之外，即數(shù)組真滿了，稱之為真上溢；
下溢： 如果空隊(duì)中執(zhí)行出隊(duì)操作，此時(shí)隊(duì)列中無元素，稱之為下溢

如何解決“假上溢”的問題呢？此時(shí)引入循環(huán)隊(duì)列。出現(xiàn)假上溢時(shí)，此時(shí)數(shù)組還有空閑的位置，將tail從新指向數(shù)組的0索引處即可，如圖所示：

如果繼續(xù)入隊(duì)E和F，則隊(duì)列的存儲(chǔ)結(jié)構(gòu)如圖：
通常而言，在對(duì)head和tail加1時(shí)，為了方便采用對(duì)數(shù)組長(zhǎng)度取余操作。另外由于順序隊(duì)列存在“假上溢”的現(xiàn)象，所以一般用循環(huán)隊(duì)列實(shí)現(xiàn)。

在采用循環(huán)隊(duì)列實(shí)現(xiàn)的過程中，當(dāng)隊(duì)列滿隊(duì)時(shí)，tail等于head，而當(dāng)隊(duì)列空時(shí)，tail也等于head，為了區(qū)分兩種狀態(tài)，一般規(guī)定循環(huán)隊(duì)列的長(zhǎng)度為數(shù)組長(zhǎng)度-1，即有一個(gè)位置不放元素，此時(shí)head==tail時(shí)為空隊(duì)，而當(dāng)head==(tail+1)%數(shù)組長(zhǎng)度，說明對(duì)滿。

下面是循環(huán)隊(duì)列的java代碼，采用數(shù)組方式實(shí)現(xiàn)：

public class ArrayQueue {
    private final Object[] queue;  //聲明一個(gè)數(shù)組
    private int head;
    private int tail;
    
    /**
     * 初始化隊(duì)列
     * @param capacity 隊(duì)列長(zhǎng)度
     */
    public ArrayQueue(int capacity){
        this.queue = new Object[capacity];
    }
    
    /**
     * 入隊(duì)
     * @param o 入隊(duì)元素
     * @return 入隊(duì)成功與否
     */
    public boolean put(Object o){
        if(head == (tail+1)%queue.length){
            //說明隊(duì)滿
            return false;
        }
        queue[tail] = o;
        tail = (tail+1)%queue.length;  //tail標(biāo)記后移一位
        return true;
    }
    
    /**
     * 返回隊(duì)首元素，但不出隊(duì)
     * @return
     */
    public Object peak() {
        if(head==tail){
            //隊(duì)空
            return null;
        }
        return queue[head];        
    }
    
    /**
     * 出隊(duì)
     * @return 出隊(duì)元素
     */
    public Object pull(){
        if(head==tail){
            return null;
        }
        Object item = queue[head];
        queue[head] = null;
        return item;
    }
    
    /**
     * 判斷是否為空
     * @return
     */
    public boolean isEmpty(){
        return head == tail;
    }
    
    /**
     * 判斷是否為滿
     * @return
     */
    public boolean isFull(){
        return head == (tail+1)%queue.length;
    }
    
    /**
     * 獲取隊(duì)列中的元素個(gè)數(shù)
     * @return
     */
    public int getsize(){
        if(tail>=head){
            return tail-head;
        }else{
            return (tail+queue.length)-head;
        }
    }    
}

下面是隊(duì)列的測(cè)試代碼

public class ArrayQueueTest {
    public static void main(String[] args) {
        ArrayQueue q = new ArrayQueue(4);  //初始化隊(duì)列長(zhǎng)度為3，因?yàn)檠h(huán)隊(duì)列有一個(gè)不放元素
        System.out.println(q.put("張三"));  //入隊(duì)，true
        System.out.println(q.put("李四"));  //入隊(duì)，true 
        System.out.println(q.put("趙五"));  //入隊(duì)，true
        System.out.println(q.put("老王"));  //隊(duì)滿，false
        
        System.out.println(q.isFull());  //隊(duì)滿 true
        System.out.println(q.getsize()); //3，隊(duì)列中有3個(gè)元素
        
        System.out.println(q.peak());  //返回“張三”  不出隊(duì)
        System.out.println(q.pull());  //返回“張三”  
        System.out.println(q.pull());  //返回“李四”  
        System.out.println(q.pull());  //返回“趙五”  
        
        System.out.println(q.isEmpty());  //true 空隊(duì)
    }
}

隊(duì)列先入先出的特點(diǎn)，使得其應(yīng)用非常廣泛，比如隊(duì)列作為“緩沖區(qū)”，可以解決計(jì)算機(jī)和外設(shè)速度不匹配的問題，F(xiàn)IFO的特點(diǎn)保證了數(shù)據(jù)傳輸?shù)捻樞?；除此之外?duì)列在后面樹的層序遍歷中也有應(yīng)用，F(xiàn)IFO的特點(diǎn)保證了處理順序不會(huì)出錯(cuò)。