Day 28 · 栈与队列：STL 容器

题意：实现一个栈，支持四种操作：

• push(x)：把 x 入栈。
• pop()：弹出栈顶。如果栈是空的，不做任何操作，输出 Empty。
• query()：输出栈顶元素。如果栈是空的，输出 Anguei!。
• size()：输出栈内元素个数。

思路

用 std::stack 直接做。要点有三个：

1. 数据类型用 unsigned long long，因为 x 可以到 2⁶⁴−1。

2. 每次 pop / query 之前都要判空，空的时候输出对应的字符串而不是去动栈。

3. 六种操作怎么区分。 这里有个陷阱：

2
5
push 2
query
size
pop
query
3
pop
query
size

2
1
Anguei!
Empty
Anguei!
0

第一组：push 2 → query 输出 2 → size 输出 1 → pop（成功，静默）→ query 时栈已空，输出 Anguei!
第二组：栈一直是空的，pop 输出 Empty，query 输出 Anguei!，size 输出 0。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);      // 数据量大，关掉同步更快
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){                       // ★ 多组数据
        int n;
        cin >> n;
        stack<unsigned long long> st;  // ★ x 可达 2^64-1，必须 ull
        while(n--){
            string op;
            cin >> op;
            // 注意：push / pop 都以 'p' 开头，query 缩写成 q，size 缩写成 s
            // 千万不能用 op[1] 区分 push 和 query —— "query"[1] 也是 'u'！
            if(op[0] == 'p'){
                if(op[1] == 'u'){          // push
                    unsigned long long x;
                    cin >> x;
                    st.push(x);
                }else{                     // pop
                    if(st.empty()) cout << "Empty\n";
                    else st.pop();
                }
            }else if(op[0] == 'q'){        // query
                if(st.empty()) cout << "Anguei!\n";
                else cout << st.top() << "\n";
            }else{                         // size
                cout << st.size() << "\n";
            }
        }
    }
    return 0;
}

易错点

• 用 int 或 long long 存 x → x 可以到 2⁶⁴−1，存不下。必须 unsigned long long。
• 用 op[1] 区分操作 → 会把 query 误判成 push（我实际踩过，会死循环）。要先看 op[0]。
• 忘记判空 → 对空栈 top() 是未定义行为，可能 RE。
• 注意两个字符串的拼写：Empty 没有感叹号，Anguei! 有感叹号。题目专门提醒过。
• 多组数据要重新声明栈：把 stack 定义在 while(T--) 循环里面， 否则上一组残留的数据会污染下一组。
• 不关 ios::sync_with_stdio 的话，10⁶ 次读入可能超时。

题意：实现一个队列。操作不是用字符串给的，而是用数字编号：

思路

纯模拟题，读一个操作号，分支处理即可。三个要点：

1. 操作 1 后面还跟着一个数 x，要接着读进来。

2. 操作 2 和 3 都要先判空，空的时候输出错误提示字符串。

3. 输出格式。 题目文字里有一句「每条输出之间应当用空行隔开」， 但官方样例输出里并没有空行。

13
1 2
3
4
1 233
3
2
3
2
4
3
2
1 144
3

2
1
2
233
0
ERR_CANNOT_QUERY
ERR_CANNOT_POP
144

逐步走一遍（题目提示里的解释）：
插入 2 → 队首是 2、个数 1 → 插入 233 → 队首还是 2（先进先出！）→ 弹出 → 队首变成 233 → 再弹出 → 队列空、个数 0 → 查询队首（空）报错 → 弹出（空）报错 → 插入 144 → 队首 144。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    queue<int> q;
    while(n--){
        int op;
        cin >> op;
        if(op == 1){
            int x;  cin >> x;              // ★ 操作 1 后面还有个数
            q.push(x);
        }else if(op == 2){
            if(q.empty()) cout << "ERR_CANNOT_POP\n";
            else q.pop();
        }else if(op == 3){
            if(q.empty()) cout << "ERR_CANNOT_QUERY\n";
            else cout << q.front() << "\n";  // ★ 队列用 front()，不是 top()
        }else{
            cout << q.size() << "\n";       // 操作 4：空队列也正常输出 0
        }
    }
    return 0;
}

易错点

• 把 front() 写成 top() → 编译报错（queue 没有 top）。
• 操作 1 忘了读 x → 后面的读入全部错位。
• 空队列时去 front() / pop() → 未定义行为。必须先判空。
• 操作 4 也去判空 → 空队列时 size 应该正常输出 0，不需要任何特殊处理。
• 两个错误字符串拼写要一字不差：ERR_CANNOT_POP 和 ERR_CANNOT_QUERY（都是大写 + 下划线）。

