【Java/数据结构】队列（Quque）

本博客将介绍队列的相关知识，包括基于数组的普通队列，基于链表的普通队列，基于数组的双端队列，基于链表的双端队列，但不包括优先级队列（PriorityQueue），此数据结构将单独发一篇博客，那么，让我们从基础的队列开始吧！

一.队列概述

1.队列概述

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

可以把他想象成排队买东西，先排队先买。

特性：FIFO（First In First Out），先进先出。

Quque在Java集合框架中的位置如下：

虽然看起来很单一，但实际上队列的实现相当丰富。

二.队列的实现

我们要模拟实现是基于数组的循环队列、基于链表的单端队列、基于数组的双端队列、基于链表的双端队列。

1.源码简介

先看看源码（可以直接看模拟实现）：
首先看看Queue接口：

继承自collection接口，提供了一些队列基本方法，

还有继承自Queue的Deque接口：

接下来看看AbstractQueue：

接下来是基本实现类：

有ArrayQueue：

LinkedList，没错，LinkedList也可以被当成队列来使用：

LinkedList是继承自Deque的，除此之外，还有像PriorityQueue（优先级队列）、BlockingDeque（双端阻塞队列）等我们暂且不讨论。

2.基于数组的循环队列

（1）原理

为什么会加上循环特性呢？

原因是普通非循环队列重复使用会造成严重的内存浪费，而加上循环特性后，就可以避免这一情况了，请看如下情况：

1、2出队，5、6、7、8入队后：

由于使用的是逻辑删除，所以1、2所占内存其实还在，反复增删后（内存不足自动扩容），就会变成一个有效数据极少，所占内存极大的队列，与是，改进成循环队列：

还是这张图，但是当我们进行4、5出队，9、10、11、12入队的操作后，就开始循环存储：

有效区域为6~12，当继续添加元素13~20后，判断队尾会追上队头时，容量不足，于是会先把所有数据复制到内存扩大的新数组，并从0下标按顺序排列后才会继续添加元素：

先复制：

再添加元素： 

通常我们会用size与capacity来记录容量是否满出，即size>=capacity时自动扩容。

在设计时，要特别注意%处的操作。

（2）基本结构

public class MyQueue {
    private int[] queue;   // 存储元素的数组
    private int front;     // 队头指针
    private int size;      // 当前元素数量
    private int capacity;  // 当前队列容量
    private static final int DEFAULT_CAPACITY = 10;
   
    // 初始化队列
    public MyQueue() {
        this.capacity = DEFAULT_CAPACITY;
        this.queue = new int[capacity];
        this.front = 0;
        this.size = 0;
    }

    ......

说明：队尾指针为 rear = (front + size) % capacity ，可以通过计算求得，不需要定义一个。

或者定义 rear，不定义size，都可以，此处队尾指针表示的是队尾元素的下一个节点，方便插入。

（3）扩容

// 队列扩容
private void resize(int newCapacity) {
    int[] newArray = new int[newCapacity];
    // 将旧数组元素按顺序复制到新数组头部
    for (int i = 0; i < size; i++) {
        newArray[i] = queue[(front + i) % capacity];
    }
    queue = newArray;
    front = 0;       // 重置队头指针
    capacity = newCapacity; // 更新容量
}

（4）enqueue（入队）

// 入队操作（支持自动扩容）
public void enqueue(int item) {
    // 队列已满时触发扩容
    if (isFull()) {
        resize(capacity * 2); // 容量翻倍
    }
    int rear = (front + size) % capacity;
    queue[rear] = item;
    size++;
}

（5）dequeue（出队）

// 出队操作
public int dequeue() {
    if (isEmpty()) {
        throw new IllegalStateException("队列为空，无法出队");
    }
    int item = queue[front];
    front = (front + 1) % capacity;
    size--;
    return item;
}

（6）peek（查看队头）

// 查看队头元素
public int peek() {
    if (isEmpty()) {
        throw new IllegalStateException("队列为空");
    }
    return queue[front];
}

（7）其他

// 判断队列是否为空
public boolean isEmpty() {
    return size == 0;
}

// 判断队列是否已满
public boolean isFull() {
    return size == capacity;
}

// 获取当前队列容量（测试用）
public int getCapacity() {
    return capacity;
}

（8）完整实现及测试代码

为了测试，初始容量改为3：

public class MyQueue {
    private int[] queue;   // 存储元素的数组
    private int front;     // 队头指针
    private int size;      // 当前元素数量
    private int capacity;  // 当前队列容量（不再是final）
    private static final int DEFAULT_CAPACITY = 3;
  
    // 初始化队列
    public MyQueue() {
        this.capacity = DEFAULT_CAPACITY;
        this.queue = new int[capacity];
        this.front = 0;
        this.size = 0;
    }

    // 入队操作（支持自动扩容）
    public void enqueue(int item) {
        // 队列已满时触发扩容
        if (isFull()) {
            resize(capacity * 2); // 容量翻倍
        }
        int rear = (front + size) % capacity;
        queue[rear] = item;
        size++;
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法出队");
        }
        int item = queue[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    // 查看队头元素
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return queue[front];
    }

