1. 什么是队列？

队列（Queue）是一种先进先出（First In First Out，FIFO）的线性数据结构。它只允许在表的一端（队尾）进行插入操作，在另一端（队头）进行删除操作。队列的这种特性使其非常适用于需要按顺序处理任务的场景，例如：

• 操作系统的进程调度
• 打印任务队列
• 消息队列系统
• 广度优先搜索（BFS）算法
• 网络数据包缓冲

2. 队列的基本操作

队列通常支持以下基本操作：

• 入队（Enqueue）：在队尾添加一个元素
• 出队（Dequeue）：从队头移除并返回一个元素
• 获取队头元素（Peek/Front）：查看队头元素但不移除
• 判断队列是否为空（IsEmpty）
• 获取队列大小（Size）

3. 队列的实现方式

3.1 数组实现（顺序队列）

使用数组实现队列时，需要维护两个指针：front（队头）和 rear（队尾）。

public class ArrayQueue<T> {
    private T[] array;
    private int front;
    private int rear;
    private int capacity;
    private int size;
    
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.array = (T[]) new Object[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }
    
    public void enqueue(T item) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear + 1) % capacity;
        array[rear] = item;
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T item = array[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return array[front];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
    
    public int size() {
        return size;
    }
}

3.2 链表实现（链式队列）

使用链表实现队列更加灵活，不需要考虑容量限制。

public class LinkedListQueue<T> {
    private static class Node<T> {
        T data;
        Node<T> next;
        
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
    
    private Node<T> front;
    private Node<T> rear;
    private int size;
    
    public LinkedListQueue() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }
    
    public void enqueue(T item) {
        Node<T> newNode = new Node<>(item);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T item = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return item;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return front.data;
    }
    
    public boolean isEmpty() {
        return front == null;
    }
    
    public int size() {
        return size;
    }
}

4. 队列的变种

4.1 双端队列（Deque）

双端队列允许在队列的两端进行插入和删除操作。

// Java 中的 Deque 接口
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("First");  // 队头插入
deque.addLast("Last");    // 队尾插入
String first = deque.removeFirst();  // 队头删除
String last = deque.removeLast();    // 队尾删除

4.2 优先队列（Priority Queue）

优先队列中的元素按照优先级出队，而不是按照入队顺序。

// Java 中的 PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
while (!pq.isEmpty()) {
    System.out.println(pq.poll());  // 输出：1, 3, 5（默认最小堆）
}

4.3 循环队列（Circular Queue）

循环队列是数组实现的一种优化，可以更有效地利用数组空间。

5. 队列的应用场景

5.1 广度优先搜索（BFS）

在图的遍历中，BFS 算法使用队列来存储待访问的节点。

public void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    
    queue.offer(start);
    visited.add(start);
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.println(current.value);
        
        for (Node neighbor : current.neighbors) {
            if (!visited.contains(neighbor)) {
                queue.offer(neighbor);
                visited.add(neighbor);
            }
        }
    }
}

5.2 线程池任务队列

线程池使用队列来管理待执行的任务。

// Java 线程池示例
ExecutorService executor = Executors.newFixedThreadPool(5);
BlockingQueue<Runnable> workQueue = new LinkedBlockingQueue<>();

// 提交任务到队列
for (int i = 0; i < 10; i++) {
    int taskId = i;
    executor.submit(() -> {
        System.out.println("Executing task " + taskId);
    });
}

executor.shutdown();

5.3 消息队列

分布式系统中使用消息队列进行异步通信和解耦。

6. 队列的时间复杂度分析

操作	数组实现	链表实现
入队（Enqueue）	O(1) 平均	O(1)
出队（Dequeue）	O(1) 平均	O(1)
查看队头（Peek）	O(1)	O(1)
判断空（IsEmpty）	O(1)	O(1)

7. 总结

队列作为一种基础的数据结构，在计算机科学中有着广泛的应用。理解队列的原理和实现方式，对于学习算法和系统设计都至关重要。在实际开发中，可以根据具体需求选择合适的队列实现：

• 需要固定容量时选择数组实现
• 需要动态扩容时选择链表实现
• 需要优先级处理时选择优先队列
• 需要两端操作时选择双端队列

掌握队列不仅有助于解决算法问题，还能帮助理解操作系统、网络通信和分布式系统等复杂系统的设计原理。