B3614 【模板】栈——题解

思路

用一个数组模拟栈，再用变量 top 表示栈内元素个数：

• 入栈：先让 top 加一，再把新数放到 a[top]；
• 出栈：若 top>0，直接让 top 减一；
• 查询：若 top>0，栈顶就是 a[top]；
• 大小：直接输出 top。

每组数据开始前把 top 重新设为 $0$。由于 $x$ 可能接近 $2^{64}$，数组元素必须使用 unsigned long long。

复杂度

每条操作的时间复杂度为 $O(1)$；数组最大占用 $O(\sum n)$ 级别空间，本代码固定开到 $10^6$。

参考代码

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

const int N = 1000005;
unsigned long long a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, top = 0;
        cin >> n;
        while (n--) {
            string op;
            cin >> op;
            if (op == "push") {
                unsigned long long x;
                cin >> x;
                a[++top] = x;
            } else if (op == "pop") {
                if (top == 0) cout << "Empty\n";
                else top--;
            } else if (op == "query") {
                if (top == 0) cout << "Anguei!\n";
                else cout << a[top] << '\n';
            } else {
                cout << top << '\n';
            }
        }
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; const int N = 1000005; unsigned long long a[N]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin>>T; while(T--){ int n,top=0; cin>>n; while(n--){ string op; cin>>op; if(op=="push"){ unsigned long long x; cin>>x; a[++top]=x; }else if(op=="pop"){ if(top0) cout<<"Empty\n"; else top--; }else if(op"query"){ if(top==0) cout<<"Anguei!\n"; else cout<<a[top]<<'\n'; }else{ cout<<top<<'\n'; } } } return 0; }