    // 队列扩容
    private void resize(int newCapacity) {
        int[] newArray = new int[newCapacity];
        // 将旧数组元素按顺序复制到新数组头部
        for (int i = 0; i < size; i++) {
            newArray[i] = queue[(front + i) % capacity];
        }
        queue = newArray;
        front = 0;       // 重置队头指针
        capacity = newCapacity; // 更新容量
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断队列是否已满
    public boolean isFull() {
        return size == capacity;
    }

    // 获取当前队列容量（测试用）
    public int getCapacity() {
        return capacity;
    }

    // 测试代码
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();

        // 初始容量3
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        System.out.println("当前容量: " + queue.getCapacity()); // 3

        // 触发扩容到6
        queue.enqueue(40);
        System.out.println("扩容后容量: " + queue.getCapacity()); // 6

        // 继续填充测试
        queue.enqueue(50);
        queue.enqueue(60);
        queue.enqueue(70); // 再次触发扩容到12
        System.out.println("再次扩容后容量: " + queue.getCapacity()); // 12

        // 验证出队顺序
        System.out.print("出队顺序: ");
        while (!queue.isEmpty()) {
            System.out.print(queue.dequeue() + " "); // 10 20 30 40 50 60 70
        }
    }
}

3.基于链表的单端队列

（1）原理

由于我们只对头尾进行操作，所以我们可以用链表来实现，头删对应出队，尾差对应入队。

由于链式结构的存在，不必担心内存不足与内存浪费，当然，一般情况下，由于创建多个对象节点，其效率不如数组实现高。

（2）实现

由于与链表类似，我们直接给出完整实现及测试用例：
 

public class LinkedListQueue {
    // 链表节点定义
    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node front; // 队头指针（出队位置）
    private Node rear;  // 队尾指针（入队位置）
    private int size;   // 队列元素数量

    public LinkedListQueue() {
        front = null;
        rear = null;
        size = 0;
    }

    // 入队操作（尾插）
    public void enqueue(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            // 队列为空时，front和rear都指向新节点
            front = newNode;
            rear = newNode;
        } else {
            // 非空时，将新节点链接到队尾，并更新rear
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    // 出队操作（头删）
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法出队");
        }
        int item = front.data;
        front = front.next; // 移动队头指针
        size--;
        
        // 如果出队后队列为空，需要同时更新rear为null
        if (isEmpty()) {
            rear = null;
        }
        return item;
    }

    // 查看队头元素
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return front.data;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return front == null;
    }

    // 获取队列元素数量
    public int size() {
        return size;
    }

    // 测试代码
    public static void main(String[] args) {
        LinkedListQueue queue = new LinkedListQueue();
        
        // 入队测试
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        System.out.println("入队后队列大小: " + queue.size()); // 3
        
        // 查看队头
        System.out.println("当前队头: " + queue.peek()); // 10
        
        // 出队测试
        System.out.println("出队: " + queue.dequeue()); // 10
        System.out.println("出队: " + queue.dequeue()); // 20
        System.out.println("出队后剩余大小: " + queue.size()); // 1
        
        // 再次入队
        queue.enqueue(40);
        System.out.println("新队尾元素: " + queue.rear.data); // 40
        
        // 清空队列测试
        System.out.println("出队: " + queue.dequeue()); // 30
        System.out.println("出队: " + queue.dequeue()); // 40
        System.out.println("队列是否为空: " + queue.isEmpty()); // true
        
        // 测试空队列异常
        try {
            queue.dequeue();
        } catch (IllegalStateException e) {
            System.out.println("异常捕获: " + e.getMessage()); // 队列为空，无法出队
        }
    }
}

4.双端队列

（1）原理

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

其两端都可出入的特性给了Deque很大的灵活性，使其基本代替了Stack，成为栈的主要实现类。

其也是实现滑动窗口的首选数据结构。

由于实现基本同上，我们直接给出实现及测试用例。

（2）基于数组的双端队列

public class MyArrayDeque {
    private int[] data;
    private int front;   // 队头指针
    private int size;    // 当前元素数量
    private int capacity; // 当前容量
    private static final int DEFAULT_CAPACITY = 8;
    // 初始化队列（默认容量8）
    public MyArrayDeque() {
        this(DEFAULT_CAPACITY);
    }

    public MyArrayDeque(int initialCapacity) {
        capacity = initialCapacity;
        data = new int[capacity];
        front = 0;
        size = 0;
    }

    // 队头插入元素
    public void addFirst(int item) {
        if (isFull()) resize(capacity * 2);
        front = (front - 1 + capacity) % capacity; // 向前移动队头指针
        data[front] = item;
        size++;
    }

    // 队尾插入元素
    public void addLast(int item) {
        if (isFull()) resize(capacity * 2);
        int rear = (front + size) % capacity;
        data[rear] = item;
        size++;
    }

