Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

9/2/2015
/******************************************************************************************
*******************************************************************************************
Chapter 3 Stack and Queue

Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? 
Push, pop and min should all operate in O(1) time.
We design this class using array instead of linkedlist
 
By: Hamed Kiani (Sep. 2, 2015)
******************************************************************************************
******************************************************************************************/

#include "stdafx.h"
#include <iostream>
using namespace std;

class minStack{

private:
        int* _main_stk;      // main stack
        int* _aux_stk;       // aux. stack to keep elements in sorted
        int _cap;        // the maximum capacity of stack
        int _top;        // size of stack

public:
        minStack(int n);
        ~minStack();
        void push(int data);
        int pop();
        bool is_empty();
        bool is_full();
        void print_stk();
        void print_aux_stk();
        int getMin();
};

minStack::minStack(int n)
{
        _cap = n;
        _main_stk = new int[_cap];
        _aux_stk  = new int[_cap];
        _top = -1;       
        cout << " an object of minStack is created!" << endl;
}

minStack::~minStack()
{       
        delete[] _main_stk;
        delete[] _aux_stk;
        cout << " an object of minStack is deleted!" << endl;
}

bool minStack::is_empty()
{
        return (_top == -1);
}

bool minStack::is_full()
{
        return (_top == _cap-1);
}

void minStack::push(int data)
{
        if (is_full())
        {
                cout << "stack overflow!" << endl;
                return;
        }
        cout << " The element " << data << " is pushed on the stack!" << endl;
        // if the stack is empty or data is less than all elements in the aux. stack, just push it
        if ((_top == -1) || (data <= _aux_stk[_top]))
        {
                _top++;             
                _main_stk[_top] = data;
                _aux_stk[_top]  = data;             
                return;
        }

        // otherwise, push data on the main stack and duplicate the current min in the new position
        int temp = _aux_stk[_top];
        _top++;             
        _main_stk[_top] = data;     
        _aux_stk[_top] = temp;      
}

// pop operation: simply just _top--!
int minStack::pop()
{
        if (is_empty())
        {
                cout << "underflow!" << endl;
                return INT_MAX;
        }       
        _top--;
        cout << " The element " << _main_stk[_top+1] << " is popped from the stack!" << endl;
}

// return min value
int minStack::getMin()
{
        return _aux_stk[_top];
}

// print the main stack
void minStack::print_stk()
{
        if (is_empty())
        {
                cout << " nothing to print!" << endl;
                return;
        }
        for (int j = 0; j <= _top; j++)
                cout << _main_stk[j] << " " ;
        cout << endl;
}

// print the main stack
void minStack::print_aux_stk()
{
        if (is_empty())
        {
                cout << " nothing to print!" << endl;
                return;
        }
        for (int j = 0; j <= _top; j++)
                cout << _aux_stk[j] << " " ;
        cout << endl;
}

////////////////////////////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
        minStack stack(10);

        stack.push(12);
        stack.push(3);
        stack.push(4);   
        stack.push(11);

        stack.push(12);
        cout << "the min value is : " << stack.getMin() << endl;
        stack.push(11);
        stack.push(41);
        cout << "the min value is : " << stack.getMin() << endl;
        stack.push(12);
        stack.push(1);
        stack.push(3);
        
        cout << "the min value is : " << stack.getMin() << endl;
        stack.print_stk();
        stack.print_aux_stk();

        cout << "the min value is : " << stack.getMin() << endl;
        stack.pop();
        stack.pop();
        stack.pop();
        cout << "the min value is : " << stack.getMin() << endl;
        stack.print_stk();
        stack.print_aux_stk();
        return 0;
}
1 Comment
Design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

Leave a Reply.

Author

Categories

Archives
