[[347452]]

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

前面我們介紹了棧(Stack)，隊(duì)列和棧是比較像的一種數(shù)據(jù)結(jié)構(gòu)。我們可以想象有很多輛汽車正在通過單行道的隧道，所有車輛不能插隊(duì)、不能掉頭，先進(jìn)來的車也先出去，我們可以把這種特征的數(shù)據(jù)結(jié)構(gòu)稱之為隊(duì)列。

隊(duì)列也屬于邏輯結(jié)構(gòu)，所謂的物理結(jié)構(gòu)是指可以將數(shù)據(jù)存儲在物理空間中，比如數(shù)組和鏈表都屬于物理數(shù)據(jù)結(jié)構(gòu);而邏輯結(jié)構(gòu)則是用于描述數(shù)據(jù)間的邏輯關(guān)系的，它可以由多種不同的物理結(jié)構(gòu)來實(shí)現(xiàn)，比如隊(duì)列和棧都屬于邏輯結(jié)構(gòu)。

隊(duì)列特性

隊(duì)列中的元素必須是先進(jìn)先出(First In First Out，F(xiàn)IFO)的，它有兩個重要的方法：入隊(duì)(enqueue)和出隊(duì)(dequeue)。隊(duì)列的入口端叫隊(duì)尾(rear)，出口端叫隊(duì)頭(front)，如下圖所示：

手?jǐn)]隊(duì)列

學(xué)習(xí)了隊(duì)列的基本知識之后，接下來我們將使用代碼來實(shí)現(xiàn)一個隊(duì)列。

首先我們先使用數(shù)組來實(shí)現(xiàn)一個隊(duì)列，它的結(jié)構(gòu)如下圖所示：

1.自定義隊(duì)列—數(shù)組

public class MyQueue<E> { 
 
    private Object[] queue; // 存儲容器 
    private int head; // 頭部指針 
    private int tail; // 尾部指針 
    private int size; // 隊(duì)列實(shí)際存儲長度 
    private int maxSize; // 最大容量 
 
    public MyQueue() { 
        // 無參構(gòu)造函數(shù)，設(shè)置默認(rèn)參數(shù) 
        this.maxSize = 10; 
        this.head = 0; 
        this.tail = -1; 
        this.size = 0; 
        this.queue = new Object[this.maxSize]; 
    } 
 
    public MyQueue(int initSize) { 
        // 有參構(gòu)造函數(shù)，設(shè)置參數(shù) 
        this.maxSize = initSize; 
        this.head = 0; 
        this.tail = -1; 
        this.size = 0; 
        this.queue = new Object[this.maxSize]; 
    } 
 
    /** 
     * 查詢隊(duì)頭元素 
     */ 
    public E peek() throws Exception { 
        if (size == 0) { 
            throw new Exception("隊(duì)列中暫無數(shù)據(jù)"); 
        } 
        return (E) this.queue[this.head]; 
    } 
 
    /** 
     * 入列 
     */ 
    public boolean offer(E e) throws Exception { 
        if (tail >= (maxSize - 1)) { 
            throw new Exception("添加失敗，隊(duì)列已滿"); 
        } 
        this.queue[++tail] = e; 
        size++; 
        return true; 
    } 
 
    /** 
     * 出列 
     */ 
    public E poll() throws Exception { 
        if (size == 0) { 
            throw new Exception("刪除失敗，隊(duì)列為空"); 
        } 
        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()); 
    } 
} 

以上代碼的執(zhí)行結(jié)果如下：

• Hello
• Java

2.自定義隊(duì)列—鏈表

用鏈表實(shí)現(xiàn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)如下圖所示：

實(shí)現(xiàn)代碼如下：

public class QueueByLinked { 
 
    /** 
     * 聲明鏈表節(jié)點(diǎn) 
     */ 
    static class Node<E> { 
        E item; // 當(dāng)前的值 
 
        Node<E> next; // 下一個節(jié)點(diǎn) 
 
