摘要：隊(duì)列的操作方式和棧類似，唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端進(jìn)行添加。

看過筆者前兩篇介紹的Java版數(shù)據(jù)結(jié)構(gòu)數(shù)組和棧的盆友，都給予了筆者一致的好評(píng)，在這里筆者感謝大家的認(rèn)可?。。?/p>

由于本章介紹的數(shù)據(jù)結(jié)構(gòu)是隊(duì)列，在隊(duì)列的實(shí)現(xiàn)上會(huì)基于前面寫的動(dòng)態(tài)數(shù)組來實(shí)現(xiàn)，而隊(duì)列又和棧不論是從特點(diǎn)上和操作上都有類似之處，所以在這里對(duì)這兩種數(shù)據(jù)結(jié)構(gòu)不了解的朋友，可以去看一下筆者前兩篇文章介紹的數(shù)據(jù)結(jié)構(gòu)數(shù)組和棧，這里筆者把鏈接貼出來（看過的盆友可以跳過此步驟...）

Java版-數(shù)據(jù)結(jié)構(gòu)-數(shù)組

Java版-數(shù)據(jù)結(jié)構(gòu)-棧

隊(duì)列是一種特殊的線性表，它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

隊(duì)列的操作方式和棧類似，唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端（rear）進(jìn)行添加。

隊(duì)列是一種線性結(jié)構(gòu)

只能從一端（隊(duì)尾）添加元素，從另一端（隊(duì)首）取出元素

先進(jìn)先出，F(xiàn)irst In First Out（FIFO）

之前在介紹棧的時(shí)候，通過示意圖來幫助大家了解什么是棧；這里，我仍采用示意圖形式向大家演示隊(duì)列常用的兩個(gè)操作：入隊(duì)操作和出隊(duì)操作。

隊(duì)列入隊(duì)操作

這里我們可以形象地想成我們到銀行辦理業(yè)務(wù)排隊(duì)的場景，現(xiàn)在A、B、C三個(gè)元素分別到銀行柜臺(tái)排成一條隊(duì)辦理業(yè)務(wù)（我們都是文明的孩紙，總不能插隊(duì)O(∩_∩)O哈?。来闻抨?duì)的元素是：A、B、C。

隊(duì)列出隊(duì)操作

當(dāng)元素A辦理完業(yè)務(wù)時(shí)，當(dāng)前是元素A先離開隊(duì)列，然后是元素B，最后是元素C

我們時(shí)刻要牢記隊(duì)列，入隊(duì)是從隊(duì)尾一端進(jìn)行入隊(duì)，出隊(duì)是從隊(duì)首一端進(jìn)行出隊(duì)，是一種：先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。

本文會(huì)介紹隊(duì)列的兩張實(shí)現(xiàn)方式，一種是數(shù)組隊(duì)列，另外一種是循環(huán)隊(duì)列，考慮篇幅長度原因，本篇我們暫時(shí)只介紹數(shù)組隊(duì)列，循環(huán)隊(duì)列放在下一篇介紹。

底層原理分析

現(xiàn)在我們聲明一個(gè)數(shù)組的長度（capacity=3），元素個(gè)數(shù)為（size=0）的int類型數(shù)組的空隊(duì)列，在這里，假設(shè)對(duì)隊(duì)列的隊(duì)首為數(shù)組的左側(cè)，隊(duì)尾為數(shù)組的右側(cè)，示意圖如下:

現(xiàn)在如果我們有四個(gè)元素：A、B、C、D要入隊(duì)

元素A入隊(duì)

元素A已經(jīng)入隊(duì)了，現(xiàn)在開始元素B入隊(duì)

元素A和元素B已經(jīng)入隊(duì)了，現(xiàn)在開始元素C入隊(duì)

元素A、B和C已經(jīng)分別入隊(duì)了，現(xiàn)在如果我們要開始元素D入隊(duì)，根據(jù)我們之前定義的動(dòng)態(tài)數(shù)組的特性，如果元素D進(jìn)行入隊(duì)操作，會(huì)發(fā)現(xiàn)此時(shí)我們的數(shù)組已經(jīng)滿了，這時(shí)候數(shù)組會(huì)自動(dòng)地擴(kuò)容（擴(kuò)容的原理：新建一個(gè)容量是原數(shù)組容量兩倍的數(shù)組，把原數(shù)組中的元素依次拷貝到新的數(shù)組中，最后引用指向新的數(shù)組）的原來的兩倍（具體擴(kuò)容多少，盆友可以自行設(shè)置）示意圖如下：

