Day 14 - 队列

📅 日期：2026年1月21日
🎯 主题：队列基础 + 用队列实现栈与单调队列

今日题目

题目1：用队列实现栈 (Implement Stack using Queues)

难度：⭐ 简单

链接：LeetCode 225. 用队列实现栈

题目描述

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

实现 MyStack 类：

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

注意：你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列，只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top();   // 返回 2
myStack.pop();   // 返回 2
myStack.empty(); // 返回 False

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

解题思路

方法一：两个队列，保持一个为空 ✅ 推荐

核心思想：

1. 使用两个队列 q1、q2，始终保证「有元素的那一个」的队尾就是栈顶
2. push(x)：将 x 加入当前有元素的那个队列（若都空则任选一个），即成为新的栈顶
3. top()：有元素队列的队尾就是栈顶；若用标准队列无法直接取队尾，可用「把除最后一个外的元素全部移到另一个队列」的方式，最后那个就是栈顶，再移回去
4. pop()：同样把除最后一个外的元素移到另一个队列，最后一个出队即为栈顶元素
5. empty()：两个队列都为空则栈为空

更简单的实现：每次 push 时把新元素放入空队列，再把另一队列中所有元素依次入队到该队列，这样新元素就在队头，等价于栈顶。

方法二：一个队列，push 时翻转

用一个队列，每次 push(x) 时先把 x 入队，再把队中已有的元素依次出队再入队，这样 x 就到了队头，即栈顶。pop/top 直接取队头即可。

代码实现

两个队列实现：

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

class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    // 保证新元素在队头（栈顶）：把新元素放入空队列，再把另一队列全部移过来
    public void push(int x) {
        if (q1.isEmpty()) {
            q1.offer(x);
            while (!q2.isEmpty()) {
                q1.offer(q2.poll());
            }
        } else {
            q2.offer(x);
            while (!q1.isEmpty()) {
                q2.offer(q1.poll());
            }
        }
    }

    public int pop() {
        if (!q1.isEmpty()) {
            return q1.poll();
        }
        return q2.poll();
    }

    public int top() {
        if (!q1.isEmpty()) {
            return q1.peek();
        }
        return q2.peek();
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}

一个队列实现（push 时翻转）：

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

class MyStack {
    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    // 新元素入队后，把原队列元素依次出队再入队，使新元素在队头
    public void push(int x) {
        int size = queue.size();
        queue.offer(x);
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

复杂度分析

• push：O(n)，需要把已有元素全部移动一次
• pop / top / empty：O(1)
• 空间复杂度：O(n)，队列中存储栈内元素

---

题目2：滑动窗口最大值 (Sliding Window Maximum)

难度：⭐⭐⭐ 困难

链接：LeetCode 239. 滑动窗口最大值

题目描述

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

返回 滑动窗口中的最大值。

示例：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

解题思路

方法一：单调队列 ✅ 推荐

核心思想：

1. 使用双端队列 deque 存储下标，且对应元素从队首到队尾单调递减（队首是当前窗口内最大值的下标）
2. 遍历数组，对于下标 i：
   • 若队首下标已不在窗口内（队首下标 <= i - k），从队首出队
   • 从队尾开始，若 nums[队尾下标] < nums[i]，则队尾出队（因为不可能再成为后面窗口的最大值），直到队空或队尾元素 >= nums[i]
   • 将 i 从队尾入队
   • 当窗口已形成（i >= k - 1）时，当前窗口最大值即为 nums[队首下标]，加入结果
3. 这样每个下标最多入队、出队各一次，总时间 O(n)。

关键点：

• 单调队列：队内按「下标」对应的「值」单调递减，队首即为当前窗口最大值
• 存下标方便判断是否还在窗口内
• 新元素从队尾比较并弹出比它小的，再入队，保证单调性

代码实现

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // 存下标，对应值单调递减

        for (int i = 0; i < n; i++) {
            // 队首下标超出窗口，弹出
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            // 队尾比当前元素小，不可能再成为最大值，弹出
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            // 窗口 [i-k+1, i] 已形成，队首即为最大值下标
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}

复杂度分析

• 时间复杂度：O(n)，每个下标最多入队、出队各一次
• 空间复杂度：O(k)，单调队列中最多 k 个下标

---

今日总结

学到了什么？

1. 用队列实现栈：通过「每次 push 时把新元素放到队头」或「两个队列倒腾」保证栈顶对应队头，从而用队列的 FIFO 模拟 LIFO
2. 单调队列：队内元素（或下标）保持单调性，队首即为当前窗口的最值，适用于滑动窗口最值问题
3. 双端队列：既可以从队首也可以从队尾出队，用于维护单调队列
4. 存下标不存值：方便判断下标是否还在窗口内，以及获取对应的值

关键技巧

技巧	适用场景	时间复杂度	空间复杂度
队列模拟栈	push 时翻转/双队列倒腾	push O(n)	O(n)
单调队列	滑动窗口最值	O(n)	O(k)
双端队列	需要两端弹出	O(1) 单次	O(k)
存下标	需要判断位置/窗口	-	-

队列操作要点

1. 队列基本操作：

   • offer(e) / add(e)：入队
   • poll() / remove()：出队（队首）
   • peek() / element()：查看队首不移除
   • isEmpty() / size()：判空、大小

2. 单调队列模式（滑动窗口最大值）：

   • 队内按值单调递减，队首为当前窗口最大值
   • 新元素从队尾比较，弹出比它小的再入队
   • 队首下标超出窗口则从队首出队
   • 窗口形成后（下标 >= k-1）每次取队首作为该窗口答案

3. 常见错误：

   • 用队列实现栈时，忘记在 push 时把栈顶维护到队头，导致 pop/top 不是 O(1) 或逻辑错误
   • 单调队列窗口边界写错（如 i - k 与 i - k + 1）
   • 存值不存下标导致无法判断是否在窗口内

相似题目推荐

• 用栈实现队列 - 栈与队列互相实现
• 设计循环队列 - 队列结构设计
• 队列的最大值 - 带最大值的队列
• 满足条件的子数组数目 - 双指针/单调性

明日计划

• Day 15 二叉树
• 练习：二叉树遍历、层序遍历（BFS 用队列）、递归与迭代写法