        Node(E e) { 
            this.item = e; 
        } 
    } 
 
    private Node firstNode; // 隊(duì)頭元素 
    private Node lastNode; // 隊(duì)尾元素 
    private int size; // 隊(duì)列實(shí)際存儲數(shù)量 
    private int maxSize; // 隊(duì)列最大容量 
 
    public QueueByLinked(int maxSize) { 
        if (maxSize <= 0) throw new RuntimeException("隊(duì)列最大容量不能為空"); 
        // 默認(rèn)初始化函數(shù) 
        firstNode = lastNode = new Node(null); 
        this.size = 0; 
        this.maxSize = maxSize; 
    } 
 
    /** 
     * 判斷隊(duì)列是否為空 
     */ 
    public boolean isEmpty() { 
        return size == 0; 
    } 
 
    /** 
     * 入列 
     */ 
    public void offer(Object e) { 
        // 最大值效驗(yàn) 
        if (maxSize <= size) throw new RuntimeException("隊(duì)列已滿"); 
        Node node = new Node(e); 
        lastNode = lastNode.next = node; // 設(shè)置最后一個節(jié)點(diǎn)和倒數(shù)第二個節(jié)點(diǎn)的 next 
        size++; // 隊(duì)列數(shù)量 +1 
    } 
 
    /** 
     * 出列 
     */ 
    public Node poll() { 
        if (isEmpty()) throw new RuntimeException("隊(duì)列為空"); 
        size--; // 隊(duì)列數(shù)量 -1 
        return firstNode = firstNode.next; // 設(shè)置并返回隊(duì)頭元素（第一個節(jié)點(diǎn)是 null，當(dāng)前元素則為 Node.next） 
    } 
     
    /** 
     * 查詢隊(duì)頭元素 
     */ 
    public Node peek() { 
        if (isEmpty()) throw new RuntimeException("隊(duì)列為空"); 
        return firstNode.next;  // 返回隊(duì)頭元素（第一個節(jié)點(diǎn)是 null，當(dāng)前元素則為 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); 
    } 
} 

以上代碼的執(zhí)行結(jié)果如下：

• Hello
• JDK
• Java

3.擴(kuò)展：使用 List 實(shí)現(xiàn)自定義隊(duì)列

除了以上兩種方式之外，我們還可以使用 Java 自身的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)隊(duì)列，比如 List，我們這里提供一個實(shí)現(xiàn)的思路(但并不建議在實(shí)際工作中使用)，實(shí)現(xiàn)代碼如下：

import java.util.ArrayList; 
import java.util.List; 
 
/** 
 * 自定義隊(duì)列（List方式） 
 */ 
public class QueueByList<E> { 
 
    private List value; // 隊(duì)列存儲容器 
 
    public QueueByList() { 
        // 初始化 
        value = new ArrayList(); 
    } 
 
    /** 
     * 判斷隊(duì)列是否為空 
     */ 
    public boolean isEmpty() { 
        return value.size() == 0; 
    } 
 
    /** 
     * 入列 
     */ 
    public void offer(Object e) { 
        value.add(e); 
    } 
 
    /** 
     * 出列 
     */ 
    public E poll() { 
        if (isEmpty()) throw new RuntimeException("隊(duì)列為空"); 
        E item = (E) value.get(0); 
        value.remove(0); 
        return item; 
    } 
 
    /** 
     * 查詢隊(duì)頭元素 
     */ 
    public E peek() { 
        if (isEmpty()) throw new RuntimeException("隊(duì)列為空"); 
        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()); 
    } 
} 

以上代碼的執(zhí)行結(jié)果如下：

• Hello
• JDK
• Java

隊(duì)列使用場景

隊(duì)列的常見使用場景有：

• 存儲多線程中等待排隊(duì)執(zhí)行的任務(wù);
• 存儲多線程公平鎖中等待執(zhí)行任務(wù)的線程;
• 常見消息中間件的任務(wù)隊(duì)列等。

總結(jié)

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