题目描述

实现一个栈，栈初始为空，支持四种操作：

(1) “push x” – 向栈顶插入一个数x；

(2) “pop” – 从栈顶弹出一个数；

(3) “empty” – 判断栈是否为空；

(4) “query” – 查询栈顶元素。

现在要对栈进行M个操作，其中的每个操作3和操作4都要输出相应的结果。

输入格式
第一行包含整数M，表示操作次数。

接下来M行，每行包含一个操作命令，操作命令为”push x”，”pop”，”empty”，”query”中的一种。

输出格式
对于每个”empty”和”query”操作都要输出一个查询结果，每个结果占一行。

其中，”empty”操作的查询结果为“YES”或“NO”，”query”操作的查询结果为一个整数，表示栈顶元素的值。

数据范围
1≤M≤100000,
1≤x≤109
所有操作保证合法。

样例

输入样例：
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
输出样例：
5
5
YES
4
NO

算法讲解

首先，这道题通过题目就可以知道，我们要做一个用来模拟栈的程序。

这道题有四个命令：

(1) “push x” – 向栈顶插入一个数x；

(2) “pop” – 从栈顶弹出一个数；

(3) “empty” – 判断栈是否为空；

(4) “query” – 查询栈顶元素。

我们一个个来分析。
分析前提：我们将stk数组作为栈，tt作为控制栈的指针（由下到上）。

第一个命令：“push x”

作用：向栈顶插入x。

实现方法：将x插入stk[tt]中，并将tt加1.

注意：建议先加tt,再将x插入到stk[tt]中。因为如果后加tt，就会导致pop命令与query命令出错（stk[tt]是空的，stk[tt-1]才是栈顶）。

解释：因为tt是从下到上控制的，所以stk[tt]永远都是栈顶。（tt在栈的最顶端）

第二个命令：“pop”

作用：从栈顶弹出一个数

实现方法：将tt减去1

解释：因为栈只有一个口，所以只能弹出栈顶的数。但是不需删除stk[tt]，因为在新的push命令执行时，stk[tt]会自动换成最新输入的数。所以只需将tt减去1，就可以达到与删除stk[tt]一样的效果。 ``

第三个命令：“empty”

作用：判断栈是否为空。

实现方法：判断tt是否大于0，如果为真，则stk不为空；如果为假，则stk为空。

解释：因为tt是从下到上控制栈的指针。如果stk一层都没有，那么stk当然是空的。

第四个命令：“query”

作用：查询栈顶元素

实现方法：输出stk[tt]。

解释：因为stk[tt]永远是栈顶，所以输出即可。

程序预览

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const int N=100010;
int stk[N],tt;//定义栈与指针
int m;
int quick_read(){//快读，可以选择使用cin（在这里就不讲了）
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
        x=x*10+(ch-'0'),ch=getchar();
    return x*f;
}
int main(){
    cin>>m;//输入查询次数
    while(m--){//开始查询
        string str;
        cin>>str;//输入命令
        //判断命令
        if(str=="push")
            stk[++tt]=quick_read() //插入数至栈顶
        else if(str=="pop")
            tt--; //弹出栈顶
        else if(str=="empty")
            if(tt>0) //判断栈是否为空
                cout<<"NO\n";
            else
                cout<<"YES\n";
        else if(str=="query")
            cout<<stk[tt]<<'\n'; //输出栈顶
    }
    return 0;
}