 Get Exclusive Deals on Amazon # Implement min() function for stack using extra Space

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 .

### 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;
}