blob: 1bcb36ab156f15c336789a0aca8264606298329e (
plain)
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
|
class MinStack {
public:
MinStack() {}
void push(int val) {
const int minVal = (m_minStack != nullptr) ? std::min(m_minStack->val, val) : val;
Node* top = new Node{m_stack, val};
Node* minTop = new Node{m_minStack, minVal};
m_stack = top;
m_minStack = minTop;
}
void pop() {
assertNonEmpty();
Node* top = m_stack;
Node* minTop = m_minStack;
m_stack = m_stack->next;
m_minStack = m_minStack->next;
delete top;
delete minTop;
}
int top() {
assertNonEmpty();
return m_stack->val;
}
int getMin() {
assertNonEmpty();
return m_minStack->val;
}
private:
struct Node {
Node* next;
int val;
};
void assertNonEmpty() const {
if (m_stack == nullptr) {
throw "empty stack";
}
}
Node* m_stack = nullptr; // The actual stack.
Node* m_minStack = nullptr; // Stack of mins.
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
|
