一文詳解「隊列」，手擼隊列的3種方法！

2020 年 10 月 21 日
筆記
core-java, 算法和數據結構

本文已收錄至我的 Github《算法圖解》系列：//github.com/vipstone/algorithm

前面我們介紹了棧（Stack），隊列和棧是比較像的一種數據結構。我們可以想像有很多輛汽車正在通過單行道的隧道，所有車輛不能插隊、不能掉頭，先進來的車也先出去，我們可以把這種特徵的數據結構稱之為隊列。

隊列也屬於邏輯結構，所謂的物理結構是指可以將數據存儲在物理空間中，比如數組和鏈表都屬於物理數據結構；而邏輯結構則是用於描述數據間的邏輯關係的，它可以由多種不同的物理結構來實現，比如隊列和棧都屬於邏輯結構。

隊列特性

隊列中的元素必須是先進先出（First In First Out，FIFO）的，它有兩個重要的方法：入隊（enqueue）和出隊（dequeue）。隊列的入口端叫隊尾（rear），出口端叫隊頭（front），如下圖所示：

手擼隊列

學習了隊列的基本知識之後，接下來我們將使用代碼來實現一個隊列。

首先我們先使用數組來實現一個隊列，它的結構如下圖所示：

1.自定義隊列—數組

public class MyQueue<E> {

    private Object[] queue; // 存儲容器
    private int head; // 頭部指針
    private int tail; // 尾部指針
    private int size; // 隊列實際存儲長度
    private int maxSize; // 最大容量

    public MyQueue() {
        // 無參構造函數，設置默認參數
        this.maxSize = 10;
        this.head = 0;
        this.tail = -1;
        this.size = 0;
        this.queue = new Object[this.maxSize];
    }

    public MyQueue(int initSize) {
        // 有參構造函數，設置參數
        this.maxSize = initSize;
        this.head = 0;
        this.tail = -1;
        this.size = 0;
        this.queue = new Object[this.maxSize];
    }

    /**
     * 查詢隊頭元素
     */
    public E peek() throws Exception {
        if (size == 0) {
            throw new Exception("隊列中暫無數據");
        }
        return (E) this.queue[this.head];
    }

    /**
     * 入列
     */
    public boolean offer(E e) throws Exception {
        if (tail >= (maxSize - 1)) {
            throw new Exception("添加失敗，隊列已滿");
        }
        this.queue[++tail] = e;
        size++;
        return true;
    }

    /**
     * 出列
     */
    public E poll() throws Exception {
        if (size == 0) {
            throw new Exception("刪除失敗，隊列為空");
        }
        size--;
        return (E) this.queue[head++];
    }

    /**
     * 代碼測試
     */
    public static void main(String[] args) throws Exception {
        MyQueue queue = new MyQueue();
        queue.offer("Hello");
        queue.offer("Java");
        System.out.println(queue.peek());
        queue.poll();
        System.out.println(queue.poll());
    }
}

以上代碼的執行結果如下：

Hello

Java

2.自定義隊列—鏈表

用鏈表實現隊列的數據結構如下圖所示：

實現代碼如下：

public class QueueByLinked {

    /**
     * 聲明鏈表節點
     */
    static class Node<E> {
        E item; // 當前的值

        Node<E> next; // 下一個節點

        Node(E e) {
            this.item = e;
        }
    }

    private Node firstNode; // 隊頭元素
    private Node lastNode; // 隊尾元素
    private int size; // 隊列實際存儲數量
    private int maxSize; // 隊列最大容量

    public QueueByLinked(int maxSize) {
        if (maxSize <= 0) throw new RuntimeException("隊列最大容量不能為空");
        // 默認初始化函數
        firstNode = lastNode = new Node(null);
        this.size = 0;
        this.maxSize = maxSize;
    }

    /**
     * 判斷隊列是否為空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 入列
     */
    public void offer(Object e) {
        // 最大值效驗
        if (maxSize <= size) throw new RuntimeException("隊列已滿");
        Node node = new Node(e);
        lastNode = lastNode.next = node; // 設置最後一個節點和倒數第二個節點的 next
        size++; // 隊列數量 +1
    }

    /**
     * 出列
     */
    public Node poll() {
        if (isEmpty()) throw new RuntimeException("隊列為空");
        size--; // 隊列數量 -1
        return firstNode = firstNode.next; // 設置並返回隊頭元素（第一個節點是 null，當前元素則為 Node.next）
    }
    
    /**
     * 查詢隊頭元素
     */
    public Node peek() {
        if (isEmpty()) throw new RuntimeException("隊列為空");
        return firstNode.next;  // 返回隊頭元素（第一個節點是 null，當前元素則為 Node.next）
    }

    /**
     * 代碼測試
     */
    public static void main(String[] args) {
        QueueByLinked queue = new QueueByLinked(10);
        queue.offer("Hello");
        queue.offer("JDK");
        queue.offer("Java");
        System.out.println(queue.poll().item);
        System.out.println(queue.poll().item);
        System.out.println(queue.poll().item);
    }
}

以上代碼的執行結果如下：

Hello

JDK

Java

3.擴展：使用 List 實現自定義隊列

除了以上兩種方式之外，我們還可以使用 Java 自身的數據結構來實現隊列，比如 List，我們這裡提供一個實現的思路（但並不建議在實際工作中使用），實現代碼如下：

import java.util.ArrayList;
import java.util.List;

/**
 * 自定義隊列（List方式）
 */
public class QueueByList<E> {

    private List value; // 隊列存儲容器

    public QueueByList() {
        // 初始化
        value = new ArrayList();
    }

    /**
     * 判斷隊列是否為空
     */
    public boolean isEmpty() {
        return value.size() == 0;
    }

    /**
     * 入列
     */
    public void offer(Object e) {
        value.add(e);
    }

    /**
     * 出列
     */
    public E poll() {
        if (isEmpty()) throw new RuntimeException("隊列為空");
        E item = (E) value.get(0);
        value.remove(0);
        return item;
    }

    /**
     * 查詢隊頭元素
     */
    public E peek() {
        if (isEmpty()) throw new RuntimeException("隊列為空");
        return (E) value.get(0);
    }

    /**
     * 代碼測試
     */
    public static void main(String[] args) {
        QueueByList queue = new QueueByList();
        queue.offer("Hello");
        queue.offer("JDK");
        queue.offer("Java");
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}

以上代碼的執行結果如下：

Hello

JDK

Java

隊列使用場景

隊列的常見使用場景有：

存儲多線程中等待排隊執行的任務；
存儲多線程公平鎖中等待執行任務的線程；
常見消息中間件的任務隊列等。

總結

通過以上三種隊列的實現方式我們可以看出，任意容器都是可以用來實現隊列（Queue）的，只要保證隊列的元素先進先出（FIFO），並且在實現類中需要包含隊列的四個核心方法：入列、出列、查詢隊列是否為空、返回隊頭元素等，就可以稱為實現了一個自定義的隊列。

最後，給大家留一個問題：隊列的類型都有哪些？歡迎評論區留言，我會在下篇文章中給出答案。歡迎關注我，每天和你一起進步一點點~

Tags: core-java 算法和數據結構