AcWing 828. 模拟栈-两种实现(数组、链表)
原题链接
简单
作者:
哥哥_7
,
2021-01-29 17:19:38
,
所有人可见
,
阅读 298
C++ 代码
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 5;
// 数组实现
class stack{
public:
void push(int x){
s[++t] = x;
}
void pop(){
t--;
}
bool empty(){
if(t == -1) return true;
else return false;
}
int top(){
return s[t];
}
private:
int s[N];
int t = -1;
};
// 链表实现
class mystack{
private:
struct Node{
int val;
Node* next;
};
Node* head = new Node(); //不存东西 只做指向
public:
void push(int x){
Node* node = (Node*)malloc(sizeof(struct Node));
node->val = x;
node->next = head->next; // 指向首元结点
head->next = node; // 更新首元结点
}
void pop(){
if(empty()) return ;
Node* tmp = head->next;
head->next = head->next->next;
free(tmp);
}
bool empty(){
return head->next?false:true;
}
int top(){
if(!empty()) return head->next->val;
}
};
int main(){
int m;
cin >> m;
mystack s;
for(int i = 0; i < m; i++){
string op;
int x;
cin >> op;
if(op == "empty") s.empty()? cout << "YES" << endl : cout << "NO" << endl;
else if(op == "pop") s.pop();
else if(op == "query") cout << s.top() << endl;
else cin >> x, s.push(x);
}
return 0;
}