Java資料結構之Queue（隊列）

Queue（隊列）

Queue（隊列）是一種特殊的線性表，它隻允許在隊頭（front）進行删除操作（出隊），在隊尾（rear）進行插入操作（入隊），是一種操作受限制的線性表。即：FIFO（First In, First Out）。

從Queue的繼承關系圖可以看到，Queue接口實作了Collection接口，是以Queue具有Collection接口的所有特性。

但是一般來說，在操作Queue時，一般隻操作Queue的相關特性方法即可。否則何必使用Queue呢？

Queue常見的方法

// 入隊
boolean offer(E e);
// 出隊
E poll();
// 擷取隊頭元素（不出隊）
E peek();
// 判斷隊列是否為空
boolean isEmpty();
// 清空隊列
void clear();
// 擷取隊列的元素個數
int size();
           

自己實作一個Queue（連結清單實作）

public class MyLinkedQueue<E> {

    private List<E> queueList = new LinkedList<>();

    // 入隊
    public boolean offer(E e){
        return queueList.add(e);
    }
    // 出隊
    public E poll(){
        checkElementIndex();
        return queueList.remove(0);
    }
    // 擷取隊頭元素（不出隊）
    public E peek(){
        checkElementIndex();
        return queueList.get(0);
    }

    private void checkElementIndex(){
        if(isEmpty()){
            throw new IndexOutOfBoundsException("queue is empty.");
        }
    }

    // 判斷隊列是否為空
    public boolean isEmpty(){
        return queueList.isEmpty();
    }
    // 清空隊列
    public void clear(){
        queueList.clear();
    }
    // 擷取隊列的元素個數
    public int size(){
        return queueList.size();
    }

}
           

自己實作一個Queue(數組實作)

public class MyArrayQueue<E>{

    private Object[] objects;

    private int size = 0;

    private int front = 0;

    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayQueue(int capacity){
        if(capacity <= 0){
            throw new IllegalArgumentException("capacity must be greater than zero.");
        }
        objects = new Object[capacity];
    }

    public MyArrayQueue(){
        this(DEFAULT_CAPACITY);
    }

    // 入隊
    public boolean offer(E e){
        ensureCapacity();
        //因為數組從0開始，是以(front + size) % objects.length就是下一個要插入的位置，而不是+1
        int index = (front + size) % objects.length;
        objects[index] = e;
        size++;
        return true;
    }

    // 確定容量足夠插入元素
    private void ensureCapacity() {
        if(size == objects.length){
            // 2倍擴容
            Object[] newObjects = new Object[this.objects.length * 2];
            for (int i = 0; i < size; i++) {
                newObjects[i] = objects[front];
                moveFrontToNext();
            }
            objects = newObjects;
            // 擴容後，隊頭從開始
            front = 0;
        }
    }

    // 出隊
    public E poll(){
        checkElementIndex();
        E e = (E) objects[front];
        moveFrontToNext();
        size--;
        return e;
    }
    // 擷取隊頭元素（不出隊）
    public E peek(){
        checkElementIndex();
        return (E) objects[front];
    }

    private void checkElementIndex(){
        if(isEmpty()){
            throw new IndexOutOfBoundsException("queue is empty.");
        }
    }

    // 判斷隊列是否為空
    public boolean isEmpty(){
        return size == 0;
    }
    // 清空隊列
    public void clear(){
        for (int i = 0; i < size; i++) {
            objects[front] = null;
            moveFrontToNext();
        }
        size = 0;
    }
    // 擷取隊列的元素個數
    public int size(){
        return size;
    }
	// 将front移動到下一個位置。這個是數組實作Queue的核心算法。
    private void moveFrontToNext(){
        front = (front + 1) % objects.length;
    }
}
           

數組實作Queue為什麼底層不使用ArrayList，而是自己實作底層邏輯呢？因為ArrayList對于出隊操作，時間複雜度為O(n)，性能不友好。而上面的代碼通過循環數組的方式，通過front指定隊頭的位置，就能實作O(1)時間複雜度的出隊操作。

數組實作Queue的核心算法就是：front = (front + count) % objects.length。它通過取模底層數組長度，可以定位到入隊的位置，進而實作循環數組。如：

​ 假設數組長度為10，隊列的front為9（數組下标從0開始，是以front為9時是第10個元素位置），隊列長度為5，那麼其底層資料的位置分别為：

1	2	3	4	5	6	7	8	9
2	3	4	5	1

現在要插入值為6的元素，則6應該是插入到數組下标為4的位置。那麼其計算公式為：

front = (front + size) % objects.length = (9 + 5) % 10 = 4

1	2	3	4	5	6	7	8	9
2	3	4	5	6	1

Deque

Deque是Queue的子接口。Queue是一種單向的隊列形式，Deque則是雙向隊列，它支援從兩個端點方向檢索和插入元素。Deque既包含隊列性質，也包含了棧的性質，是以Deque既可以支援FIFO形式也可以支援LIFO形式。

Deque常見的方法

// 向隊列頭部插入一個元素,失敗時抛出異常
void push(E e);
// 向隊列頭部插入一個元素,失敗時抛出異常
void addFirst(E e);
// 向隊列尾部插入一個元素,失敗時抛出異常
void addLast(E e);
// 向隊列頭部加入一個元素,失敗時傳回false
boolean offerFirst(E e);
// 向隊列尾部加入一個元素,失敗時傳回false
boolean offerLast(E e);

// 擷取隊列頭部元素,隊列為空時抛出異常
E getFirst();
// 擷取隊列尾部元素,隊列為空時抛出異常
E getLast();
// 擷取隊列頭部元素,隊列為空時傳回null
E peekFirst();
// 擷取隊列尾部元素,隊列為空時傳回null
E peekLast();
// 删除第一次出現的指定元素,不存在時傳回false
boolean removeFirstOccurrence(Object o);
// 删除最後一次出現的指定元素,不存在時傳回false
boolean removeLastOccurrence(Object o);
// 彈出隊列頭部元素,隊列為空時抛出異常
E pop();
// 彈出隊列頭部元素,隊列為空時抛出異常
E removeFirst();
// 彈出隊列頭部元素,隊列為空時傳回null
E pollFirst();
// 彈出隊列尾部元素,隊列為空時傳回null
E pollLast();
           

從上面的方法可以看出，Deque在Queue的方法上新添了對隊列頭尾元素的操作。

需要注意push = addFirst，pop = removeFirst，隻是使用了不同的方法名展現隊清單示棧結構時的特點。

Deque的實作

同Queue一樣，Deque的實作也可以劃分成通用實作和并發實作。

通用實作主要有兩個實作類ArrayDeque和LinkedList：

ArrayDeque是個可變數組，它是在Java 6之後新添加的，而LinkedList是一種連結清單結構的list。LinkedList要比ArrayDeque更加靈活，因為它也實作了List接口的所有操作，并且可以插入null元素，這在ArrayDeque中是不允許的。

從效率來看，ArrayDeque要比LinkedList在兩端增删元素上更為高效，因為沒有在節點建立删除上的開銷。最适合使用LinkedList的情況是疊代隊列時删除目前疊代的元素。

總體ArrayDeque要比LinkedList更優越，在大隊列的測試上有3倍與LinkedList的性能，最好的是給ArrayDeque一個較大的初始化大小，以避免底層數組擴容時資料拷貝的開銷。

LinkedBlockingDeque是Deque的并發實作,在隊列為空的時候，它的takeFirst,takeLast會阻塞等待隊列處于可用狀态。

參考：https://www.cnblogs.com/bushi/p/6681543.html