#include #include /** * My solution to the Stack problem * I asked myself a simple question, * instead of a variable or a pointer, * why not just use a 2nd Stack? One * that specifically holds the min * value? So that's what I did. * @Author: Ace * Bugs: None Known * Version: * 0.0.0.1: Designed the original stack * 0.0.0.2: Designed the MinStack * 0.0.0.3: Testing and Debugging. * 0.0.0.4: Released. */ /** * A simple stack class with basic * stack funtionalities. */ class Stack { private: static const int MAX = 100; int arr[MAX]; int top; public: Stack() {top = -1;}; bool isEmpty(); bool isFull(); int pop(); void push(int x); }; /* * Stack's member method to check if * the stack is empty * @return: true if Stack is empty, * false otherwise */ bool Stack::isEmpty() { return top == -1; } /* * Stack's member method to check if * the stack is full * @return: true if Stack is full, * false otherwise */ bool Stack::isFull() { return top == (MAX - 1); } /* Stack's member method to remove an element from it */ int Stack::pop() { if(isEmpty()) { std::cout<<"Stack Underflow"; abort(); } int x = arr[top]; top--; return x; } /* * Stack's member method to insert * an element to it * @param x: element to be added */ void Stack::push(int x) { if(isFull()) { std::cout<<"Stack Overflow"; abort(); } arr[++top] = x; } /** * A class that supports all the stack * operations and one additional * operation getMin() that returns the * minimum element from stack at any * time. This class inherits from the * stack class and uses an auxiliarry * stack that holds minimum elements */ class MinStack: public Stack { private: Stack min; public: int pop(); void push(int x); int getMin(); }; /* MinStack's member method to insert * an element to it. This method makes * sure that the min stack is also * updated with appropriate minimum * values * @param x: element to be added */ void MinStack::push(int x) { if(isEmpty()) { Stack::push(x); min.push(x); } else { Stack::push(x); int y = min.pop(); min.push(y); if( x < y ) min.push(x); else min.push(y); } } /* * MinStack's member method to remove an * element from it. This method removes * top element from min stack also. * @return the value at the top of * MinStack */ int MinStack::pop() { int x = Stack::pop(); min.pop(); return x; } /* * MinStack's member method to get * minimum element from it. * Remember O(1) time constraint! * @return the minimum value of the * stack */ int MinStack::getMin() { int x = min.pop(); min.push(x); return x; } int main() { MinStack s; s.push(10); s.pop(); s.push(20); s.push(30); std::cout << s.getMin() << std::endl; s.push(5); std::cout << s.getMin(); return 0; }

Stack Minimum