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.
Example:
Consider the following SpecialStack 16 --> TOP 15 29 19 18 When getMin() is called it should return 15, which is the minimum element in the current stack. If we do pop two times on stack, the stack becomes 29 --> TOP 19 18 When getMin() is called, it should return 18 which is the minimum in the current stack.
Solution: Use two stacks: one to store actual stack elements and other as an auxiliary stack to store minimum values. The idea is to do push() and pop() operations in such a way that the top of auxiliary stack is always the minimum. Let us see how push() and pop() operations work.
Push(int x) // inserts an element x to Special Stack
1) push x to the first stack (the stack with actual elements)
2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y.
…..a) If x is smaller than y then push x to the auxiliary stack.
…..b) If x is greater than y then push y to the auxiliary stack.
int Pop() // removes an element from Special Stack and return the removed element
1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.
The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.
int getMin() // returns the minimum element from Special Stack
1) Return the top element of auxiliary stack.
We can see that all above operations are O(1).
Let us see an example. Let us assume that both stacks are initially empty and 18, 19, 29, 15 and 16 are inserted to the SpecialStack.
When we insert 18, both stacks change to following. Actual Stack 18 <--- top Auxiliary Stack 18 <---- top When 19 is inserted, both stacks change to following. Actual Stack 19 <--- top 18 Auxiliary Stack 18 <---- top 18 When 29 is inserted, both stacks change to following. Actual Stack 29 <--- top 19 18 Auxiliary Stack 18 <---- top 18 18 When 15 is inserted, both stacks change to following. Actual Stack 15 <--- top 29 19 18 Auxiliary Stack 15 <---- top 18 18 18 When 16 is inserted, both stacks change to following. Actual Stack 16 <--- top 15 29 19 18 Auxiliary Stack 15 <---- top 15 18 18 18
Following is implementation for SpecialStack class. In the below implementation, SpecialStack inherits from Stack and has one Stack object min which work as auxiliary stack.
C++
#include<iostream> #include<stdlib.h> using namespace std; /* A simple stack class with basic stack funtionalities */class Stack { private: static const int max = 100; int arr[max]; int top; public: Stack() { top = -1; } bool isEmpty(); bool isFull(); int pop(); void push(int x); }; /* Stack's member method to check if the stack is iempty */bool Stack::isEmpty() { if(top == -1) return true; return false; } /* Stack's member method to check if the stack is full */bool Stack::isFull() { if(top == max - 1) return true; return false; } /* Stack's member method to remove an element from it */int Stack::pop() { if(isEmpty()) { cout<<"Stack Underflow"; abort(); } int x = arr[top]; top--; return x; } /* Stack's member method to insert an element to it */void Stack::push(int x) { if(isFull()) { cout<<"Stack Overflow"; abort(); } top++; arr[top] = x; } /* A class that supports all the stack operations and one additional operation getMin() that returns the minimum element from stack at any time. This class inherits from the stack class and uses an auxiliarry stack that holds minimum elements */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; } /* Driver program to test SpecialStack methods */int main() { SpecialStack s; s.push(10); s.push(20); s.push(30); cout<<s.getMin()<<endl; s.push(5); cout<<s.getMin(); return 0; } |
Java
//Java implementation of SpecialStack // Note : here we use Stack class for Stack implementation import java.util.Stack; /* A class that supports all the stack operations and one additional operation getMin() that returns the minimum element from stack at any time. This class inherits from the stack class and uses an auxiliarry stack that holds minimum elements */ class SpecialStack extends Stack<Integer> { Stack<Integer> min = new Stack<>(); /* 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 push(int x) { if(isEmpty() == true) { super.push(x); min.push(x); } else { super.push(x); int y = min.pop(); min.push(y); if(x < y) min.push(x); else min.push(y); } } /* 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 */ public Integer pop() { int x = super.pop(); min.pop(); return x; } /* SpecialStack's member method to get minimum element from it. */ int getMin() { int x = min.pop(); min.push(x); return x; } /* Driver program to test SpecialStack methods */ public static void main(String[] args) { SpecialStack s = new SpecialStack(); s.push(10); s.push(20); s.push(30); System.out.println(s.getMin()); s.push(5); System.out.println(s.getMin()); } } // This code is contributed by Sumit Ghosh |
Output:
10
5
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().
C++
/* 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); /* 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(y); return x; } |
Java
/* 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 push(int x) { if(isEmpty() == true) { super.push(x); min.push(x); } else { super.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. */public Integer pop() { int x = super.pop(); int y = min.pop(); /* Push the popped element y back only if it is not equal to x */ if ( y != x ) min.push(y); return x; } // This code is contributed by Sumit Ghosh |
Design a stack that supports getMin() in O(1) time and O(1) extra space
Thanks to @Venki, @swarup and @Jing Huang for their inputs.
Please write comments if you find the above code incorrect, or find other ways to solve the same problem.
leave a comment
0 Comments