【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();// 初始容量3queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);System.out.println("当前容量: " + queue.getCapacity()); // 3// 触发扩容到6queue.enqueue(40);System.out.println("扩容后容量: " + queue.getCapacity()); // 6// 继续填充测试queue.enqueue(50);queue.enqueue(60);queue.enqueue(70); // 再次触发扩容到12System.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 {// 非空时，将新节点链接到队尾，并更新rearrear.next = newNode;rear = newNode;}size++;}// 出队操作（头删）public int dequeue() {if (isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}int item = front.data;front = front.next; // 移动队头指针size--;// 如果出队后队列为空，需要同时更新rear为nullif (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()); // 10System.out.println("出队: " + queue.dequeue()); // 20System.out.println("出队后剩余大小: " + queue.size()); // 1// 再次入队queue.enqueue(40);System.out.println("新队尾元素: " + queue.rear.data); // 40// 清空队列测试System.out.println("出队: " + queue.dequeue()); // 30System.out.println("出队: " + queue.dequeue()); // 40System.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()); // 30System.out.println("队尾移除: " + deque.removeLast());   // 60System.out.println("当前队头: " + deque.peekFirst());    // 20System.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()); // 20System.out.println("移除队尾: " + deque.removeLast());  // 40deque.display(); // 队列内容: 10 30// 边界测试deque.removeFirst();deque.removeLast();System.out.println("队列是否为空: " + deque.isEmpty()); // true// 异常测试try {deque.removeFirst();} catch (IllegalStateException e) {System.out.println("异常捕获: " + e.getMessage());}}
}