Problem: Implement a stack in which we can call a function min_stack() which always return the minimum element on the stack at that time.
example: stack s
Stack Data
4 <-- Top
5
6
7
2 <<=== Minimum element in the stack at this point of time.
9
In above stack I should be able to get the minimum value in the stack i.e.
min_stack(s) should return me : 2 .
Use an additional stack which always contain the top most element as minimum as follows :-
Min_ Stack
First 9 comes, min_stack has 9
second 2 comes min_stack has 2 on top
third 7 comes , now check whether 7 is lesser then 2 if not push again the 2 on the min stack
so stack at this point is
Min Stack Original Stack
2 7
2 2
9 9
example: stack s
Stack Data
4 <-- Top
5
6
7
2 <<=== Minimum element in the stack at this point of time.
9
In above stack I should be able to get the minimum value in the stack i.e.
min_stack(s) should return me : 2 .
Algorithm
Use an additional stack which always contain the top most element as minimum as follows :-
Min_ Stack
First 9 comes, min_stack has 9
second 2 comes min_stack has 2 on top
third 7 comes , now check whether 7 is lesser then 2 if not push again the 2 on the min stack
so stack at this point is
Min Stack Original Stack
2 7
2 2
9 9
C++ Complete Code Implementation
#include <iostream>
#include <vector>
using namespace std;
#define SIZE 100
template <class t>
class stack{
int top;
t elem[SIZE];
t minelem[SIZE]; /* stack to minimum element */
public:
stack();
void push(t);
t pop();
t seek ();
t min();
};
template <class t>
stack<t>::stack()
{
top=-1;
}
template <class t>
void stack<t> :: push ( t x)
{
if (top ==SIZE)
cout<<"stack full";
else{
elem[++top]=x;
/* here we will check whether top element in the min stack is lesser or not to push further element. */
t temp=minelem[top-1];
if ( temp < x)
minelem[top]=temp;
else
minelem[top]=x;
}
}
template <class t>
t stack <t>:: pop()
{
if (top ==-1)
return 0;
else
return (elem[top--]);
}
template <class t>
t stack <t>:: seek ()
{
if (top ==-1)
return 0;
else
return (elem[top]);
}
template <class t>
t stack<t>:: min()
{
if(top==-1)
return 0;
else
return(minelem[top]);
}
int main()
{
stack <int> s;
s.push(2);
s.push(3);
s.push(4);
cout<<"\nmin="<<s.min();
s.push(1);
cout<<"\nmin1="<<s.min();
cout<<"\npoped elem="<<s.pop();
cout<<"\nmin="<<s.min();
return 0;
}
