Wednesday, July 11, 2012

Write a program to implement a stack that can return a minimum value of the current elements at any instance

The Approach:-
  1. Have a second stack instance which will hold the minimum values.

  2. During a push operation if the new data is smaller than the top value in minimum stack push the data into the minimum stack.

  3. During a pop operation if the popped out value is same as top value in minimum stack pop the top element from minimum stack.

  4. At any given instance the top element in the minimum stack is the minimum value of all elements in the stack.

C++ program to implement a stack that can return a minimum value of the current elements at any instance

#include <iostream>
#include <list>
using namespace std;

// Basic stack using list
class Stack {
 private:
  list<int> mData;
  int count;
 public:
  Stack() { count = 0; }
  ~Stack() {}
  void push(int data) {
   mData.push_front(data);
   count++;
  }
  int top() {
   return mData.front();   
  }
  void pop() {
   mData.pop_front();
   count--;
  }
  bool empty() {
   return (count == 0) ? true : false;
  }
  int size() {
   return count;
  }
};

// Min stack
class MinStack : public Stack {
 private:  
  Stack* mMin;
 public:
  MinStack() { mMin = new Stack(); }

  ~MinStack() { delete mMin; }

  void mpush(int data) {
   if ( mMin->size() == 0 ) 
    mMin->push(data);
   else {
    if ( data < mMin->top() )
     mMin->push(data);
   }
   push(data);
  }

  void mpop() {
   int val = top();
   if ( val == mMin->top() )
    mMin->pop();
   pop();
  }

  int mmin() {
   return mMin->top();
  }
};

// Test program
int main() {
 MinStack* ms = new MinStack();
 ms->mpush(10);
 ms->mpush(20);
 ms->mpush(30);
 cout << "Minimum value in stack = " << ms->mmin() << endl;
 ms->mpush(5);
 cout << "Minimum value in stack = " << ms->mmin() << endl;
 ms->mpop();
 cout << "Minimum value in stack = " << ms->mmin() << endl;
 delete ms;
}

Output:-
Minimum value in stack = 10
Minimum value in stack = 5
Minimum value in stack = 10

2 comments :

  1. class node
    {
    public:
    int data;
    int min // to hold minimum value till that node
    node* nxt;
    node *head;
    node(int d)
    {
    data=d;
    }
    };
    class stack
    {
    node *head;
    void push(int d)
    { node nd=new node(d);
    if(head==null)
    {
    head=nd;
    nd->min=d;
    nd->nxt=null;
    }
    else
    {
    nd->nxt=head;
    head=nd;
    if(dnxt.min)
    nd.min=d;
    else
    nd.min=nd->nxt.min;

    }

    }
    int return_min()
    {
    return(head->nxt.min);

    }

    // rest logic for pop is same also make a main class to instantiate this class.

    }






    ReplyDelete
  2. This is incorrect if the stack is pushed in same value. If the stack have items: 5, 15, 5, 30, 20, 10. Then the pop operation of the top item: 5 will delete the only 5 at the top of the stack mMin. So the incorrect minimum value: 10 is obtained, even if there is still another 5 in current stack.

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top