队列高频面试题全解析：7道必刷题目+详细解题思路-菜鸟笔记

队列（Queue）是一种先进先出（FIFO）的数据结构，在算法面试中被广泛考察。本文精选 7 道 LeetCode 高频队列题目，涵盖设计题、单调队列、优先队列等核心场景，每题附解题思路与完整 C++ 实现。

一、用栈实现队列简单

LeetCode 232. 用栈实现队列

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

void push(x)：将元素 x 推到队列的末尾
int pop()：从队列的开头移除并返回元素
in peek()：返回队列开头的元素
bool empty()：如果队列为空，返回 true；否则，返回 false

解题思路

使用两个栈 s_in 和 s_out：

入队：直接压入 s_in
出队/查看队头：若 s_out 为空，将 s_in 中所有元素倒入 s_out，再从 s_out 取顶；否则直接取 s_out 栈顶

关键：每个元素最多被”倒”一次，均摊时间复杂度为 O(1)。

入队: push(1) push(2) push(3)
s_in: [1, 2, 3]   s_out: []

出队: pop()
s_in: []   s_out: [3, 2, 1]  → 弹出 1

C++ 实现

class MyQueue {

private:
    stack<int> s_in, s_out;

    void transfer() {

        if (s_out.empty()) {

            while (!s_in.empty()) {

                s_out.push(s_in.top());
                s_in.pop();
            }
        }
    }

public:
    MyQueue() {
  }

    void push(int x) {

        s_in.push(x);
    }

    int pop() {

        transfer();
        int val = s_out.top();
        s_out.pop();
        return val;
    }

    int peek() {

        transfer();
        return s_out.top();
    }

    bool empty() {

        return s_in.empty() && s_out.empty();
    }
};

复杂度分析

时间复杂度：O(1)
空间复杂度：O(n)

二、用队列实现栈简单

LeetCode 225. 用队列实现栈

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，支持 push、pop、top、empty 操作。

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
bool empty() 如果栈是空的，返回 true ；否则，返回 false 。

解题思路

单队列方案（推荐）：每次 push 后，将队列中新元素之前的所有元素依次出队再入队，使新元素始终位于队头，从而模拟栈的 LIFO 特性。

push(1): q = [1]
push(2): q = [2, 1]  (将 1 移到 2 后面)
push(3): q = [3, 2, 1]
pop():   返回 3，q = [2, 1]

C++ 实现

class MyStack {

private:
    queue<int> q;

public:
    MyStack() {
  }

    void push(int x) {

        q.push(x);
        // 将 x 之前的所有元素移到 x 后面
        for (int i = 0; i < (int)q.size() - 1; i++) {

            q.push(q.front());
            q.pop();
        }
    }

    int pop() {

        int val = q.front();
        q.pop();
        return val;
    }

    int top() {

        return q.front();
    }

    bool empty() {

        return q.empty();
    }
};

复杂度分析

时间复杂度：push O(n)，其余 O(1)
空间复杂度：O(n)

三、设计循环队列中等

LeetCode 622. 设计循环队列

题目描述

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
设计你的循环队列实现，需要支持以下操作：

enQueue(value)：向循环队列插入一个元素，如果成功插入则返回真。
deQueue()：从循环队列中删除一个元素，如果成功插入则返回真。
Front()：从队首获取元素，如果队列为空，返回 -1 。
Rear()：获取队尾元素，如果队列为空，返回 -1 。
isEmpty()/isFull()：检查是否为空/满

解题思路

使用数组 + 首尾指针实现循环队列：

维护 head（队首索引）、tail（下一个可写位置）、size（当前元素个数）
入队：data[tail] = val; tail = (tail + 1) % capacity
出队：head = (head + 1) % capacity
用 size 判断空满，避免首尾指针重合时的歧义

容量 3 的循环队列：
enQueue(1): [1, _, _]  head=0, tail=1
enQueue(2): [1, 2, _]  head=0, tail=2
enQueue(3): [1, 2, 3]  head=0, tail=0 (循环)
deQueue():  [_, 2, 3]  head=1, tail=0
enQueue(4): [4, 2, 3]  head=1, tail=1

C++ 实现

class MyCircularQueue {

private:
    vector<int> data;
    int head, tail, size, capacity;

public:
    MyCircularQueue(int k) : data(k), head(0), tail(0), size(0), capacity(k) {
  }

