栈与队列

本章目标：理解栈和队列的本质，掌握括号匹配、表达式求值等经典应用。

你将学到

• 栈的 LIFO 特性与经典应用
• 队列的 FIFO 特性与 BFS
• 双端队列（Deque）
• 用栈实现队列、用队列实现栈
• 表达式求值（中缀转后缀）
• 最小栈设计

1. 概念

栈是后进先出（LIFO）的数据结构，像一摞盘子——最后放的最先拿。队列是先进先出（FIFO），像排队——先来的先服务。

栈的核心应用场景：函数调用栈、括号匹配、表达式求值、DFS 的非递归实现、撤销操作（Undo）。队列的核心应用：BFS、任务调度、消息缓冲。

Swift 中可以用数组模拟栈（append + popLast），也可以用数组模拟队列（但 removeFirst 是 O(n)，高效实现需要用双栈或环形数组）。

2. 核心模板

括号匹配

func isValid(_ s: String) -> Bool {
    let pairs: [Character: Character] = [")": "(", "]": "[", "}": "{"]
    var stack: [Character] = []
    for ch in s {
        if ch == "(" || ch == "[" || ch == "{" {
            stack.append(ch)
        } else {
            if stack.isEmpty || stack.last != pairs[ch] {
                return false
            }
            stack.removeLast()
        }
    }
    return stack.isEmpty
}

最小栈（O(1) 获取最小值）

class MinStack {
    private var stack: [(val: Int, minVal: Int)] = []

    func push(_ val: Int) {
        let minVal = stack.isEmpty ? val : min(val, stack.last!.minVal)
        stack.append((val: val, minVal: minVal))
    }

    func pop() {
        stack.removeLast()
    }

    func top() -> Int {
        return stack.last!.val
    }

    func getMin() -> Int {
        return stack.last!.minVal
    }
}

用两个栈实现队列

class MyQueue {
    private var inStack: [Int] = []
    private var outStack: [Int] = []

    func push(_ x: Int) {
        inStack.append(x)
    }

    private func transfer() {
        if outStack.isEmpty {
            while let val = inStack.popLast() {
                outStack.append(val)
            }
        }
    }

    func pop() -> Int {
        transfer()
        return outStack.removeLast()
    }

    func peek() -> Int {
        transfer()
        return outStack.last!
    }

    func empty() -> Bool {
        return inStack.isEmpty && outStack.isEmpty
    }
}

复杂度

• 括号匹配：时间 O(n)，空间 O(n)
• 最小栈：所有操作均摊 O(1)
• 双栈队列：均摊 O(1)

3. 经典题目精讲

LeetCode 150 · 逆波兰表达式求值

题意：给定后缀表达式（逆波兰表示法），求值。

思路：遇到数字入栈，遇到运算符弹两个出来算完再入栈。

func evalRPN(_ tokens: [String]) -> Int {
    var stack: [Int] = []
    for token in tokens {
        if let num = Int(token) {
            stack.append(num)
        } else {
            let b = stack.removeLast()
            let a = stack.removeLast()
            switch token {
            case "+": stack.append(a + b)
            case "-": stack.append(a - b)
            case "*": stack.append(a * b)
            case "/": stack.append(Int(a / b))  // 向零取整
            default: break
            }
        }
    }
    return stack.last!
}

LeetCode 239 · 滑动窗口最大值

题意：给定数组和窗口大小 k，返回每个窗口中的最大值。

思路：单调递减队列，队头始终是当前窗口最大值。

func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
    var result: [Int] = []
    var deque: [Int] = []  // 存索引，对应的值单调递减
    for i in 0..<nums.count {
        // 移除超出窗口的元素
        while let first = deque.first, first <= i - k {
            deque.removeFirst()
        }
        // 维护单调性：比当前元素小的都弹掉
        while let last = deque.last, nums[last] <= nums[i] {
            deque.removeLast()
        }
        deque.append(i)
        if i >= k - 1 {
            result.append(nums[deque.first!])
        }
    }
    return result
}

4. 易错点

• ⚠️ Swift 数组 removeFirst() 是 O(n)，高性能场景需用自定义双端队列
• ⚠️ 逆波兰除法在 Swift 中 / 对负数是向零取整，符合题意
• ⚠️ 表达式求值需注意运算符优先级和括号嵌套

5. 推荐刷题清单

题号	题名	难度	关键
20	有效的括号	Easy	栈
155	最小栈	Easy	辅助栈
232	用栈实现队列	Easy	双栈
239	滑动窗口最大值	Hard	单调队列
150	逆波兰表达式求值	Medium	后缀表达式

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS)