[[347452]]

本文已收錄至我的 Github《算法圖解》系列：https://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)，并且在實現類中需要包含隊列的四個核心方法：入列、出列、查詢隊列是否為空、返回隊頭元素等，就可以稱為實現了一個自定義的隊列。