1、什么是队列

队列 (Queue) 是一种基础的线性数据结构。想象一下在超市排队结账的场景：最先到达收银台的人会最先完成结账离开。后来的人需要排在队伍的末尾，并等待前面的人全部处理完毕。

核心原则：先进先出 (First-In, First-Out)，这个原则通常缩写为 FIFO。它规定了数据处理的顺序：最早进入队列的元素，将是第一个被移除和处理的元素

2、队列的基本结构

为什么要有队首和队尾？

• 队首（front）：用于删除元素，保证最先入队的元素最先出队
• 队尾（rear）：用于添加元素，新元素总是添加到队列末尾
• 单向操作：这种设计确保了FIFO原则的严格执行

3、队列的基本操作

操作	描述	时间复杂度
入队	在队尾添加一个元素	O(1)
出队	从队首删除一个元素并返回	O(1)
查看队首	查看队首元素但不删除	O(1)
判断空队列	检查队列是否为空	O(1)
获取大小	返回队列中元素的数量	O(1)

3.1 入队操作

因为队列遵循FIFO原则，新来的元素应该排在队伍的最后面，等待轮到它时才能被处理。

3.2 出队操作

因为队首的元素是最早入队的，按照FIFO原则，它应该最先被处理和移除。

4、有界和无界队列

一个非常重要的细节是队列的容量。根据容量是否有限，队列可以分为两类：

• 无界队列 : 理论上可以无限增长，只要系统内存充足。Python 的 <font style="color:rgb(31, 41, 55);background-color:rgb(249, 250, 251);">list</font> 和 <font style="color:rgb(31, 41, 55);background-color:rgb(249, 250, 251);">deque</font>默认都是无界队列。
• 有界队列 : 具有固定的容量上限。当队列满了之后，任何新的入队请求都需要根据预设的策略来处理。这在资源有限或需要控制生产速率的场景中非常关键。

5、可视化演示

juejin

6、基于 Java 实现的队列

6.1 基于数组的队列

public class ArrayQueue {
    private Object[] items;
    private int head;
    private int tail;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        items = new Object[capacity];
        head = 0;
        tail = 0;
    }

    // 入队
    public boolean enqueue(Object item) {
        if (tail == capacity) { // 队列已满
            return false;
        }
        items[tail] = item;
        tail++;
        return true;
    }

    // 出队
    public Object dequeue() {
        if (head == tail) { // 队列为空
            return null;
        }
        Object item = items[head];
        head++;
        return item;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Queue: [");
        for (int i = head; i < tail; i++) {
            sb.append(items[i]);
            if (i < tail - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

6.2 基于 LinkedList 的队列

Java 中 LinkedList 本身实现了 Queue 接口，可直接用于队列操作：

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

public class LinkedListQueueDemo {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        // 入队
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        // 出队
        System.out.println(queue.poll()); // 输出 10
        // 查看队首元素（不出队）
        System.out.println(queue.peek()); // 输出 20
        System.out.println(queue); // 输出 [20, 30]
    }
}

6.3 两种方式的性能对比

操作	数组队列	LinkedList 队列
入队/出队	若不扩容，时间复杂度为 O(1)；若扩容，为 O(n)	时间复杂度始终为 O(1)
空间占用	需预先分配容量，可能有空间浪费	元素按需分配，空间利用率更高
适用场景	已知队列最大容量，追求高吞吐	队列容量不确定，或频繁进行增删

6.4 使用链表实现队列（自定义）

public class LinkedQueue {
    // 节点类
    private static class Node {
        Object data;
        Node next;

        public Node(Object data) {
            this.data = data;
        }
    }

    private Node head;
    private Node tail;
    private int size;

    public LinkedQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    // 入队
    public void enqueue(Object item) {
        Node newNode = new Node(item);
        if (tail == null) { // 队列为空
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
    }

    // 出队
    public Object dequeue() {
        if (head == null) { // 队列为空
            return null;
        }
        Object item = head.data;
        head = head.next;
        if (head == null) { // 队列空了，tail 置空
            tail = null;
        }
        size--;
        return item;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Queue: [");
        Node cur = head;
        while (cur != null) {
            sb.append(cur.data);
            if (cur.next != null) {
                sb.append(", ");
            }
            cur = cur.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

6.5 线程安全的队列

Java 提供了 java.util.concurrent 包下的线程安全队列，如 ConcurrentLinkedQueue（非阻塞）、ArrayBlockingQueue（阻塞）等。

示例（ConcurrentLinkedQueue）：

import java.util.concurrent.ConcurrentLinkedQueue;

public class ThreadSafeQueueDemo {
    public static void main(String[] args) {
        ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();
        // 入队
        queue.offer(100);
        queue.offer(200);
        // 出队
        System.out.println(queue.poll()); // 输出 100
    }
}

7、特殊类型的队列

7.1 循环队列（参考前文的 CircularQueue 实现）

核心是利用取模运算实现“环形复用”，避免数组队列的“假溢出”问题。

7.2 双端队列（Deque）

Java 中 Deque 接口支持两端（队首、队尾）的入队/出队操作，LinkedList 和 ArrayDeque 都实现了该接口。

示例（ArrayDeque）：

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        // 队尾入队
        deque.offerLast("A");
        deque.offerLast("B");
        // 队首入队
        deque.offerFirst("C");
        // 队首出队
        System.out.println(deque.pollFirst()); // 输出 C
        // 队尾出队
        System.out.println(deque.pollLast()); // 输出 B
    }
}

7.3 优先队列（PriorityQueue）

基于堆结构实现，元素按优先级（默认自然序或自定义比较器）出队。

示例：

import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(30);
        pq.offer(10);
        pq.offer(20);
        // 出队时按从小到大顺序
        System.out.println(pq.poll()); // 输出 10
        System.out.println(pq.poll()); // 输出 20
    }
}

自定义比较器（实现大顶堆）：

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
pq.offer(30);
pq.offer(10);
pq.offer(20);
System.out.println(pq.poll()); // 输出 30

7.4 队列对比

队列类型	核心特性	典型实现类/接口	适用场景
普通队列	先进先出（FIFO）	Queue/LinkedList/ArrayQueue	任务调度、消息队列等基础场景
循环队列	数组环形复用，减少空间浪费	自定义 CircularQueue	已知容量上限的高性能场景
双端队列	两端均可增删	Deque/ArrayDeque/LinkedList	滑动窗口、栈模拟等场景
优先队列	按优先级出队	PriorityQueue	任务优先级调度、TopK 问题
线程安全队列	支持多线程并发操作	ConcurrentLinkedQueue/ArrayBlockingQueue	并发编程中的数据共享

8、应用场景

• 普通队列：消息队列（如 RabbitMQ 底层逻辑）、广度优先搜索（BFS）。
• 循环队列：数据库连接池、生产者-消费者模型的缓冲区。
• 双端队列：滑动窗口算法（如“最长无重复子串”问题）、栈的模拟（Deque 可当栈用）。
• 优先队列：任务调度（如高优先级任务先执行）、求数据流的中位数。
• 线程安全队列：多线程环境下的日志收集、任务分发。

9、总结

Java 中队列的实现丰富多样，从基础的数组、链表队列，到特殊的循环队列、双端队列、优先队列，再到线程安全队列，每种队列都有其适用场景。在实际开发中，需根据容量是否确定、是否需要并发支持、元素优先级要求等因素，选择合适的队列实现。