// Source : https://oj.leetcode.com/problems/min-stack/
// Author : Hao Chen
// Date   : 2014-11-16

/********************************************************************************** 
* 
* Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
* 
* push(x) -- Push element x onto stack.
* 
* pop() -- Removes the element on top of the stack.
* 
* top() -- Get the top element.
* 
* getMin() -- Retrieve the minimum element in the stack.
* 
*               
**********************************************************************************/

#include 
#include 
using namespace std;

//It seems C++ vector cause the Memory Limit Error, So, implement a simple one
template 
class Stack {
    private:
        T* _stack;
        int _capacity;
        int _top;
    public:
        Stack():_capacity(1),_top(-1){
            _stack = (T*)malloc(_capacity*sizeof(T));
        }

        ~Stack(){
            free(_stack);
        }

        void push(T x){
            _top++;
            if ( _top >= _capacity ){
                //if capacity is not enough, enlarge it 5 times.
                //Notes: why 5 times? because if you change to other(e.g. 2 times), 
                //       LeetCode system will report Run-time Error! it sucks!
                _capacity*=5;
                _stack = (T*)realloc(_stack, _capacity*sizeof(T));
            }
            _stack[_top] = x;
        }

        T pop() {
            return top(true);
        }

        T& top(bool pop=false) {
            if (_top>=0){
                if (pop){
                    return _stack[_top--];
                }
                return _stack[_top];
            }
            static T null;
            return null;
        }

        bool empty(){
            return (_top