Min Stack Solutions in C++

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



#include <stdlib.h>
#include <iostream>
using namespace std;

//It seems C++ vector cause the Memory Limit Error, So, implement a simple one
template <typename T>
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<0);
        }
        int size() {
            return _top+1;
        }
        void clear(){
            _top = -1;
        }
};


/*
 * Idea: 
 *
 *    Using two stacks, 
 *    1) one stack is the real stack to store the data.
 *    2) another stack store the minimal number when it changes.
 *
 *    For example:
 *
 *        if we keep pushing the following numbers:
 *        5 1 1 2 3 2 
 *        the minial number stack will be: 
 *        5 1 1   <-- only store the number which <= cureent minimal number
 *   
 *    Then, when we pop up the stack.
 *
 *    we need compare whether the current number is the current minial number.
 *    if it is, then we need popup the number in minimal number stack.
 *        
 */
class MinStack {
    private:
        //Using a minData struct to remove the duplication in minimal stack
        //which can save the memory.
        struct minData{
            int min;
            int cnt;
            minData():min(0), cnt(0) {}
            minData(int m, int c):min(m),cnt(c){}
        };
        Stack<int> stack; //real stack store the data
        Stack<minData> minStack; //minimal number stack store the number 
        int min; //current minial number

    public:

        void push(int x) {
            if(stack.empty()){
                min = x;
                minStack.push(minData(x,1));
            }else{
                if (min >= x ){
                    min = x;
                    //if current minial number already pushed, then just add the reference coount.
                    if (minStack.top().min == x){
                        minStack.top().cnt++;
                    }else{
                        minStack.push(minData(x,1));
                    }
                }
            }
            stack.push(x);

        }

        void pop() {
            if (stack.empty()){
                return;
            }
            int x = stack.pop();
            if (x == minStack.top().min){
                //de-reference the count at first.
                if (minStack.top().cnt > 1){
                    minStack.top().cnt--;
                }else{
                    minStack.pop();
                    min = minStack.top().min;
                }
            }
        }

        int top() {
            return stack.top();
        }

        int getMin() {
            return min;
        }
        void clear() {
            stack.clear();
            minStack.clear();
        }

};

int main()
{
    cout << "--- expected output [0, 0, 0, 2]" << endl;
    MinStack ms;
    ms.push(2);
    ms.push(0);
    ms.push(3);
    ms.push(0);

    cout << ms.getMin() << endl;
    ms.pop();
    cout << ms.getMin() << endl;
    ms.pop();
    cout << ms.getMin() << endl;
    ms.pop();
    cout << ms.getMin() << endl;


    ms.clear();

    cout << "--- expected output [2147483647 2147483646 2147483646 2147483647 2147483647 -2147483648 -2147483648 2147483647 " << endl;

    ms.push(2147483646);
    ms.push(2147483646);
    ms.push(2147483647);

    cout << ms.top() << endl;
    ms.pop();
    cout << ms.getMin() << endl;
    ms.pop();
    cout << ms.getMin() << endl;
    ms.pop();

    ms.push(2147483647);
    cout << ms.top() << endl;
    cout << ms.getMin() << endl;
    ms.push(-2147483648);
    cout << ms.top() << endl;
    cout << ms.getMin() << endl;
    ms.pop();
    cout << ms.getMin() << endl;


    return 0;
}

/// Source : https://leetcode.com/problems/min-stack/description/
/// Author : liuyubobobo
/// Time   : 2017-11-16

#include <iostream>
#include <set>
#include <cassert>

using namespace std;

/// Using two sets
/// Time Complexity: push: O(nlogn)
///                  pop:  O(nlogn)
///                  top:  O(nlogn)
///                  getMin: O(nlogn)
/// Space Complexity: O(n)
class MinStack {

private:
    int index = 0;
    set<pair<int, int>> vi;   // value - index
    set<pair<int, int>> iv;   // index - value

public:
    /** initialize your data structure here. */
    MinStack() {
        vi.clear();
        iv.clear();
        index = 0;
    }