到這里我們已經(jīng)完成了元素:A、B、C、D的入隊(duì)操作了，現(xiàn)在我們來看一下，它們的出隊(duì)操作，根據(jù)隊(duì)列的特性，隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，之前入隊(duì)操作順序依次是：A->B->C->D，那么出隊(duì)操作順序仍然是：A->B->C->D

現(xiàn)在我們來看一下元素A和元素B出隊(duì)后的示意圖：

元素C和D的出隊(duì)原理和元素A出隊(duì)的原理一樣，直至全部出隊(duì)完成，變成空隊(duì)列

在元素出隊(duì)的過程中，相應(yīng)地也會(huì)進(jìn)行縮容操作，之前筆者這邊定義，當(dāng)數(shù)組中元素的個(gè)數(shù)（size）等于數(shù)組容量（capacity）的一半時(shí)，數(shù)組會(huì)進(jìn)行縮容操作，這也正是動(dòng)態(tài)數(shù)組的特點(diǎn)。

了解了數(shù)組隊(duì)列的底層原理之后，接下來我們用代碼來實(shí)現(xiàn)一下（建議盆友，在看之前，自己可以嘗試寫一下，然后在看，這樣印象可能會(huì)比較深刻O(∩_∩)O哈?。?/p>

隊(duì)列基本操作

向隊(duì)列中添加元素（入隊(duì)）

void enqueue(E e);

從隊(duì)列中取出元素（出隊(duì)）

E dequeue();

獲取隊(duì)首元素

E getFront();

獲取隊(duì)列中元素個(gè)數(shù)

int getSize();

判斷隊(duì)列是否為空

boolean isEmpty();

代碼實(shí)現(xiàn)

接口定義 ：Queue

public interface Queue {
    /**
     * 入隊(duì)
     *
     * @param e
     */
    void enqueue(E e);

    /**
     * 出隊(duì)
     *
     * @return
     */
    E dequeue();

    /**
     * 獲取隊(duì)首元素
     *
     * @return
     */
    E getFront();

    /**
     * 獲取隊(duì)列中元素的個(gè)數(shù)
     *
     * @return
     */
    int getSize();

    /**
     * 判斷隊(duì)列是否為空
     *
     * @return
     */
    boolean isEmpty();
}

DynamicArrayQueue 類實(shí)現(xiàn)接口 Queue

public class DynamicArrayQueue implements Queue {

    /**
     * 用數(shù)組存放隊(duì)列中元素的個(gè)數(shù)
     */
    private DynamicArray dynamicArray;

    /**
     * 指定容量，初始化隊(duì)列
     *
     * @param capacity
     */
    public DynamicArrayQueue(int capacity) {
        dynamicArray = new DynamicArray<>(capacity);
    }

    /**
     * 默認(rèn)容量，初始化隊(duì)列
     */
    public DynamicArrayQueue() {
        dynamicArray = new DynamicArray<>();
    }


    @Override
    public void enqueue(E e) {
        dynamicArray.addLast(e);
    }

    @Override
    public E dequeue() {
        return dynamicArray.removeFirst();
    }

    @Override
    public E getFront() {
        return dynamicArray.getFirst();
    }

    @Override
    public int getSize() {
        return dynamicArray.getSize();
    }

    @Override
    public boolean isEmpty() {
        return dynamicArray.isEmpty();
    }

    @Override
    public String toString() {
        return "DynamicArrayQueue{" +
                "【隊(duì)首】dynamicArray=" + dynamicArray + "}【隊(duì)尾】";
    }
}

測試類： DynamicArrayQueueTest

