队列算法题解题思路与代码分析

1. 基础实现与栈混合类

核心解题思路

• 用栈实现队列：使用两个栈，一个负责入队（inStack），一个负责出队（outStack）。出队时，如果 outStack 为空，将 inStack 中的所有元素依次弹出并压入 outStack，这样 outStack 的栈顶就是最先入队的元素。
• 用队列实现栈：使用一个队列，入栈时正常入队；出栈时，将队首的前 n-1 个元素依次出队并重新入队，这样原来的队尾元素就移动到了队首，然后将其出队。

经典例题：232. 用栈实现队列

/**
 * 初始化两个栈
 * inStack 用于入队操作
 * outStack 用于出队操作
 */
var MyQueue = function() {
    this.inStack = [];
    this.outStack = [];
};

/** 
 * 入队：直接压入 inStack
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.inStack.push(x);
};

/**
 * 将 inStack 的元素转移到 outStack，确保 outStack 的栈顶是最先入队的元素
 * @return {void}
 */
MyQueue.prototype.transfer = function() {
    if (this.outStack.length === 0) {
        while (this.inStack.length > 0) {
            this.outStack.push(this.inStack.pop());
        }
    }
};

/**
 * 出队：如果 outStack 为空，先转移，然后弹出 outStack 栈顶
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    this.transfer();
    return this.outStack.pop();
};

/**
 * 获取队首元素：类似 pop，但只查看不弹出
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    this.transfer();
    return this.outStack[this.outStack.length - 1];
};

/**
 * 判断队列是否为空
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.inStack.length === 0 && this.outStack.length === 0;
};

关键点：

• transfer 方法保证了 outStack 的栈顶始终是队首元素。
• 只有在 outStack 为空时才进行转移，避免了频繁转移，摊还时间复杂度为 O(1)。

2. 优先队列（堆）类

核心解题思路

优先队列通常用堆实现。在 JavaScript 中，没有内置的堆，但可以使用数组模拟，或者借助第三方库。在力扣中，我们可以手写一个最小堆或最大堆来解决 TopK、数据流中位数等问题。以下例题使用自定义最小堆。

经典例题：347. 前 K 个高频元素

/**
 * 思路：哈希表统计频率，然后维护一个大小为 k 的最小堆
 * 堆中保存 [频率, 元素] 的二元组，按频率排序
 */

// 最小堆实现
class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 插入元素
    push(node) {
        this.heap.push(node);
        this.bubbleUp(this.heap.length - 1);
    }
    // 弹出堆顶（最小值）
    pop() {
        const min = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return min;
    }
    // 上浮
    bubbleUp(index) {
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2);
            if (this.heap[parent][0] > this.heap[index][0]) {
                [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
                index = parent;
            } else {
                break;
            }
        }
    }
    // 下沉
    sinkDown(index) {
        const length = this.heap.length;
        while (true) {
            let leftChild = 2 * index + 1;
            let rightChild = 2 * index + 2;
            let swap = null;
            let element = this.heap[index];

            if (leftChild < length && this.heap[leftChild][0] < element[0]) {
                swap = leftChild;
            }

            if (rightChild < length) {
                if ((swap === null && this.heap[rightChild][0] < element[0]) ||
                    (swap !== null && this.heap[rightChild][0] < this.heap[leftChild][0])) {
                    swap = rightChild;
                }
            }

            if (swap === null) break;
            [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
            index = swap;
        }
    }
    size() {
        return this.heap.length;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    // 统计频率
    const freqMap = new Map();
    for (const num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }

    const minHeap = new MinHeap();

    // 遍历频率表，维护大小为 k 的最小堆
    for (const [num, freq] of freqMap) {
        if (minHeap.size() < k) {
            minHeap.push([freq, num]);
        } else {
            // 如果当前频率大于堆顶的最小频率，则替换堆顶
            if (freq > minHeap.heap[0][0]) {
                minHeap.pop();
                minHeap.push([freq, num]);
            }
        }
    }

    // 从堆中取出所有元素（按频率从小到大，但本题不要求顺序）
    const result = [];
    while (minHeap.size() > 0) {
        result.push(minHeap.pop()[1]);
    }
    return result;
};

关键点：

• 手动实现最小堆，核心是 bubbleUp 和 sinkDown 方法。
• 维护大小为 k 的最小堆，堆顶是当前第 k 大的频率，当新元素频率大于堆顶时，替换堆顶并调整堆。

3. 单调队列类

核心解题思路

单调队列通常用双端队列（Deque）实现。队列中的元素保持单调递减（或递增）。当窗口滑动时，从队尾入队新元素，并移除所有比它小的元素以保持单调性；队首始终是当前窗口的最大值（或最小值）。同时，需要检查队首元素是否还在窗口内，否则弹出。

经典例题：239. 滑动窗口最大值

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const result = [];
    // 双端队列，存储元素的下标
    const deque = [];

    for (let i = 0; i < nums.length; i++) {
        // 1. 移除队尾比当前元素小的元素（保持队列递减）
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        // 2. 将当前元素下标加入队尾
        deque.push(i);

        // 3. 如果队首元素已经不在当前窗口内，移除
        if (deque[0] < i - k + 1) {
            deque.shift();
        }

        // 4. 当窗口形成后（i >= k-1），记录最大值
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
};

关键点：

• 使用双端队列存储下标，方便从两端操作。
• 队列始终保持单调递减，队首即为窗口最大值。
• 每次迭代都要检查队首是否过期（下标小于窗口左边界）。

4. 广度优先搜索（BFS）类

核心解题思路

BFS 通常使用队列进行层级遍历。对于图或矩阵的 BFS，需要标记已访问节点，防止重复访问。对于树的层次遍历，利用队列可以按层处理。

经典例题：102. 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (!root) return [];
    const result = [];
    const queue = [root]; // 队列初始包含根节点

    while (queue.length > 0) {
        const levelSize = queue.length; // 当前层的节点数
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift(); // 出队
            currentLevel.push(node.val);

            // 将下一层节点入队
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
    }

    return result;
};

