Simple Min stack C++ example that retrieve minimum element in constant time. Logic is very simple. Time complexity to pop a value from the stack is constant. Hence, implementation will use two stacks i.e. one to keep value and another stack to keep minimum value. For implementation STL stack will be used.
Logic:
Create two stacks, original stacks that holds values and another min stack that holds min values
PUSH operation:
Push input value in original stack. If the min stack is empty, then push the value in min stack also.
If min stack is not empty, get the top value of min stack and compare with input value. If input value is less than are equal to min stack top value then push it to min stack.
POP operation:
pop value from original stack. Also, get both stacks top value and compare it. If both top values are equal then also pop value from min stack or else don’t pop from min stack.
MIN VAULE OPERATION:
Return min value from min stack.
C++ Program for min stack design
Below is the class design form min value from the stack in constant time.
/*
* Min stack C++ implementation to retrieve
* alwasys min value from the stack
*/
#include <string>
#include <stack>
#include <iostream>
using namespace std;
#define INVALID_VALUE 999
class MinStack
{
stack<int> oStack;//first stack
stack<int> minStack;//min stack
public:
// Push Method
void push(int item){
//push item in original stack
oStack.push(item);
//Check if this min Stack is empty
//if empty then push item.
//or else compare with min stack top
//value if input value is less or equal
//to value of top of min stack, if yes
//Then push item in min stack or else leave
//it
if(minStack.empty()){
minStack.push(item);
}else if(item <= minStack.top())
{
minStack.push(item);
}
}
// Pop Method
void pop(){
//if minstack top value is equal to
//original stack top value, only then pop
//value from min stack or else leave it.
if(!oStack.empty() && !oStack.empty() ){
if( minStack.top() == oStack.top()){
minStack.pop();
}
}
//Also pop original stack
if(!oStack.empty()){
oStack.pop();
}
}
// return minimum value from the stack
// if stack is empty then return a
//large value that will be invalid
int getMin(){
if(!minStack.empty()){
return minStack.top();
}
return INVALID_VALUE;
}
//Get to value from the stack
//if empty then return large value
int getTop(){
if(!oStack.empty()){
return oStack.top();
}
return INVALID_VALUE;
}
};
/*------------------------------------------
* Test minimum value from stack
*/
int main(){
//Fill the stack
MinStack s;
s.push(5);
s.push(7);
s.push(2);
s.push(8);
s.push(5);
s.push(9);
cout<<"Value :"<<s.getTop();
cout<<" Min value :"<<s.getMin()<<endl;
s.pop();
cout<<"Value :"<<s.getTop();
cout<<" Min value :"<<s.getMin()<<endl;
s.pop();
cout<<"Value :"<<s.getTop();
cout<<" Min value :"<<s.getMin()<<endl;
s.pop();
cout<<"Value :"<<s.getTop();
cout<<" Min value :"<<s.getMin()<<endl;
s.pop();
cout<<"Value :"<<s.getTop();
cout<<" Min value :"<<s.getMin()<<endl;
s.pop();
cout<<"Value :"<<s.getTop();
cout<<" Min value :"<<s.getMin()<<endl;
return 0;
}OUTPUT:
Value :9 Min value :2
Value :5 Min value :2
Value :8 Min value :2
Value :2 Min value :2
Value :7 Min value :5
Value :5Min value :5