# 14370: 【原4370】Min Stack

### 题目描述

author: Mars 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4370

## Description

• push(x)——x 入栈；
• pop()——堆顶元素出栈；
• top()——返回栈顶元素
• getMin()——求栈内最小值

## Input Format

• 0 x : push(x)
• 1 : pop()
• 2 : top()
• 3 : getMin()

10
0 1
0 2
2
3
1
3
1
1
2
3

2
1
1
Empty
Empty
Empty

## Limits:

0 < n <= 10^6
0 <= x < 3 * 10^9

## ligongzzz's solution

``````#include <iostream>
#include <stack>
using namespace std;

class myStack {
stack<unsigned  int> real_stack;
stack<pair<unsigned int,unsigned int>> min_stack;

public:
void push(unsigned int x) {
real_stack.push(x);
if (min_stack.empty()||min_stack.top().second>x){
min_stack.push(make_pair(real_stack.size(), x));
}
}

void pop() {
if (real_stack.empty()) {
cout << "Empty\n";
return;
}
if (min_stack.top().first==real_stack.size()) {
min_stack.pop();
}
real_stack.pop();
}

void top() {
if (real_stack.empty()) {
cout << "Empty\n";
return;
}
cout << real_stack.top() << "\n";
}

void getMin() {
if (real_stack.empty()) {
cout << "Empty\n";
return;
}
cout << min_stack.top().second << "\n";
}
};

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n = 0;
cin >> n;

myStack stack1;

for (;n;--n) {
int a;
cin >> a;
if (a==0) {
unsigned int b;
cin >> b;
stack1.push(b);
}
else if (a==1) {
stack1.pop();
}
else if (a==2) {
stack1.top();
}
else {
stack1.getMin();
}
}
}
``````