关键点：

• 使用队列存储待访问节点。
• 在开始处理每一层之前，先记录当前队列的长度（即当前层的节点数），然后一次性处理完该层，保证 result 中每个子数组对应一层。
• shift() 操作在 JavaScript 中时间复杂度 O(n)，但如果队列很大可能影响性能，可以使用数组索引模拟队列（用两个指针）优化，但通常题目数据量下足够。

5. 双端队列（Deque）类

核心解题思路

双端队列允许在两端进行插入和删除操作。在 JavaScript 中，可以用数组模拟，但需要注意数组头部操作（unshift/shift）的时间复杂度为 O(n)。对于需要频繁头部操作的场景，可以手动实现链表或使用两个栈组合。但在 LeetCode 环境下，通常数组模拟即可。

经典例题：641. 设计循环双端队列

/**
 * 使用数组实现循环双端队列
 * @param {number} k
 */
var MyCircularDeque = function(k) {
    this.capacity = k + 1; // 浪费一个空间来区分队空和队满
    this.queue = new Array(this.capacity);
    this.front = 0; // 队首指针
    this.rear = 0;  // 队尾指针（指向下一个插入位置）
};

/** 
 * 从队首插入
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function(value) {
    if (this.isFull()) return false;
    this.front = (this.front - 1 + this.capacity) % this.capacity; // 前移
    this.queue[this.front] = value;
    return true;
};

/** 
 * 从队尾插入
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function(value) {
    if (this.isFull()) return false;
    this.queue[this.rear] = value;
    this.rear = (this.rear + 1) % this.capacity; // 后移
    return true;
};

/**
 * 删除队首元素
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function() {
    if (this.isEmpty()) return false;
    this.front = (this.front + 1) % this.capacity;
    return true;
};

/**
 * 删除队尾元素
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function() {
    if (this.isEmpty()) return false;
    this.rear = (this.rear - 1 + this.capacity) % this.capacity;
    return true;
};

/**
 * 获取队首元素
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function() {
    if (this.isEmpty()) return -1;
    return this.queue[this.front];
};

/**
 * 获取队尾元素（注意 rear 指向下一个插入位置，所以队尾元素是 rear-1）
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function() {
    if (this.isEmpty()) return -1;
    return this.queue[(this.rear - 1 + this.capacity) % this.capacity];
};

/** 
 * 判断队列是否为空
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function() {
    return this.front === this.rear;
};

/** 
 * 判断队列是否已满（浪费一个空间）
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function() {
    return (this.rear + 1) % this.capacity === this.front;
};

关键点：

• 循环队列通过取模运算实现循环。
• 浪费一个空间来区分队空和队满：队空条件 front == rear；队满条件 (rear+1) % capacity == front。
• 指针移动时需考虑循环。

6. 队列简单应用类

核心解题思路

这类题目直接利用队列的 FIFO 特性，模拟请求或操作。通常不需要复杂的数据结构，只需使用数组的 push（入队）和 shift（出队）即可。

经典例题：933. 最近的请求次数

var RecentCounter = function() {
    this.queue = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    // 将当前请求入队
    this.queue.push(t);
    // 移除所有在 [t-3000, t] 范围之外的请求
    while (this.queue[0] < t - 3000) {
        this.queue.shift();
    }
    // 队列长度即为最近请求次数
    return this.queue.length;
};

关键点：

• 队列中的请求时间天然有序（因为 ping 的 t 严格递增）。
• 每次调用 ping 时，只需将队首超出时间窗口的请求移除即可。
• 时间复杂度 O(1)（摊还），因为每个请求最多被移除一次。

总结

队列相关的题目主要围绕其 FIFO 特性展开，进阶应用包括：

• 优先队列：解决 Top K、调度问题。
• 单调队列：解决滑动窗口最值。
• BFS：解决层次遍历、最短路径、拓扑排序。
• 双端队列：允许两端操作，实现单调队列或循环队列。