基于容器适配器的栈/队列高效解法

1. 双栈实现队列（LeetCode 232）

问题：用两个栈实现先进先出队列，支持push, pop, peek, empty操作。
解法：

• 输入栈in_stack处理push操作
• 输出栈out_stack处理pop/peek操作
• 当out_stack为空时，将in_stack元素全部弹出压入out_stack

时间复杂度：

• 均摊$O(1)$
• 空间复杂度$O(n)$

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

    def _transfer(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

---

2. 双队列实现栈（LeetCode 225）

问题：用两个队列实现后进先出栈，支持push, pop, top, empty操作。
解法：

• 主队列q1存储元素，辅助队列q2用于转移
• push时直接加入q1
• pop时将q1前$n-1$个元素移入q2，弹出最后一个元素

时间复杂度：

• pop操作$O(n)$
• 空间复杂度$O(n)$

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q1.append(x)

    def pop(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        res = self.q1.popleft()
        self.q1, self.q2 = self.q2, self.q1  # 交换队列
        return res

    def top(self) -> int:
        return self.q1[-1] if self.q1 else None

    def empty(self) -> bool:
        return not self.q1

---

3. 最小栈（LeetCode 155）

问题：实现能在$O(1)$时间内检索最小元素的栈。
解法：

• 主栈存储元素
• 辅助栈同步存储当前最小值
• 辅助栈栈顶恒为当前最小值

时间复杂度：

• 所有操作$O(1)$
• 空间复杂度$O(n)$

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

---

4. 单调队列解滑动窗口最大值（LeetCode 239）

问题：求数组每个滑动窗口$k$中的最大值。
解法：

• 使用双端队列维护单调递减索引
• 队首存储当前窗口最大值索引
• 移除超出窗口范围或小于新元素的索引

时间复杂度：

• $O(n)$
• 空间复杂度$O(k)$

from collections import deque

def maxSlidingWindow(nums: list, k: int) -> list:
    dq = deque()
    res = []
    for i in range(len(nums)):
        # 移除超出窗口的索引
        if dq and dq[0] == i - k:
            dq.popleft()
        # 维护单调递减性
        while dq and nums[i] >= nums[dq[-1]]:
            dq.pop()
        dq.append(i)
        # 记录窗口最大值
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

---

关键优化思想

1. 状态同步：双栈/双队列需保持操作后状态一致
2. 惰性转移：元素转移在必要时进行（如双栈队列的_transfer）
3. 单调性维护：单调栈/队列通过移除无效元素保持有序性
4. 索引存储：滑动窗口问题存储索引而非值，便于范围检查

这些方法在算法竞赛和工程中广泛应用，能显著提升容器操作效率。