    bool enQueue(int value) {

        if (isFull()) return false;
        data[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    bool deQueue() {

        if (isEmpty()) return false;
        head = (head + 1) % capacity;
        size--;
        return true;
    }

    int Front() {

        return isEmpty() ? -1 : data[head];
    }

    int Rear() {

        return isEmpty() ? -1 : data[(tail - 1 + capacity) % capacity];
    }

    bool isEmpty() {
   return size == 0; }

    bool isFull() {
   return size == capacity; }
};

复杂度分析

时间复杂度：O(1)
空间复杂度：O(n)

四、设计循环双端队列中等

LeetCode 641. 设计循环双端队列

题目描述

设计实现双端队列，支持从两端进行插入和删除：

insertFront()：将元素添加到双端队列头部，如果操作成功返回 true ，否则返回 false 。
insertLast()：将元素添加到双端队列尾部，如果操作成功返回 true ，否则返回 false 。
deleteFront()/deleteLast()：删除头/尾元素，如果操作成功返回 true ，否则返回 false 。
getFront()/getRear()：获取头/尾元素，如果操作成功返回 true ，否则返回 false 。
bool isEmpty()/isFull()：检查双端队列为空/满。

解题思路

在循环队列基础上扩展，支持双端操作：

头部插入：head = (head - 1 + capacity) % capacity，再写入
尾部删除：tail = (tail - 1 + capacity) % capacity

注意取模时加 capacity 防止负数越界。

C++ 实现

class MyCircularDeque {

private:
    vector<int> data;
    int head, tail, size, capacity;

public:
    MyCircularDeque(int k) : data(k), head(0), tail(0), size(0), capacity(k) {
  }

    bool insertFront(int value) {

        if (isFull()) return false;
        head = (head - 1 + capacity) % capacity;
        data[head] = value;
        size++;
        return true;
    }

    bool insertLast(int value) {

        if (isFull()) return false;
        data[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    bool deleteFront() {

        if (isEmpty()) return false;
        head = (head + 1) % capacity;
        size--;
        return true;
    }

    bool deleteLast() {

        if (isEmpty()) return false;
        tail = (tail - 1 + capacity) % capacity;
        size--;
        return true;
    }

    int getFront() {

        return isEmpty() ? -1 : data[head];
    }

    int getRear() {

        return isEmpty() ? -1 : data[(tail - 1 + capacity) % capacity];
    }

    bool isEmpty() {
   return size == 0; }
    bool isFull()  {
   return size == capacity; }
};

复杂度分析

时间复杂度：O(1)
空间复杂度：O(n)

五、设计前中后队列中等

LeetCode 1670. 设计前中后队列

题目描述

请你设计一个队列，支持在前、中、后三个位置的 push 和 pop 操作：

pushFront(val)/pushMiddle(val)/pushBack(val)
popFront()/popMiddle()/popBack()

“中间”定义：若长度为偶数，取偏左的那个中间位置。

解题思路

使用两个双端队列（left 和 right）维护”左半”和”右半”，保持以下平衡条件：

left.size() == right.size() 或 left.size() == right.size() + 1

每次操作后调用 balance() 重新平衡两个队列，中间元素即 left 的尾部。

pushBack(1): left=[1]  right=[]
pushBack(2): left=[1]  right=[2]
pushBack(3): left=[1,2] right=[3]
pushMiddle(4): 插入left尾 → left=[1,4] right=[2,3] (balance后)
popMiddle(): 取left尾 4 → left=[1] right=[2,3] → balance → left=[1,2] right=[3]

C++ 实现

class FrontMiddleBackQueue {

private:
    deque<int> left, right;

    // 保持 left.size() == right.size() 或 left.size() == right.size() + 1
    void balance() {

        if (left.size() > right.size() + 1) {

            right.push_front(left.back());
            left.pop_back();
        } else if (right.size() > left.size()) {

            left.push_back(right.front());
            right.pop_front();
        }
    }

public:
    FrontMiddleBackQueue() {
  }

    void pushFront(int val) {

        left.push_front(val);
        balance();
    }

    void pushMiddle(int val) {

        if (left.size() == right.size()) {

            // n 为偶数，插入位置下标 = n/2，即 left 当前尾部后
            left.push_back(val);
        } else {

            // n 为奇数，插入位置下标 = n/2 = left.size()-1，即 left.back() 之前
            // 做法：保存并弹出 left.back()，push val，再把原 back 压回
            int mid = left.back();
            left.pop_back();
            left.push_back(val);
            left.push_back(mid);
            balance(); // left 变为 right+2，需移 1 个到 right
        }
    }

    void pushBack(int val) {

        right.push_back(val);
        balance();
    }

    int popFront() {

        if (left.empty() && right.empty()) return -1;
        int val;
        if (!left.empty()) {

            val = left.front();
            left.pop_front();
        } else {

            val = right.front();
            right.pop_front();
        }
        balance();
        return val;
    }

    int popMiddle() {

        if (left.empty() && right.empty()) return -1;
        int val = left.back();
        left.pop_back();
        balance();
        return val;
    }

    int popBack() {

        if (left.empty() && right.empty()) return -1;
        int val;
        if (!right.empty()) {

            val = right.back();
            right.pop_back();
        } else {

            val = left.back();
            left.pop_back();
        }
        balance();
        return val;
    }
};

复杂度分析

时间复杂度：O(1)
空间复杂度：O(n)

六、绝对差不超过限制的最长连续子数组中等

LeetCode 1438. 绝对差不超过限制的最长连续子数组

题目描述

给你一个整数数组 nums 和一个整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或等于 limit。

示例：nums = [8,2,4,7]，limit = 4，输出 2（子数组 [2,4] 或 [4,7]）

[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此，满足题意的最长子数组的长度为 2 。

解题思路

滑动窗口 + 单调双端队列：

在窗口 [left, right] 中，我们只需知道窗口的最大值和最小值，若 max - min > limit，则移动左指针缩小窗口。

用两个单调队列维护：

maxQ：单调递减队列，队头始终是窗口最大值
minQ：单调递增队列，队头始终是窗口最小值

用两个单调队列分别”监视”窗口的最大值和最小值，新元素进来时踢掉”没用的旧元素”，左指针移动时踢掉”过期的元素”，从而 O(1) 随时获取窗口极值，整体 O(n) 解决问题。

通俗解释

滑动窗口 = 临时组队
把整个数组想象成一排人，我们要从中选连续的一小队人（窗口），要求这队里最高的和最矮的身高差不超过 limit。

右指针 right：逐个拉人进队（遍历数组，把当前元素加入窗口）；
左指针 left：如果队内身高差超标了，就把队最左边的人踢出去（缩小窗口），直到身高差符合要求；
我们的目标：找到能凑出的最长的队伍。

单调双端队列 = 记录 “最值候选人”
如果每次加新人后，都挨个比一遍队内所有人的身高找最高 / 最矮，效率太低。我们用两个 “特殊排队本”（单调队列）来记关键人，避免重复比较：

maxQ（单调递减队列）：记 “身高大佬”
这个本子只记队内身高从高到低的人，队头是当前队内最高的。
- 加新人时：如果新人比本子最后一个人高，就把最后这个人划掉（因为新人更高，后续找最高时轮不到他了），直到本子里的人都比新人高，再把新人记在最后；
- 比如：队内已有 [8,4,2]，加新人 7。本子里最后一个是 2（比 7 小，划掉）→ 4（比 7 小，划掉）→ 8（比 7 大），最终本子变成 [8,7]；
- 这样一来，本子第一个人永远是当前队内最高的，不用挨个比。
minQ（单调递增队列）：记 “身高小趴菜”
这个本子只记队内身高从低到高的人，队头是当前队内最矮的。
- 加新人时：如果新人比本子最后一个人矮，就把最后这个人划掉（因为新人更矮，后续找最矮时轮不到他了），直到本子里的人都比新人矮，再把新人记在最后；
- 比如：队内已有 [2,4,8]，加新人 1。本子里最后一个是 8（比 1 大，划掉）→ 4（比 1 大，划掉）→ 2（比 1 大，划掉），最终本子变成 [1]；
- 这样一来，本子第一个人永远是当前队内最矮的。

核心操作流程

初始化：左指针 left 站在队伍最左边，两个本子都是空的，最长队伍长度 ans = 0；
右指针 right 开始拉人：
- 把当前人（nums[right]）按规则加入 maxQ 和 minQ；
- 检查：当前队内最高（maxQ 队头）和最矮（minQ 队头）的差是否超过 limit；
  - 如果超了：把队最左边的人（nums[left]）踢出去，left 右移一步，(left++) —— 如果这个人正好是 maxQ 队头 / minQ 队头，也要从对应本子里删掉，重复检查直到差不超标；
  - 如果没超：看看当前队伍长度（right-left+1）是不是比之前最长的还长，更新 ans ；
遍历完所有人后，ans 就是答案。

为什么不会漏掉正确答案？
左指针右移时，被踢出窗口的元素，已经确定无法再让窗口变长了（因为它导致了违规），所以不会漏解。

right=0, 加入 8：
  maxQ: [0(8)]   minQ: [0(8)]
  窗口最大=8, 最小=8, 差=0   left=0, 长度=1

right=1, 加入 2：
  maxQ: 2<8，直接加 → [0(8), 1(2)]
  minQ: 2<8，踢掉8 → [1(2)]
  窗口最大=8, 最小=2, 差=6 > 4 
  → left右移到1，检查队头：maxQ队头是0 < left=1，踢掉 → maxQ:[1(2)]
  窗口最大=2, 最小=2, 差=0   长度=1

right=2, 加入 4：
  maxQ: 4>2，踢掉2 → [2(4)]
  minQ: 4>2，直接加 → [1(2), 2(4)]
  窗口最大=4, 最小=2, 差=2   left=1, 长度=2  ← 当前最优

right=3, 加入 7：
  maxQ: 7>4，踢掉4 → [3(7)]
  minQ: 7>4，直接加 → [1(2), 2(4), 3(7)]
  窗口最大=7, 最小=2, 差=5 > 4 
  → left右移到2，minQ队头是1 < left=2，踢掉 → minQ:[2(4), 3(7)]
  窗口最大=7, 最小=4, 差=3   长度=2

最终答案 = 2

C++ 实现

class Solution {

public:
    int longestSubarray(vector<int>& nums, int limit) {

        deque<int> maxQ, minQ; // 存储下标
        int left = 0, ans = 0;

        for (int right = 0; right < (int)nums.size(); right++) {

            // 维护单调递减队列（队头为最大值）
            while (!maxQ.empty() && nums[maxQ.back()] <= nums[right])
                maxQ.pop_back();
            maxQ.push_back(right);

            // 维护单调递增队列（队头为最小值）
            while (!minQ.empty() && nums[minQ.back()] >= nums[right])
                minQ.pop_back();
            minQ.push_back(right);

            // 若当前窗口不满足条件，收缩左边界
            while (nums[maxQ.front()] - nums[minQ.front()] > limit) {

                left++;
                if (maxQ.front() < left) maxQ.pop_front();
                if (minQ.front() < left) minQ.pop_front();
            }

            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

七、滑动窗口最大值困难

LeetCode 239. 滑动窗口最大值

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字，滑动窗口每次只向右移动一位。返回滑动窗口中的最大值数组。

示例：nums = [1,3,-1,-3,5,3,6,7]，k = 3，输出 [3,3,5,5,6,7]

解题思路

单调递减双端队列（经典模板题）：

维护一个单调递减队列，队头始终是当前窗口的最大值下标：

新元素入队前，从队尾弹出所有比新元素小的下标（它们永远不会是最大值）
检查队头是否已超出窗口范围，若超出则弹出
每当窗口长度达到 k，记录队头元素为当前窗口最大值

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0: deque=[0(1)]
i=1: 3>1，弹出0 → deque=[1(3)]
i=2: -1<3 → deque=[1(3), 2(-1)]，窗口满 → 输出 nums[1]=3
i=3: -3<-1 → deque=[1(3),2(-1),3(-3)]，队头1未过期 → 输出 3
i=4: 5>-3,5>-1,5>3 → deque=[4(5)]，输出 5
...

C++ 实现

class Solution {

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        deque<int> dq; // 存储下标，单调递减
        vector<int> result;

        for (int i = 0; i < (int)nums.size(); i++) {

            // 1. 弹出队尾中所有比 nums[i] 小的元素
            while (!dq.empty() && nums[dq.back()] <= nums[i])
                dq.pop_back();
            dq.push_back(i);

            // 2. 弹出已不在窗口内的队头
            if (dq.front() < i - k + 1)
                dq.pop_front();

            // 3. 窗口满时记录最大值
            if (i >= k - 1)
                result.push_back(nums[dq.front()]);
        }

        return result;
    }
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

核心思想：单调队列保证每个元素最多入队出队各一次，线性时间内解决了朴素 O(nk) 的问题。

队列高频面试题全解析：7道必刷题目+详细解题思路

一、用栈实现队列简单

题目描述

解题思路

C++ 实现

二、用队列实现栈简单

题目描述

解题思路

C++ 实现

三、设计循环队列中等

题目描述

解题思路

C++ 实现

四、设计循环双端队列中等

题目描述

解题思路

C++ 实现

五、设计前中后队列中等

题目描述

解题思路

C++ 实现

六、绝对差不超过限制的最长连续子数组中等

题目描述

解题思路

通俗解释

C++ 实现

七、滑动窗口最大值困难

题目描述

解题思路

C++ 实现

菜鸟笔记

热门教程

推荐教程

一、用栈实现队列 简单

题目描述

解题思路

C++ 实现

二、用队列实现栈 简单

题目描述

解题思路

C++ 实现

三、设计循环队列 中等

题目描述

解题思路

C++ 实现

四、设计循环双端队列 中等

题目描述

解题思路

C++ 实现

五、设计前中后队列 中等

题目描述

解题思路

C++ 实现

六、绝对差不超过限制的最长连续子数组 中等

题目描述

解题思路

通俗解释

C++ 实现

七、滑动窗口最大值 困难

题目描述

解题思路

C++ 实现

菜鸟笔记

热门教程

推荐教程

一、用栈实现队列简单

二、用队列实现栈简单

三、设计循环队列中等

四、设计循环双端队列中等

五、设计前中后队列中等

六、绝对差不超过限制的最长连续子数组中等

七、滑动窗口最大值困难