- [//]: # (推荐题解模板,请替换blablabla等内容 ^^)
题目描述
实现一个栈,栈初始为空,支持四种操作:
(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
关注走起~~~
思路
栈的思路很明确,他是一种先进后出的模型
利用数组进行模拟
因为操作的都是栈顶元素,所以只需要一个尾部指针tt来指向栈顶元素即可
tt = -1 即表示空,同时当插入一个元素,tt+1,指向当前栈顶元素,比如插入1,栈顶元素在数组中的位置为0
初始化
tt = -1
stack = [0, 0, 0]
操作1 push 1, 2
插入1
stack = [1, 0, 0]
tt = 0
插入2
stack = [1, 2, 0]
tt = 1
操作2 pop 1, 2, 3
取出栈顶元素1
stack = [1, 0, 0]
tt = 0
取出栈顶元素2
stack = [0. 0. 0]
tt = -1
栈为空,栈中不存在元素3
java
import java.io.*;
public class Main{
static int m;
static int N = 100010;
static int[] stack = new int[N];
static int tt = -1;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
m = Integer.parseInt(br.readLine());
while(m -- > 0){
int x;
String[] s = br.readLine().split(" ");
String opt = s[0];
if(opt.equals("push")){
x = Integer.parseInt(s[1]);
stack[++ tt] = x;
}else if(opt.equals("pop")){
if(tt != -1) tt --;
}else if(opt.equals("empty")){
if(tt == -1) System.out.println("YES");
else System.out.println("NO");
}else{
System.out.println(stack[tt]);
}
}
}
}
python3
N = 100010
stack = [0] * N
tt = -1
def main():
global stack, tt
m = int(input())
while(m):
m -= 1
s = list(input().split(" "))
opt = s[0]
if(opt == "push"):
x = s[1]
tt += 1
stack[tt] = x
elif(opt == "pop"):
if(tt != -1): tt -= 1
elif(opt == "empty"):
if(tt == -1): print("YES")
else: print("NO")
else:
print(stack[tt])
main()
c++
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int stack[N], tt = -1; //tt = -1表示栈中没有元素
int main(){
cin >> m;
while(m --){
string opt;
int x;
cin >> opt;
if(opt == "push"){
cin >> x;
stack[++ tt] = x;
}
else if(opt == "pop"){
if(tt != -1) tt --;
}
else if(opt == "empty"){
if(tt == -1) cout<< "YES" << endl;
else cout<< "NO" << endl;
}
else{
cout<< stack[tt] << endl;
}
}
return 0;
}