-
Notifications
You must be signed in to change notification settings - Fork 0
/
MinStack.hpp
51 lines (41 loc) · 830 Bytes
/
MinStack.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//Min Stack
//Design a stack that supports push, pop, top, and retrieving the minimum element
//in constant time.
//
//push(x) --Push element x onto stack.
//pop() --Removes the element on top of the stack.
//top() --Get the top element.
//getMin() --Retrieve the minimum element in the stack.
#include <climits>
class MinStack {
public:
MinStack() :min_value(INT_MAX),it_top(0){};
void push_top(int x){
stack[it_top++] = x;
}
void push(int x) {
push_top(x);
if (x <= min_value)
min_value = x;
push_top(min_value);
}
void pop() {
if (it_top > 0)
it_top -= 2;
}
int top() {
if (it_top > 0)
return stack[it_top - 2];
}
int getMin() {
if (it_top > 0)
return stack[it_top - 1];
}
private:
void push_top(int x){
stack[it_top++] = x;
}
int stack[150];
int it_top;
int min_value;
};