    void push(int x) {
        vi.insert(make_pair(x, index));
        iv.insert(make_pair(index, x));
        index ++;
    }

    int pop() {

        assert(iv.size() > 0);

        pair<int, int> e_iv = *iv.rbegin();
        iv.erase(e_iv);

        pair<int, int> e_vi = make_pair(e_iv.second, e_iv.first);
        vi.erase(e_vi);

        return e_iv.second;
    }

    int top() {
        assert(iv.size() > 0);
        return iv.rbegin()->second;
    }

    int getMin() {
        assert(vi.size() > 0);
        return vi.begin()->first;
    }

};

int main() {

    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl; // -> -3
    minStack.pop();
    cout << minStack.top() << endl;    // -> 0
    cout << minStack.getMin() << endl; // -> -2

    return 0;
}

/// Source : https://leetcode.com/problems/max-stack/description/
/// Author : liuyubobobo
/// Time   : 2017-11-28

#include <iostream>
#include <stack>
#include <cassert>

using namespace std;

/// Using two stacks
/// We have one regular stack for push, pop and top operations
/// We have another stack for getMin operations, which named minStack
/// minStack will store the current min value in the stack
///
/// Time Complexity: push: O(1)
///                  pop:  O(1)
///                  top:  O(1)
///                  getMin: O(1)
/// Space Complexity: O(n)
class MinStack {

private:
    stack<int> normalStack;
    stack<int> minStack;

public:
    /** initialize your data structure here. */
    MinStack() {
        while(!normalStack.empty())
            normalStack.pop();

        while(!minStack.empty())
            minStack.pop();
    }

    void push(int x) {
        normalStack.push(x);
        if(minStack.empty())
            minStack.push(x);
        else
            minStack.push(min(minStack.top(), x));
    }

    int pop() {

        assert(normalStack.size() > 0);

        int v = normalStack.top();
        normalStack.pop();
        minStack.pop();

        return v;
    }

    int top() {
        assert(normalStack.size() > 0);
        return normalStack.top();
    }

    int getMin() {
        assert(normalStack.size() > 0);
        return minStack.top();
    }
};


int main() {

    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl; // -> -3
    minStack.pop();
    cout << minStack.top() << endl;    // -> 0
    cout << minStack.getMin() << endl; // -> -2

    return 0;
}

/// Source : https://leetcode.com/problems/max-stack/description/
/// Author : liuyubobobo
/// Time   : 2017-11-28

#include <iostream>
#include <map>
#include <cassert>
#include <list>
#include <vector>

using namespace std;

/// Using a list to simulate th stack
/// Using a TreeMap to record every node in the list
/// So we can get the min value in the list quickly and erase it easily
/// Since the problen doesn't require popMin operation,
/// we may not see the advantage of this method,
/// But in problem 716, Max Stack, it's different.
/// https://leetcode.com/problems/max-stack/description/
///
/// Time Complexity: push: O(1)
///                  pop:  O(1)
///                  top:  O(1)
///                  peekMax: O(1)
///                  popMax:  O(logn)
/// Space Complexity: O(n)
class MinStack {

private:
    list<int> stack;
    map<int, vector<list<int>::iterator>> record;

public:
    /** initialize your data structure here. */
    MinStack() {
        stack.clear();
        record.clear();
    }

    void push(int x) {
        stack.push_back(x);

        list<int>::iterator iter = stack.begin();
        advance(iter, stack.size() - 1);

        record[x].push_back(iter);
    }

    int pop() {

        int ret = stack.back();
        stack.pop_back();

        record[ret].pop_back();
        if(record[ret].size() == 0)
            record.erase(ret);

        return ret;
    }

    int top() {
        assert(stack.size() > 0);
        return stack.back();
    }

    int getMin() {
        assert(stack.size() > 0);
        return record.begin()->first;
    }

};


int main() {

    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl; // -> -3
    minStack.pop();
    cout << minStack.top() << endl;    // -> 0
    cout << minStack.getMin() << endl; // -> -2

    return 0;
}