面试数据结构：栈与队列

栈是后进先出，队列是先进先出。

栈

栈常用于括号匹配、表达式求值、递归模拟和单调栈。

std::stack<int> st;

队列

队列常用于 BFS。

std::queue<int> q;

单调栈

单调栈用于快速寻找下一个更大或更小元素。

核心是维护一个单调序列，每个元素最多入栈出栈一次，因此复杂度通常是 O(n)。

图片来源：Wikimedia Commons，栈结构示意图。

括号匹配

栈最经典的题是括号匹配。遇到左括号入栈，遇到右括号时检查栈顶是否匹配。

bool valid(std::string s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(') st.push(c);
        else {
            if (st.empty()) return false;
            st.pop();
        }
    }
    return st.empty();
}

真实题目会有三种括号，但核心不变。

队列与层次

队列常用来表达“按层推进”。BFS 不是简单地把 DFS 改成队列，它代表一种按距离从小到大扩展状态的方式。因此无权图最短路、迷宫最短步数这类题优先考虑 BFS。