栈与队列

栈与队列

栈的定义与基本操作；队列的定义与基本操作。

概念

栈（Stack）只允许在一端（栈顶）插入和删除，遵循后进先出（LIFO）。队列（Queue）在一端入队、另一端出队，遵循先进先出（FIFO）。二者都是线性表上的操作受限，可用数组或链表实现。栈常用于表达式求值、括号匹配、深度优先搜索的辅助结构；队列常用于广度优先搜索、按到达顺序处理任务。与 cspj.ds.linked-list 相邻——实现栈队列常基于链表或数组，但考点是访问规则而非链式存储本身；与 cspj.algo.dfs-bfs 有交集，初赛更爱直接考出栈序列合法性、后缀表达式或栈+队列混合模拟。

CSP-J 常考

• cspj-r1-2021 第 5 题：给定入栈顺序，判断哪一个不是合法出栈序列。
• cspj-r1-2022 第 2 题：按固定顺序进栈，选非法的出栈序列（经典卡特兰约束）。
• cspj-r1-2022 第 5 题：栈与队列操作交错进行，根据最终出队顺序反推栈的最小容量。
• cspj-r1-2023 第 8 题：给后缀表达式，还原对应的中缀表达式（栈的经典应用）。
• cspj-r2-2020 第 3 题（表达式）：后缀逻辑表达式 &、|、!，用栈求值并处理「临时取反某一变量」的多次询问。

#include <stack>
using namespace std;

// 用栈把后缀算术式 "3 4 +" 求值（操作数与运算符用空格分隔）
int evalRpn(const string& s) {
    stack<int> st;
    // 简例：手工把 "3 4 +" 拆成 token 处理
    st.push(3); st.push(4);
    int b = st.top(); st.pop();
    int a = st.top(); st.pop();
    st.push(a + b);
    return st.top();
}

易错点

• 判断出栈序列：某元素出栈后，栈中尚未出栈的元素相对顺序不能颠倒。
• 后缀转中缀：遇到运算符先弹右操作数再弹左操作数，顺序反了括号就错。
• 「栈无法用两个栈实现队列」是错的——双栈可以模拟队列；选「本质不同、无法实现」的选项要警惕。
• 栈+队列混合题要按题意逐步模拟，不要凭直觉猜最终顺序。