题解 | #【模板】栈的操作#
【模板】栈的操作
https://www.nowcoder.com/practice/cdf02ea916454957b575585634e5773a
题目链接
题目描述
你需要模拟一个整数栈的四种基本操作：
push x: 将整数x压入栈顶。pop: 弹出栈顶元素。如果栈为空，则输出 "Error"。query: 查询栈顶元素。如果栈为空，则输出 "Empty"。size: 输出栈中当前元素的数量。
输入格式
第一行是一个整数 n，表示操作的总次数。
接下来 n 行，每行是一个操作指令。
输出格式 根据操作指令，按顺序输出相应的结果，每个结果占一行。
解题思路
本题是数据结构中的经典问题，旨在熟悉"栈"（Stack）这一后进先出（Last-In, First-Out, LIFO）的数据结构。几乎所有现代编程语言的标准库都内置了高效的栈实现，我们直接使用即可。
-
选择数据结构:
- C++:
std::stack - Java:
java.util.ArrayDeque(官方推荐，比java.util.Stack更高效) 或java.util.Stack。 - Python:
list类型可以非常方便地作为栈来使用。
- C++:
-
主程序逻辑:
- 读入操作总数
n。 - 实例化一个栈对象。
- 进入一个循环，执行
n次。 - 在循环中，读取每一行的操作命令（如 "push", "pop" 等）。
- 读入操作总数
-
分发操作: 使用
if-else或switch语句根据读取到的命令字符串执行相应的栈操作：push x: 读取命令 "push" 及其后的整数x，调用栈的压入方法（push()/append()）将x入栈。pop:- 关键: 在执行
pop操作前，必须检查栈是否为空（empty()/isEmpty()/if not stack:）。 - 如果栈不为空，则调用弹出方法（
pop()）。 - 如果栈为空，则按题目要求输出 "Empty"。
- 关键: 在执行
query:- 同样，必须先检查栈是否为空。
- 如果栈不为空，则调用查询栈顶方法（
top()/peek()/stack[-1]）并输出结果。 - 如果栈为空，则按题目要求输出 "Empty"。
size: 直接调用获取大小的方法（size()/len()）并输出结果。
这个流程直接模拟了题目的要求，核心在于正确使用所选语言的栈API，并细心处理空栈的边界条件。
代码
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
stack<int> s;
string command;
for (int i = 0; i < n; ++i) {
cin >> command;
if (command == "push") {
int x;
cin >> x;
s.push(x);
} else if (command == "pop") {
if (s.empty()) {
cout << "Empty" << endl;
} else {
s.pop();
}
} else if (command == "query") {
if (s.empty()) {
cout << "Empty" << endl;
} else {
cout << s.top() << endl;
}
} else if (command == "size") {
cout << s.size() << endl;
}
}
return 0;
}
import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
String command = sc.next();
switch (command) {
case "push":
int x = sc.nextInt();
stack.push(x);
break;
case "pop":
if (stack.isEmpty()) {
System.out.println("Empty");
} else {
stack.pop();
}
break;
case "query":
if (stack.isEmpty()) {
System.out.println("Empty");
} else {
System.out.println(stack.peek());
}
break;
case "size":
System.out.println(stack.size());
break;
}
}
}
}
def main():
n = int(input())
stack = []
for _ in range(n):
line = input().split()
command = line[0]
if command == "push":
x = int(line[1])
stack.append(x)
elif command == "pop":
if not stack:
print("Empty")
else:
stack.pop()
elif command == "query":
if not stack:
print("Empty")
else:
print(stack[-1])
elif command == "size":
print(len(stack))
if __name__ == "__main__":
main()
算法及复杂度
- 算法: 基于标准库的栈进行模拟。
- 时间复杂度:
，其中
是操作的总次数。每一次
push,pop,query(top),size操作的摊销时间复杂度都是。
- 空间复杂度:
push），栈中会存储
韶音科技二面153人在聊
有没有加锁，要是你们同时加会出现库存为-1吗？