15 Jan 2015

e-Khaliyan

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