-
Notifications
You must be signed in to change notification settings - Fork 0
/
MinStack.cpp
89 lines (79 loc) · 1.7 KB
/
MinStack.cpp
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
//Implementation of min stack in O(1) Space and Time complexity
/*let y be newMinimum and x be oldMinimum
=> y<x
=> 2y<x+y
=> 2y-x<y So, we use 2y-x as flag here */
struct MyStack
{
stack<int>s;
int minElement;
//to get minimum element of stack
void getMin()
{
if(s.size()==0)
cout<< -1<<endl;
else
cout<<minElement<<endl;;
}
void push(int x)
{
if(s.size()==0)
{
s.push(x);
minElement=x; //for empty stack, only element will be the minElement
}
else {
if(x>=minElement)
{
s.push(x); //greater element is pushed directly, no updates to minElement
}
else
{
s.push(2*x-minElement); //used as a flag since it will be lower than minElement
minElement=x; //new minElement updated
}
}
}
void pop()
{
if(s.size()==0)
cout<< -1<<endl;
else{
if(s.top()>=minElement)
s.pop(); //greater element popped since its not minimum
else{
//working as flag
minElement=2*minElement-s.top(); //flag indicated we had updated minElement, so getting previous minElement
s.pop();
}
}
}
void top()
{
if(s.size()==0)
cout<< -1<<endl;
else{
if(s.top()>=minElement)
cout<< s.top()<<endl; //element at top
else
cout<< minElement<<endl; //element in stack is actually flag, real element is in minElement
}
}
};
int main()
{
MyStack s;
s.push(3);
s.push(5);
s.getMin();
s.push(2);
s.push(1);
s.getMin();
s.pop();
s.getMin();
s.pop();
s.top();
return 0;
}