线性数据结构之队列

队列的基本概念

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
        }
    }
}

总结对比

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