public class DynamicArrayQueueTest {
    @Test
    public void testArrayQueue() {
        // 指定容量（capacity=6）初始化隊(duì)列
        DynamicArrayQueue dynamicArrayQueue = new DynamicArrayQueue(3);
        System.out.println("初始隊(duì)列：" + dynamicArrayQueue);

        // 準(zhǔn)備入隊(duì)元素
        List enQueueElements = Arrays.asList("A", "B", "C");

        // 元素入隊(duì)
        enQueueElements.forEach(x -> dynamicArrayQueue.enqueue(x));
        System.out.println("元素A、B、C入隊(duì)：" + dynamicArrayQueue);

        // 此時(shí)如果又有一個(gè)元素D入隊(duì)，會(huì)發(fā)生擴(kuò)容操作 （size == capacity）進(jìn)行擴(kuò)容
        dynamicArrayQueue.enqueue("D");
        System.out.println("元素D入隊(duì)，發(fā)生擴(kuò)容：" + dynamicArrayQueue);


        // 元素A出隊(duì)，會(huì)發(fā)生縮容操作（size == capacity / 2）進(jìn)行縮容
        dynamicArrayQueue.dequeue();
        System.out.println("元素A出隊(duì)，發(fā)生縮容：" + dynamicArrayQueue);

        // 元素B出隊(duì)
        dynamicArrayQueue.dequeue();
        System.out.println("元素B出隊(duì)：" + dynamicArrayQueue);

    }
}

運(yùn)行結(jié)果

初始隊(duì)列：DynamicArrayQueue{【隊(duì)首】dynamicArray=DynamicArray{data=[null, null, null], size=0,capacity=3}}【隊(duì)尾】

元素A、B、C入隊(duì)：DynamicArrayQueue{【隊(duì)首】dynamicArray=DynamicArray{data=[A, B, C], size=3,capacity=3}}【隊(duì)尾】

元素D入隊(duì)，發(fā)生擴(kuò)容：DynamicArrayQueue{【隊(duì)首】dynamicArray=DynamicArray{data=[A, B, C, D, null, null], size=4,capacity=6}}【隊(duì)尾】

元素A出隊(duì)，發(fā)生縮容：DynamicArrayQueue{【隊(duì)首】dynamicArray=DynamicArray{data=[B, C, D], size=3,capacity=3}}【隊(duì)尾】

元素B出隊(duì)：DynamicArrayQueue{【隊(duì)首】dynamicArray=DynamicArray{data=[C, D, null], size=2,capacity=3}}【隊(duì)尾】

細(xì)心的盆友，會(huì)發(fā)現(xiàn)，因?yàn)殛?duì)列的底層是數(shù)組來實(shí)現(xiàn)的，隊(duì)列的出隊(duì)操作實(shí)際上就是：刪除數(shù)組中的第一個(gè)元素，后面的所有元素都要往前面挪一位；其實(shí)這樣性能是比較低下的，時(shí)間復(fù)雜度是O(n)級(jí)別的。
我們想如果元素進(jìn)行出隊(duì)操作后，能否不挪動(dòng)后面的元素，還能維持隊(duì)列的特性，這樣問題不就解決了嗎？盆友可以自行思考一下。

完整版代碼GitHub倉庫地址：Java版數(shù)據(jù)結(jié)構(gòu)-隊(duì)列（數(shù)組隊(duì)列） 歡迎大家【關(guān)注】和【Star】

本篇完成的數(shù)組隊(duì)列是基于之前【Java版-數(shù)據(jù)結(jié)構(gòu)-數(shù)組】動(dòng)態(tài)數(shù)組來實(shí)現(xiàn)的，下一篇筆者會(huì)給大家介紹用循環(huán)隊(duì)列來解決數(shù)組隊(duì)列帶來的性能問題。接下來，筆者還會(huì)一一的實(shí)現(xiàn)其它常見的數(shù)組結(jié)構(gòu)。

靜態(tài)數(shù)組

動(dòng)態(tài)數(shù)組

棧

數(shù)組隊(duì)列

循環(huán)隊(duì)列

鏈表

循環(huán)鏈表

二分搜索樹

優(yōu)先隊(duì)列

堆

線段樹

字典樹

AVL

紅黑樹

哈希表

....

持續(xù)更新中，歡迎大家關(guān)注公眾號(hào)：小白程序之路（whiteontheroad），第一時(shí)間獲取最新信息?。?！

筆者博客地址：http:www.gulj.cn