题目描述
实现一个栈,栈初始为空,支持四种操作:
1.push x – 向栈顶插入一个数 x;
2.pop – 从栈顶弹出一个数;
3.empty – 判断栈是否为空;
4.query – 查询栈顶元素。
现在要对栈进行M个操作,其中的每个操作3和操作4都要输出相应的结果。
样例
输入样例:
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
输出样例:
5
5
YES
4
NO
算法1
(暴力枚举) $O(n)$
C++ 代码
#include <iostream>
using namespace std;
#define Max 100100
struct stack{
int arr[Max];
int top;
};
void init(struct stack* s){
s->top = -1;
}
void push(struct stack* s,int x){
s->arr[++s->top] = x;
}
bool empty(struct stack* s){
if(s->top==-1){
cout<<"YES"<<endl;
return true;
}
else{
cout<<"NO"<<endl;
return false;
}
}
bool pop(struct stack* s,int* x){
if(s->top == -1) return false;
else{
(*x) = s->arr[s->top];
s->top--;
}
return true;
}
bool query(struct stack* s,int* x){
if(s->top == -1) return false;
else{
(*x) = s->arr[s->top];
}
cout<<(*x)<<endl;
return true;
}
int main(){
struct stack s;
int x;
int num;
cin>>num;
init(&s);
string op;
int k;
while(num--){
cin>>op;
if(op == "push"){
cin>>k;
push(&s,k);
}
else if(op == "pop"){
pop(&s,&x);
}
else if(op == "empty"){
empty(&s);
}
else{
query(&s,&x);
}
}
return 0;
}