队列的基本概念

1. 特点

• FIFO：先进先出，即第一个加入队列的元素将第一个被移除。
• 基本操作：
  • Enqueue：在队尾插入新元素。
  • Dequeue：移除队首元素并返回其值。
  • Peek：查看队首元素但不移除它。
  • isEmpty：检查队列是否为空。
  • Size：返回队列中元素的数量。

2. 应用场景

• 资源调度：如 CPU 任务调度、操作系统的进程管理。
• 数据缓冲：如网络数据包缓冲、I/O 缓存。
• 广度优先搜索：在图或树中实现广度优先搜索（BFS）。

---

一、普通队列（Queue）

定义与实现原理

普通队列是一种典型的 FIFO 数据结构，可以用数组或链表实现。队列的起始端称为队首（Front），元素从队尾（Rear）插入并从队首移除。

1. 优点

• 结构简单：操作仅限于队首和队尾，逻辑清晰。
• 实现简单：基于数组或链表均可方便实现。

2. 缺点

• 内存浪费：使用数组实现时，元素出队后，前端空间无法复用。
• 容量固定：基于数组的实现需要预定义大小，可能导致溢出或浪费。

3. 适用场景

• 任务调度：如打印机作业队列、操作系统进程管理。
• 数据流缓冲：如网络传输、消息队列。

4. 示例代码（Java）

class Queue {private int[] queue;private int front;private int rear;private int capacity;private int size;public Queue(int capacity) {this.capacity = capacity;queue = new int[capacity];front = 0;rear = -1;size = 0;}// 入队操作public void enqueue(int value) {if (isFull()) {throw new IllegalStateException("队列已满，无法入队");}rear = (rear + 1) % capacity;queue[rear] = value;size++;}// 出队操作public int dequeue() {if (isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}int value = queue[front];front = (front + 1) % capacity;size--;return value;}// 查看队首元素public int peek() {if (isEmpty()) {throw new IllegalStateException("队列为空，无法查看队首");}return queue[front];}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == capacity;}public int getSize() {return size;}
}

二、循环队列（Circular Queue）

定义与实现原理

循环队列在普通队列的基础上通过“环形”结构解决了内存浪费问题。即当队列尾部到达数组末端时，若数组前端有空位，则队尾可以“循环”至数组的起始位置。这种设计使得队列可以利用已出队元素的空间，提高了内存利用率。

1. 优点

• 内存利用率高：通过循环结构实现空间复用，避免了数组前端的空位浪费。
• 操作简单：依然只需维护队首和队尾的指针。

2. 缺点

• 容量固定：依然需要预设大小，不支持动态扩展。

3. 适用场景

• 缓存区：如多媒体数据流缓冲、循环缓冲区。
• 调度系统：如 CPU 任务轮询调度。

4. 示例代码（Java）

class CircularQueue {private int[] queue;private int front;private int rear;private int capacity;private int size;public CircularQueue(int capacity) {this.capacity = capacity;queue = new int[capacity];front = 0;rear = -1;size = 0;}// 入队操作public void enqueue(int value) {if (isFull()) {throw new IllegalStateException("队列已满，无法入队");}rear = (rear + 1) % capacity;queue[rear] = value;size++;}// 出队操作public int dequeue() {if (isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}int value = queue[front];front = (front + 1) % capacity;size--;return value;}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == capacity;}
}

三、双端队列（Deque）

定义与实现原理

双端队列（Deque）是一种扩展的队列，支持从两端进行插入和删除。Deque 分为 输入受限双端队列（仅允许从一端插入元素）和 输出受限双端队列（仅允许从一端删除元素）。

1. 优点

• 灵活性高：可在队列两端操作，既支持先进先出也支持后进先出。
• 多功能性：适合实现复杂的队列结构，如双向遍历或优先级调度。

2. 缺点

• 实现复杂：操作两端的逻辑较复杂，且链表实现时内存消耗较大。

3. 适用场景

• 浏览器前进后退功能：实现历史记录的快速访问。
• 滑动窗口算法：在数据流中实时计算窗口内的最小值或最大值。

4. 示例代码（Java）

import java.util.LinkedList;class Deque {private LinkedList<Integer> deque;public Deque() {deque = new LinkedList<>();}// 队首入队public void addFront(int value) {deque.addFirst(value);}// 队尾入队public void addRear(int value) {deque.addLast(value);}// 队首出队public int removeFront() {if (deque.isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}return deque.removeFirst();}// 队尾出队public int removeRear() {if (deque.isEmpty()) {throw new IllegalStateException("队列为空，无法出队");}return deque.removeLast();}// 查看队首元素public int peekFront() {if (deque.isEmpty()) {throw new IllegalStateException("队列为空");}return deque.getFirst();}// 查看队尾元素public int peekRear() {if (deque.isEmpty()) {throw new IllegalStateException("队列为空");}return deque.getLast();}
}

四、优先队列（Priority Queue）

定义与实现原理

优先队列是一种特殊的队列，元素按优先级排列。出队时优先级最高的元素先出队。可以通过 堆（如二叉堆）或 排序链表 实现优先队列。

1. 优点

• 灵活性强：根据优先级决定元素出队顺序，而不是固定的 FIFO。
• 适合处理多任务调度：优先级越高的任务越先得到处理。

2. 缺点

• 实现复杂：需要排序或堆操作，插入和删除操作相对复杂。
• 性能依赖于实现：不同实现方法对性能的影响较大，使用堆可达到 O(log n) 的插入和删除效率。

3. 适用场景

• 任务调度：CPU 任务调度、网络数据包优先级管理。
• 最短路径算法：如 Dijkstra 算法中优先处理距离最短的节点。

4. 示例代码（Java）

Java 中的 PriorityQueue 类实现了优先队列，以下示例展示了使用 Java 内置优先队列。

import java.util.PriorityQueue;public class PriorityQueueExample {public static void main(String[] args) {// 创建优先队列，默认情况下，优先级越小的元素越先出队PriorityQueue<Integer> pq = new PriorityQueue<>();pq.add(30);pq.add(10);pq.add(20);// 出队，按优先级顺序出队while (!pq.isEmpty()) {System.out.println(pq.poll()); // 输出 10 20 30}}
}

总结对比

类型	特点	优点	缺点	适用场景
普通队列	先进先出（FIFO）	结构简单，操作高效	内存浪费（数组实现）	任务调度、数据流缓冲
循环队列	环形结构，解决内存浪费问题	内存利用率高	容量固定	缓冲区、轮询调度
双端队列	支持两端插入和删除	灵活性高	实现复杂	浏览器历史、滑动窗口
优先队列	按优先级出队	灵活性强，适合调度任务	实现复杂，性能依赖于实现方法	任务调度、最短路径算法

根据具体需求和场景选择合适的队列类型，能更好地解决问题。