-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtrack_min_stack.cpp
107 lines (97 loc) · 1.67 KB
/
track_min_stack.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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <utility>
#include <iostream>
#include <stack>
#include <cassert>
using namespace std;
/* implements two ways of tracking min element in stack */
namespace solution_two_stacks // add extra min stack
{
class min_stack
{
private:
stack<int> min;
stack<int> s;
public:
void push(int n)
{
if ( min.empty() || n <= min.top() )
min.push(n);
s.push(n);
}
void pop()
{
if ( s.empty() ) return;
if ( min.top() == s.top())
min.pop();
s.pop();
}
int top()
{
return s.top();
}
int get_min()
{
return min.top();
}
};
}
class utility
{
public:
template <typename T1, typename T2>
static pair<T1, T2> make_pair(T1 t1, T2 t2) // T1 is elements, T2 is the currrent min element when T1 is pushed
{
pair<T1,T2> p;
p.first = t1;
p.second = t2;
return p;
}
};
namespace solution_one_stack
{
class min_stack{
private:
stack<pair<int,int>>s;
public:
void push(int n)
{
if ( s.empty() ) s.push( utility::make_pair<int,int>(n, n));
else
{
if ( n < s.top().second ) s.push(utility::make_pair<int,int>(n, n));
else s.push( utility::make_pair<int,int>(n, s.top().second));
}
}
void pop()
{
s.pop();
}
int top()
{
return s.top().first;
}
int get_min()
{
return s.top().second;
}
};
}
template <class TEST_CLASS>
void testcase()
{
TEST_CLASS ms;
ms.push(2);
ms.push(1);
assert( ms.get_min() == 1 );
ms.push(3);
ms.push(0);
assert( ms.get_min() == 0 );
ms.pop();
assert( ms.get_min() == 1 );
}
int main()
{
testcase<solution_one_stack::min_stack>();
testcase<solution_two_stacks::min_stack>();
return 0;
}