    // 移除队头元素
    public int removeFirst() {
        if (isEmpty()) throw new IllegalStateException("Deque is empty");
        int item = data[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    // 移除队尾元素
    public int removeLast() {
        if (isEmpty()) throw new IllegalStateException("Deque is empty");
        int rear = (front + size - 1) % capacity;
        int item = data[rear];
        size--;
        return item;
    }

    // 查看队头元素
    public int peekFirst() {
        if (isEmpty()) throw new IllegalStateException("Deque is empty");
        return data[front];
    }

    // 查看队尾元素
    public int peekLast() {
        if (isEmpty()) throw new IllegalStateException("Deque is empty");
        return data[(front + size - 1) % capacity];
    }

    // 动态扩容
    private void resize(int newCapacity) {
        int[] newData = new int[newCapacity];
        // 将元素按顺序复制到新数组头部
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % capacity];
        }
        data = newData;
        capacity = newCapacity;
        front = 0; // 重置队头指针
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }

    // 测试代码
    public static void main(String[] args) {
        MyArrayDeque deque = new MyArrayDeque(3);

        // 队头插入
        deque.addFirst(10);
        deque.addFirst(20);
        deque.addFirst(30); // 触发扩容到6

        // 队尾插入
        deque.addLast(40);
        deque.addLast(50);
        deque.addLast(60); // 再次触发扩容到12

        // 验证顺序
        System.out.println("队头移除: " + deque.removeFirst()); // 30
        System.out.println("队尾移除: " + deque.removeLast());   // 60
        System.out.println("当前队头: " + deque.peekFirst());    // 20
        System.out.println("当前队尾: " + deque.peekLast());     // 50
    }
}

（3）基于链表的双端队列

public class LinkedDeque {
    // 双向链表节点定义
    private static class Node {
        int data;
        Node prev;
        Node next;

        Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    private Node front;  // 队头指针
    private Node rear;   // 队尾指针
    private int size;    // 队列元素数量

    public LinkedDeque() {
        front = null;
        rear = null;
        size = 0;
    }

    // 队头插入元素
    public void addFirst(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            // 队列为空时，front和rear都指向新节点
            front = rear = newNode;
        } else {
            // 将新节点链接到当前队头前
            newNode.next = front;
            front.prev = newNode;
            front = newNode; // 更新队头指针
        }
        size++;
    }

    // 队尾插入元素
    public void addLast(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            // 将新节点链接到当前队尾后
            rear.next = newNode;
            newNode.prev = rear;
            rear = newNode; // 更新队尾指针
        }
        size++;
    }

    // 移除队头元素
    public int removeFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法移除");
        }
        int item = front.data;
        if (front == rear) {
            // 只有一个元素时，移除后队列为空
            front = rear = null;
        } else {
            front = front.next;
            front.prev = null; // 断开旧队头链接
        }
        size--;
        return item;
    }

    // 移除队尾元素
    public int removeLast() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法移除");
        }
        int item = rear.data;
        if (front == rear) {
            front = rear = null;
        } else {
            rear = rear.prev;
            rear.next = null; // 断开旧队尾链接
        }
        size--;
        return item;
    }

    // 查看队头元素
    public int peekFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return front.data;
    }

    // 查看队尾元素
    public int peekLast() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return rear.data;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    // 打印队列内容（测试用）
    public void display() {
        Node current = front;
        System.out.print("队列内容: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // 测试代码
    public static void main(String[] args) {
        LinkedDeque deque = new LinkedDeque();
        
        // 队头插入测试
        deque.addFirst(10);
        deque.addFirst(20);
        deque.display(); // 队列内容: 20 10
        
        // 队尾插入测试
        deque.addLast(30);
        deque.addLast(40);
        deque.display(); // 队列内容: 20 10 30 40
        
        // 移除测试
        System.out.println("移除队头: " + deque.removeFirst()); // 20
        System.out.println("移除队尾: " + deque.removeLast());  // 40
        deque.display(); // 队列内容: 10 30
        
        // 边界测试
        deque.removeFirst();
        deque.removeLast();
        System.out.println("队列是否为空: " + deque.isEmpty()); // true
        
        // 异常测试
        try {
            deque.removeFirst();
        } catch (IllegalStateException e) {
            System.out.println("异常捕获: " + e.getMessage());
        }
    }
}

5.其他队列

• 优先级队列（PriorityQueue）：其底层实现是堆，具体来说是完全二叉树，我们会单独开一篇博客分析。
• 阻塞队列（BlockingDeque）：用于线程操作的数据结构。

三.队列API的使用

Java当中基础队列有2种实现方式：

• ArrayDeque
• LinkedList

一般两者可以相互替代，只是LinkedList适用于需要频繁增删的队列，ArrayDeque适用于对访问性能要求高的队列，一般我们用ArrayDeque。

本博客重点在于理解其实现以及原理，详细使用请详见：Java ArrayDeque - Java教程 - 菜鸟教程

以及官方文档：ArrayDeque (Java Platform SE 8 )

结语

队列还是比较好理解和实现的，在理解了数据结构的底层原理以及实现后，我们才能更加清晰地正确使用数据结构，也能更好地学习后面的算法和原理了。

好了，本博客到此结束，喜欢不妨点个赞吧，我接下来会把剩下的数据结构一一解析完，下次是二叉树，敬请期待！

我们下次见ξ( ✿＞◡❛)!