基礎(chǔ)知識

隊列是一種特殊的線性表，他的特殊性在于我們只能操作他頭部和尾部的元素，中間的元素我們操作不了，我們只能在他的頭部進(jìn)行刪除，尾部進(jìn)行添加。就像大家排隊到銀行取錢一樣，先來的肯定要排到前面，后來的只能排在隊尾，所有元素都要遵守這個操作，沒有VIP會員，所以走后門插隊的現(xiàn)象是不可能存在的，他是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。我們來看一下隊列的數(shù)據(jù)結(jié)構(gòu)是什么樣的

1，一般隊列

image.png

他只能從左邊進(jìn)，右邊出，隊列實現(xiàn)方式一般有兩種，一種是基于數(shù)組的，還一種是基于鏈表的，如果基于鏈表的倒還好說，因為鏈表的長度是隨時都可以變的，這個實現(xiàn)起來比較簡單。如果是基于數(shù)組的，就會稍微有點不同，因為數(shù)組的大小在初始化的時候就已經(jīng)固定了，我們來看一下基于數(shù)組的實現(xiàn)，假如我們初始化一個長度是10的隊列

在這里插入圖片描述

front指向的是隊列的頭，tail指向的是隊列尾的下一個存儲空間，最初始的時候front=0，tail=0，每添加一個元素tail就加1，每移除一個元素front就加1，但是這樣會有一個問題，如果一個元素不停的加入隊列，然后再不停的從隊列中移除，會導(dǎo)致tail和front越來越大，最后會導(dǎo)致隊列無法再加入數(shù)據(jù)了，但實際上隊列前面全部都是空的，這導(dǎo)致空間的極大浪費。我們自己來寫一個簡單的隊列看一下

public class MyQueue<E> {

    private final Object[] data;
    private final int maxSize;
    private int size;
    private int front = 0;
    private int tail = 0;

    public MyQueue(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("隊列容量必須大于0 : " + maxSize);
        }
        this.maxSize = maxSize;
        data = new Object[this.maxSize];
    }

    public void add(E e) {
        if (isFull()) {//這地方可以擴(kuò)容也可以拋異常，為了方便這里我們就不在擴(kuò)容了。
            throw new IllegalStateException("隊列已經(jīng)滿了，無法再加入……");
        }
        data[tail++] = e;
        size++;
    }

    public E remove() {
        if (isEmpty()) {
            throw new IllegalStateException("隊列是空的，無法移除……");
        }
        E t = (E) data[front];
        data[front++] = null;
        size--;
        return t;
    }

    //隊列頭和隊列尾指向同一空間的時候，并且沒到隊尾，表示隊列是空的
    public boolean isEmpty() {
        return front == tail && !isFull();
    }

    public boolean isFull() {//最后一個位置是不存儲數(shù)據(jù)的
        return tail == maxSize - 1;
    }

    public int getSize() {
        return size;
    }
}

代碼非常簡單，當(dāng)然隊列的實現(xiàn)不一定是這一種方式，比如我們可以讓tail指向隊尾的元素，或者以鏈表的形式來實現(xiàn)都是可以的，不同的實現(xiàn)方式會導(dǎo)致上面的方法有所不同。我們來測試一下

public static void main(String[] args) {
    MyQueue myQueue = new MyQueue(10);
    System.out.println("isEmpty()=" + myQueue.isEmpty());
    System.out.println("isFull()=" + myQueue.isFull());
    System.out.println("getSize()=" + myQueue.getSize());
    for (int i = 0; i < 9; i++) {
        myQueue.add(i * 100);
        myQueue.remove();
    }
    System.out.println("----------------------------");
    System.out.println("isEmpty()=" + myQueue.isEmpty());
    System.out.println("isFull()=" + myQueue.isFull());
    System.out.println("getSize()=" + myQueue.getSize());
}

看一下打印的結(jié)果

    isEmpty()=true
    isFull()=false
    getSize()=0
    ----------------------------
    isEmpty()=false
    isFull()=true
    getSize()=0

我們添加了9次，然后又移除了9次，結(jié)果隊列竟然滿了，如果我們再添加一次的話肯定會拋異常，但實際上隊列的size是0，還是空的，也就是說數(shù)組的每個位置只能使用一次，這樣就造成了極大的浪費。那么前面使用過的空間還能不能再次利用了呢，實際上是可以的，我們可以把隊列看成是環(huán)形的，當(dāng)tail到達(dá)數(shù)組末尾的時候，如果數(shù)組的前面有空位子，我們可以讓tail從頭開始，這個時候一個新的隊列就產(chǎn)生了，那就是雙端隊列。