题意：给一个后缀表达式（逆波兰式），求它的值。运算符只有 + - * /。 操作数后面跟 . 表示这个数结束，整个表达式用 @ 结尾。 保证除法除数不为 0，且除法结果向 0 取整。

思路

一个栈搞定，从左往右扫字符串：

1. 读到 数字字符 → 拼到当前数字里：num = num * 10 + (c - '0')。
2. 读到 . → 一个数读完了，把 num 入栈，然后 num = 0 重新开始。
3. 读到 @ → 表达式结束，跳出循环。
4. 读到 运算符 → 先弹出的是右操作数，后弹出的是左操作数，算完把结果入栈。

循环结束后，栈顶就是答案。

3.5.2.-*7.+@

16

10.28.30./*7.-@

-7

样例 2 手推：10、28、30 依次入栈 → 遇 / 弹出 30 和 28， 算 28 / 30 = 0（整数除法）→ 入栈得到 [10, 0] → 遇 * 弹出 0 和 10， 算 10 × 0 = 0 → 入栈得到 [0] → 7 入栈得到 [0, 7] → 遇 - 弹出 7 和 0， 算 0 − 7 = −7。注意这里就是「先弹出的当右操作数」：0 − 7，不是 7 − 0。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;

    stack<long long> st;
    long long num = 0;                // 正在拼的数字

    for(size_t i = 0; i < s.size(); i++){
        char c = s[i];
        if(c >= '0' && c <= '9'){
            num = num * 10 + (c - '0');   // ★ 多位数：一位一位拼起来
        }else if(c == '.'){
            st.push(num);                 // 遇到 '.' 说明一个数读完了
            num = 0;
        }else if(c == '@'){
            break;                        // 表达式结束
        }else{                            // 运算符
            long long b = st.top(); st.pop();   // ★ 先弹出的是右操作数
            long long a = st.top(); st.pop();
            long long r = 0;
            if(c == '+')      r = a + b;
            else if(c == '-') r = a - b;
            else if(c == '*') r = a * b;
            else              r = a / b;  // C++ 的 / 本身就是向 0 取整
            st.push(r);
        }
    }

    cout << st.top() << "\n";
    return 0;
}

易错点

• 减法和除法把操作数顺序弄反 → 这是本题第一大 WA 原因。记住：先弹出的是右操作数。
• 多位数没处理 → 读到 10. 时只识别成 1，后面全乱。必须用 num * 10 + digit 累积。
• 读到 . 忘了把 num 清零 → 下一个数字会接在旧的后面（比如 12 之后读 3 会变成 123）。
• 用 cin >> s 读入是可行的（表达式里没有空格），但如果题目说「一行可能带空格」就得用 getline。
• 循环条件写成 i < s.size() 但忘了处理 @ → @ 会被当成运算符处理。要显式 break。
• 判断数字要用 c >= '0' && c <= '9'，不要用字符的 ASCII 码硬编码。

题意：表达式由数字、小写字母、运算符 + - * / 和左右小括号组成，以 @ 结尾。 判断圆括号是否匹配：匹配输出 YES，否则输出 NO。

只有圆括号要管，方括号、大括号题面里没有。

思路

用栈做（这是通用解法）：遇 ( 入栈；遇 ) 时先判空 —— 空说明右括号多了，立刻判 NO；不空就弹一个。扫完后再判一次栈是否为空，不空说明左括号多了。

2*(x+y)/(1-x)@

YES

(25+x)*(a*(a+b+b)@

NO

样例 1：两个 ( 两个 )，且顺序正确 → YES。
样例 2：有两个 ( 但只有一个 )，结束时栈里还剩一个 → NO。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;

    stack<char> st;
    bool ok = true;

    for(size_t i = 0; i < s.size(); i++){
        char c = s[i];
        if(c == '@') break;                 // 表达式结束
        if(c == '('){
            st.push(c);                     // 左括号入栈
        }else if(c == ')'){
            if(st.empty()){                 // ★ 右括号多了，当场判错
                ok = false;
                break;
            }
            st.pop();                       // 和栈顶的左括号配对
        }
    }

    if(!st.empty()) ok = false;             // ★ 左括号多了
    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

易错点

• 只在最后判一次栈是否为空，遇到 )( 这种会错判成 YES。必须在循环里对空栈判错。
• 对空栈调用 top() / pop() → 未定义行为。要先判空。
• 忘记在 @ 处停下 → 后面的字符会被当成表达式内容。
• 输出是 YES / NO，全大写，别写 Yes 或 yes。
• 题目说的是「左圆括号少于 20 个」，所以栈的深度很小，不用担心中间会爆栈。