【模板】栈(Stack Template) 题解

思路分析

使用数组或 std::vector<unsigned long long> 模拟栈。注意两点易错细节：一是元素范围 $0 \le x < 2^{64}$，必须使用 unsigned long long；二是单测试点含多组数据，每组数据开始时必须将栈顶指针清零；此外空栈 pop 输出 Empty（无感叹号），空栈 query 输出 Anguei!（有感叹号）。时间复杂度 $O(\sum n)$。

参考代码

#include <iostream>
#include <string>
using namespace std;

const int MX = 1000005;
unsigned long long stk[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--)
    {
        int n;
        cin >> n;
        int top = 0;
        for (int i = 0; i < n; ++i)
        {
            string op;
            cin >> op;
            if (op[0] == 'p' && op[1] == 'u')
            {
                unsigned long long x;
                cin >> x;
                stk[++top] = x;
            }
            else if (op[0] == 'p')
            {
                if (top == 0) cout << "Empty\n";
                else --top;
            }
            else if (op[0] == 'q')
            {
                if (top == 0) cout << "Anguei!\n";
                else cout << stk[top] << "\n";
            }
            else
            {
                cout << top << "\n";
            }
        }
    }
    return 0;
}