队列(Queue)数据结构详解

先进先出(FIFO)的线性数据结构 · 系统设计核心组件

什么是队列

队列(Queue)是一种遵循先进先出(FIFO, First In First Out)原则的线性数据结构。就像现实中排队一样，先排队的人先得到服务，后来的人只能排在队尾等待。

            核心特性：元素只能从队尾(Rear)插入，从队首(Front)删除。这种受限的访问方式使队列成为处理顺序任务的理想选择。
        

队列与栈的区别

特性	队列(Queue)	栈(Stack)
访问原则	FIFO(先进先出)	LIFO(后进先出)
插入位置	队尾(Rear)	栈顶(Top)
删除位置	队首(Front)	栈顶(Top)
典型应用	任务调度、BFS	函数调用、DFS

队列类型

FIFO普通队列(Simple Queue)

最基本的队列形式，元素从队尾入队，从队首出队。数组实现时可能存在"假溢出"问题——即数组前端有空位但无法使用。

循环循环队列(Circular Queue)

通过取模运算将数组首尾相连，解决普通队列的空间浪费问题。当指针到达数组末尾时自动回绕到开头，充分利用空间。

优先优先队列(Priority Queue)

元素按优先级排序，优先级高的元素先出队。通常用堆(Heap)实现，广泛应用于Dijkstra算法、任务调度等场景。

双端队列(Deque)

双端队列允许在队首和队尾都进行插入和删除操作，是队列和栈的泛化形式。Java中的ArrayDeque和LinkedList都实现了Deque接口。

阻塞队列(Blocking Queue)

在多线程环境下，当队列为空时获取操作会阻塞等待，当队列满时插入操作会阻塞等待。是生产者-消费者模式的核心组件，Java中的BlockingQueue接口提供了多种实现。

基本操作

操作	描述	时间复杂度
`enqueue(e)`	将元素e添加到队尾	O(1)
`dequeue()`	移除并返回队首元素	O(1)
`peek()/front()`	查看队首元素但不移除	O(1)
`isEmpty()`	检查队列是否为空	O(1)
`size()`	返回队列中元素数量	O(1)
`isFull()`	检查队列是否已满(有界队列)	O(1)

注意：优先队列的enqueue操作需要维护堆序性，时间复杂度为O(log n)；dequeue同样为O(log n)。

实现方式

数组实现(循环队列)

class CircularQueue {
    constructor(capacity) {
        this.data = new Array(capacity);
        this.capacity = capacity;
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    // 入队
    enqueue(element) {
        if (this.isFull()) return false;
        this.data[this.rear] = element;
        this.rear = (this.rear + 1) % this.capacity;
        this.size++;
        return true;
    }
    // 出队
    dequeue() {
        if (this.isEmpty()) return null;
        const element = this.data[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size--;
        return element;
    }
    isEmpty() { return this.size === 0; }
    isFull() { return this.size === this.capacity; }
}

链表实现

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}
class LinkedQueue {
    constructor() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }
    enqueue(value) {
        const node = new Node(value);
        if (this.isEmpty()) {
            this.front = this.rear = node;
        } else {
            this.rear.next = node;
            this.rear = node;
        }
        this.size++;
    }
    dequeue() {
        if (this.isEmpty()) return null;
        const value = this.front.value;
        this.front = this.front.next;
        if (!this.front) this.rear = null;
        this.size--;
        return value;
    }
    isEmpty() { return this.size === 0; }
}

优先队列(最小堆实现)

class MinHeap {
    constructor() { this.heap = []; }
    // 入队：添加到末尾后上浮
    enqueue(val, priority) {
        this.heap.push({ val, priority });
        this._siftUp(this.heap.length - 1);
    }
    // 出队：取出堆顶后下沉
    dequeue() {
        if (this.heap.length === 0) return null;
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this._siftDown(0);
        }
        return min;
    }
    _siftUp(i) {
        while (i > 0) {
            const p = Math.floor((i - 1) / 2);
            if (this.heap[p].priority <= this.heap[i].priority) break;
            [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
            i = p;
        }
    }
    _siftDown(i) {
        const n = this.heap.length;
        while (2 * i + 1 < n) {
            let j = 2 * i + 1;
            if (j + 1 < n && this.heap[j+1].priority < this.heap[j].priority) j++;
            if (this.heap[i].priority <= this.heap[j].priority) break;
            [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
            i = j;
        }
    }
}

交互演示

选择队列类型，通过入队/出队操作观察队列的工作原理：

队列类型:

输入元素:

优先级:

队列可视化

队列为空

复杂度分析

队列类型	入队	出队	查看队首	空间复杂度
普通队列(数组)	O(1)	O(1)*	O(1)	O(n)
循环队列	O(1)	O(1)	O(1)	O(n)
链表队列	O(1)	O(1)	O(1)	O(n)
优先队列(堆)	O(log n)	O(log n)	O(1)	O(n)

* 普通数组队列出队如需移动元素则为O(n)，使用双指针技术可优化为O(1)但会造成空间浪费。

应用场景

广度优先搜索(BFS)：图遍历算法的核心数据结构，按层次顺序访问节点
任务调度：操作系统进程调度、打印任务队列、线程池任务管理
消息队列：RabbitMQ、Kafka等中间件实现异步解耦与削峰填谷
缓冲区：IO缓冲、网络数据包缓冲、视频流缓冲
生产者-消费者模式：多线程协作的经典模式
滑动窗口：网络流量控制、限流算法、实时数据处理
最短路径算法：Dijkstra算法使用优先队列选择最小距离节点
事件驱动系统：GUI事件循环、游戏引擎事件处理

实际案例：Web服务器请求队列

            Web服务器使用请求队列管理并发连接。当请求到达速度超过处理能力时，请求被放入队列等待。Tomcat的acceptCount参数控制等待队列长度，Nginx使用backlog配置监听队列大小。
        

队列类型对比

特性	普通队列	循环队列	优先队列	双端队列
入队位置	队尾	队尾	按优先级	两端均可
出队位置	队首	队首	最高优先级	两端均可
空间利用	可能浪费	高效	高效	高效
实现复杂度	简单	中等	较复杂	中等
典型实现	数组/链表	数组	堆	数组/链表
Java类	LinkedList	ArrayDeque	PriorityQueue	ArrayDeque

选择建议

需要严格FIFO顺序 → 普通队列或循环队列
固定容量且需高效空间利用 → 循环队列
需要按优先级处理 → 优先队列
需要两端操作灵活性 → 双端队列
多线程环境 → 阻塞队列(如ConcurrentLinkedQueue)