LeetCode 155 - Min Stack - LintCode 12
Question: Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc
Space Optimized Version
The above approach can be optimized. We can limit the number of elements in auxiliary stack. We can push only when the incoming element of main stack is smaller than or equal to top of auxiliary stack. Similarly during pop, if the pop off element equal to top of auxiliary stack, remove the top element of auxiliary stack. Following is modified implementation of push() and pop().
http://articles.leetcode.com/2010/11/stack-that-supports-push-pop-and-getmin.html
-- Not optimized
Read full article from Design and Implement Special Stack Data Structure | Added Space Optimized Version | GeeksforGeeks
Question: Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc
Space Optimized Version
The above approach can be optimized. We can limit the number of elements in auxiliary stack. We can push only when the incoming element of main stack is smaller than or equal to top of auxiliary stack. Similarly during pop, if the pop off element equal to top of auxiliary stack, remove the top element of auxiliary stack. Following is modified implementation of push() and pop().
http://articles.leetcode.com/2010/11/stack-that-supports-push-pop-and-getmin.html
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
struct StackGetMin {
void push(int x) {
elements.push(x);
if (minStack.empty() || x <= minStack.top())
minStack.push(x);
}
bool pop() {
if (elements.empty()) return false;
if (elements.top() == minStack.top())
minStack.pop();
elements.pop();
return true;
}
bool getMin(int &min) {
if (minStack.empty()) {
return false;
} else {
min = minStack.top();
return true;
}
}
stack<int> elements;
stack<int> minStack;
};
|
void SpecialStack::push(int x){ if(isEmpty()==true) { Stack::push(x); min.push(x); } else { Stack::push(x); int y = min.pop(); min.push(y); /* push only when the incoming element of main stack is smaller than or equal to top of auxiliary stack */ if( x <= y ) min.push(x); }}/* SpecialStack's member method to remove an element from it. This method removes top element from min stack also. */int SpecialStack::pop(){ int x = Stack::pop(); int y = min.pop(); /* Push the popped element y back only if it is not equal to x */ if ( y != x ) min.push(x); return x;}-- Not optimized
class SpecialStack: public Stack{ Stack min;public: int pop(); void push(int x); int getMin();};/* SpecialStack's member method to insert an element to it. This method makes sure that the min stack is also updated with appropriate minimum values */void SpecialStack::push(int x){ if(isEmpty()==true) { Stack::push(x); min.push(x); } else { Stack::push(x); int y = min.pop(); min.push(y); if( x < y ) min.push(x); else min.push(y); }}/* SpecialStack's member method to remove an element from it. This method removes top element from min stack also. */int SpecialStack::pop(){ int x = Stack::pop(); min.pop(); return x;}/* SpecialStack's member method to get minimum element from it. */int SpecialStack::getMin(){ int x = min.pop(); min.push(x); return x;}Read full article from Design and Implement Special Stack Data Structure | Added Space Optimized Version | GeeksforGeeks
