思維導圖

什么是隊列：

隊列，又稱為佇列（queue），是先進先出（FIFO, First-In-First-Out）的線性表。在具體應用中通常用鏈表或者數(shù)組來實現(xiàn)。隊列只允許在后端（稱為rear）進行插入操作，在前端（稱為front）進行刪除操作。

特點：

?隊列也是一種線性結構
?相比數(shù)組，隊列對應的操作是數(shù)組的子集
?只能從一端(隊尾)添加元素，只能從另一端(隊首)取出元素
?隊列是一種先進先出(FIFO,First In First Out)的數(shù)據(jù)結構

操作：

隊列數(shù)據(jù)結構使用兩種基本操作：進隊（enqueue）和出隊（dequeue）：
進隊：將數(shù)據(jù)從隊尾插入，隊列元素加1
出隊：將數(shù)據(jù)從隊首移出，隊列元素減1

圖示：

和日常排隊一樣，人們遵守規(guī)則，后來的人排最后，不能插隊，隊首的人辦好事情就出隊

種類：

順序隊列：在順序隊列中，出隊操作后又進行入隊操作，當隊尾指針已經(jīng)到數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，會有“假溢出”(如下圖)，解決假溢出的途徑----采用循環(huán)隊列。

假溢出

循環(huán)隊列：

臆想成環(huán)

在循環(huán)隊列中，空隊特征是front = rear, 隊滿時也會有front = rear; 判斷條件將出現(xiàn)二義性
解決方案有三種：

1. 加設標志位，讓刪除動作使其為1，插入動作使其為0， 則可識別當前front == rear;
2. 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）
3. 人為浪費一個單元，令隊滿特征為 front = (rear +1)%length(數(shù)組長度)---空閑單元法
   這里采用空閑單元法解決二義性問題。

代碼實現(xiàn)(循環(huán)隊列)：

接口定義：

public interface Queue<E> {
    int size();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

public class LoopQueue<E> implements Queue<E>{
    private E[] queue;
    private int front, rear;//隊首，隊尾指針
    private int size;//元素個數(shù)

    /**
     * 隊列容量為capaCity
     *因為要人為浪費一個單元，所以new的
     *時候+1
     * @param capacity
     */
    public LoopQueue(int capacity) {
        queue = (E[]) new Object[capacity + 1];
    }

    //隊列容量無參時初始為10
    public LoopQueue() {
        this(10);
    }

    //隊列是否為空
    public boolean isEmpty() {
        return front == rear;
    }

    //隊列元素個數(shù)
    public int size() {
        return size;
    }

    //隊列容量
    public int getCapacity() {
        return queue.length - 1;
    }

    //元素入隊尾
    public void enqueue(E e) {
        if ((rear + 1) % queue.length == front) {
            throw new IllegalArgumentException("Queue is full,enqueue is failed");
        }
        queue[rear] = e;
        rear = (rear + 1) % queue.length;
        size++;
    }

    //元素出隊首
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty,dequeue is failed");
        }
        E ret = queue[front];
        queue[front] = null;
        front = (front + 1) % queue.length;
        size--;
        return ret;
    }

    //查看隊首元素
    public E getFront() {
        return queue[front];
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue size = %d,capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for (int i = front; i != rear; i = (i + 1) % queue.length) {
            res.append(queue[i]);
            if ((i + 1) % queue.length != rear) {
                res.append(',');
            }
        }
        res.append("] rear");
        return res.toString();
    }
}

為了使該隊列能動態(tài)增減，加入以下優(yōu)化:

//隊列擴容
    public void resize(int newCapacity) {
        E[] newQueue = (E[]) new Object[newCapacity + 1];
        //將舊隊列隊首(可能不再數(shù)組首位置)元素放入新隊列第一個位置
        for (int i = 0; i < size; i++) {
            newQueue[i] = queue[(i + front) % queue.length];
        }
        queue = newQueue;
        front = 0;
        rear = size;
    }

enqueue優(yōu)化：

 //元素入隊尾
    public void enqueue(E e) {
        if ((rear + 1) % queue.length == front) {
            resize(2 * getCapacity());
        }
        queue[rear] = e;
        rear = (rear + 1) % queue.length;
        size++;
    }

dequeue優(yōu)化：

//元素出隊首
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty,dequeue is failed");
        }
        E ret = queue[front];
        queue[front] = null;
        front = (front + 1) % queue.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

測試結果：

部分

時間復雜度：

基于堆的優(yōu)先隊列：

請了解堆后再看后續(xù)代碼，在后續(xù)章節(jié)有說明(八)數(shù)據(jù)結構之堆

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
    private MaxHeap<E> maxHeap;

    public PriorityQueue() {
        maxHeap = new MaxHeap<>();
    }

    @Override
    public int size() {
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }
    
    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }
}