数据结构之队列：原理与应用

一、基本原理

• 队列是一种特殊的线性表
• 队列是一个有序表(可以用数组或链表实现)
• 遵循“先来先服务”的原则，它只允许在表的前端（队头）进行删除操作，在表的后端（队尾）进行插入操作

(一) 核心操作

• 入队（Enqueue）：在队尾添加元素。
• 出队（Dequeue）：从队头移除元素。
• 查看队头（Front）：获取队头元素但不移除。
• 判空（IsEmpty）：检查队列是否为空。

队列的逻辑结构类似于现实中的排队场景，例如超市收银或银行叫号系统，先到达的顾客优先服务。

(二) 代码示例

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        // 创建一个队列
        Queue<Integer> queue = new LinkedList<>();

        // 入队
        queue.offer(10);
        queue.offer(20);

        System.out.println("队列大小: " + queue.size());// 输出 2

        // 出队
        int front = queue.poll();
        System.out.println("出队元素: " + front);  // 输出 10

        // 查看队列的头元素但不移除它
        int peek = queue.peek();
        System.out.println("队列头元素: " + peek);  // 输出 20

        // 检查队列是否为空
        boolean isEmpty = queue.isEmpty();
        System.out.println("队列是否为空: " + isEmpty);  // 输出 false
    }
}

public interface Queue<E> extends Collection<E> {
    //插入元素，成功返回true，失败抛出异常
    boolean add(E e);
    //插入元素，成功返回true，失败返回false或抛出异常 
    boolean offer(E e);
    //取出并移除头部元素，空队列抛出异常 
    E remove();
    //取出并移除头部元素，空队列返回null 
    E poll();
    //取出但不移除头部元素，空队列抛出异常 
    E element();
    //取出但不移除头部元素，空队列返回null 
    E peek();
    //删除并返回队头元素，当队列为空，则会阻塞等待
    E take();
}

二、基本类型

1. 双端队列（Deque）

• • 支持在队头和队尾同时进行插入和删除操作，灵活性更高。

1. 优先队列（Priority Queue）

• • 元素按优先级出队，而非顺序，适用于任务调度等需要优先级处理的场景。

1. 阻塞队列

• • 在队列为空时，出队操作阻塞；在队列满时，入队操作阻塞，适用于多线程同步场景。

三、实现方式

队列的实现主要有两种方式，各自适用于不同场景：

1. 数组实现（顺序队列）

• • 特点：使用固定大小的数组存储元素，通过两个指针（front和rear）分别标记队头和队尾。
  • 问题：当rear指针到达数组末尾时，若队头有空闲位置，无法直接利用，导致“假溢出”。
  • 优化方案：引入循环队列，通过模运算实现指针的循环移动，从而高效利用数组空间。

1. 链表实现（链式队列）

• • 特点：使用动态链表存储元素，无需预先分配固定大小，通过两个指针（head和tail）分别指向队头和队尾。
  • 优势：空间利用率高，适合元素数量不确定或动态变化的场景。

四、复杂度分析

• 时间复杂度：

• • 入队（Enqueue）：O(1)（数组和链表实现均高效）。
  • 出队（Dequeue）：O(1)（链表实现直接操作头节点；数组实现需移动指针，但循环队列优化后仍为O(1)）。

• 空间复杂度：

• • 数组实现：固定大小，可能浪费空间或溢出。
  • 链表实现：动态分配，空间利用率高，但需额外指针存储空间。

五、应用场景

队列在计算机科学和实际工程中具有广泛应用，以下是一些典型场景：

1. 任务调度与资源管理

• • 操作系统进程调度：CPU按照队列顺序执行进程，确保公平性。
  • 打印机任务队列：用户提交的打印任务按顺序处理，避免混乱。

1. 消息传递与缓冲区管理

• • 网络数据包处理：接收到的数据包按顺序进入队列，由处理器按顺序处理，确保数据完整性。
  • 生产者-消费者模型：生产者将数据放入队列，消费者从队列中取出数据，实现解耦和异步处理。

1. 算法与系统设计

• • 广度优先搜索（BFS）：使用队列逐层遍历图的节点，确保按层次访问。
  • Web服务器请求处理：客户端请求按顺序进入队列，服务器按顺序响应，避免过载。

1. 异步通信与事件处理

• • 即时通讯应用：如WhatsApp在用户离线时，消息暂存于队列，待用户上线后按顺序接收。
  • GUI事件处理：用户操作事件按顺序进入队列，由事件循环按顺序处理。

六、优缺点

• 优点：

• • 逻辑简单，易于实现。
  • 保证元素顺序处理，适用于需要公平性的场景。

• 缺点：

• • 数组实现需预先分配空间，可能浪费或不足。
  • 中间插入或删除效率低（需移动大量元素），但队列通常不涉及此类操作。

七、参看资料

Java 中常用队列用法详解 - 技术栈