2，雙端隊列

雙端隊列也是有兩個指針，front指向隊首，tail指向隊尾的下一個存儲單元，并且雙端隊列的隊首和隊尾都可以添加和刪除元素，我們來看一下圖

在這里插入圖片描述

這樣空間就可以循環(huán)利用了，不會造成浪費，我們來看下代碼

public class MyQueue<E> {

    //存儲的元素
    private Object[] data;

    //指向隊列頭，這個頭并不是數(shù)組的第0個元素，如果這樣
    // front就沒有意義了，這個從下面的addFirst(E e)方
    // 法也可以看出，如果當(dāng)front等于0的時候，在添加到
    // first，那么會添加到數(shù)組的末尾，并且front也指向
    // 數(shù)組的末尾
    private int front;

    //指向隊列尾的下一個空間，可以這樣理解，front指向
    // 的是第一個元素，tail指向的是最后一個元素的下一
    // 個，指的是空的。
    private int tail;

    public MyQueue(int numElements) {
        data = new Object[numElements];
    }

    //空間擴(kuò)容，我們這里選擇擴(kuò)大一倍，當(dāng)然也可以選擇其
    // 他值，僅僅當(dāng)滿的時候才能觸發(fā)擴(kuò)容， 這時候front
    // 和tail都會指向同一個元素
    private void doubleCapacity() {
        int p = front;
        int n = data.length;//數(shù)組的長度
        //關(guān)鍵是r不好理解，舉個例子，在數(shù)組中，front
        // 不一定是之前0位置的，他可以指向其他位置，
        // 比如原來空間大小為16，front為13，也就是第
        // 14個元素（數(shù)組是從0開始的），那么r就是16-13=3，
        // 也就是從front往后還有多少元素，待會copy的時候
        // 也是先從最后的r個元素開始
        int r = n - p;
        Object[] a = new Object[n << 1];//擴(kuò)大一倍
        System.arraycopy(data, p, a, 0, r);//先copy后面的r個
        System.arraycopy(data, 0, a, r, p);//再copy前面的p個
        data = a;
        //重新調(diào)整front和tail的值
        front = 0;
        tail = n;
    }

    public void addFirst(E e) {
        //添加到front的前面，所以front-1
        front = (front - 1 + data.length) % data.length;
        data[front] = e;
        if (front == tail)//判斷是否滿了
            doubleCapacity();
    }

    public void addLast(E e) {
        //添加到最后一個，這個方法和addFirst有很明顯的不同，
        // addFirst是添加的時候就要計算front的位置，而addLast
        // 方法是存值之后在計算tail的，/因為tail位置是沒有
        // 存值的，他表示的末端元素的下一個，是空，所以存值之后
        //要計算tail的值
        data[tail] = e;
        tail = (tail + 1) % data.length;
        if (tail == front)//判斷是否滿
            doubleCapacity();
    }

    public E removeFirst() {//刪除第一個
        if (isEmpty())
            throw new IllegalStateException("隊列是空的，無法移除……");
        E result = (E) data[front];
        data[front] = null;
        // 刪除第一個，這里的所有第一我們都認(rèn)為是front所指的，
        // 不是數(shù)組的0位置，然后在計算front的值
        front = (front + 1) % data.length;
        return result;
    }

    public E removeLast() {//刪除最后一個
        if (isEmpty())
            throw new IllegalStateException("隊列是空的，無法移除……");
        tail = (tail - 1 + data.length) % data.length;
        E result = (E) data[tail];
        data[tail] = null;
        return result;
    }

    public E peekFirst() {
        if (isEmpty())
            throw new IllegalStateException("隊列是空的，無法獲取……");
        return (E) data[front];
    }

    public E peekLast() {
        if (isEmpty())
            throw new IllegalStateException("隊列是空的，無法獲取……");
        return (E) data[(tail - 1 + data.length) % data.length];
    }

    public int size() {//元素的size
        return (tail - front + data.length) % data.length;
    }

    //是否為空，在上面添加元素的時候也可能front==tail，當(dāng)添加
    // 元素之后front==tail的時候就認(rèn)為是滿了，然后擴(kuò)容，重新
    // 調(diào)整front和tail的值,所以擴(kuò)容之后front就不可能等于tail。
    //如果沒有觸發(fā)上面添加元素的時候front等于tail我們就認(rèn)為他是空的。
    public boolean isEmpty() {
        return front == tail;
    }
}

代碼中都有詳細(xì)的注釋，就不在過多介紹。