/********************************************************************
    purpose:    

    設計包含min函數的棧。
    定義棧的數據結構，要求添加一個min函數，能夠得到棧的最小元素。
    要求函數min、push以及pop的時間復雜度都是O(1)。

*********************************************************************/
#include <vector> 

using namespace std;

template<class T>
class stack
{
private:
    T* elements;
    int count, top;
    int* minPos;
public:
    stack(int n) {
        top = 0;
        count = n;
        minPos = new int[count];
        elements = new T[count];
        if (elements == NULL || minPos == NULL) 
        {
            count = 0;
            cout<<"no more memory."<<endl;
        }
    }
    void push(T element)
    {
        if (top >= count) {
            cout<<"stack is full."<<endl;
        } else {
            if (top <= 0 || element < elements[top-1]) {
                minPos[top] = top;
            } else {
                minPos[top] = minPos[top-1];
            }
            elements[top++] = element;
        }
    }
    T pop()
    {
        if (top <= 0) {
            throw "no element in stack";
        } else {
            return elements[--top];
        }
    }
    T min()
    {
        if (top <= 0) throw "no element in stack";
        return elements[minPos[top-1]];
    }

    bool empty()
    {
        return top <= 0;
    }

    ~stack()
    {
        delete[] elements;
        delete[] minPos;
    }
};


void Test_StackWithMinFunc()
{
    stack<int> st(20);
    int val[] = {6,7,1,3,9,11};
    int len = sizeof(val)/sizeof(val[0]);
    for (int i = 0; i < len; i++) {
        st.push(val[i]);
        cout<<st.min()<<endl;
    }
    while(!st.empty())
    {
        cout<<st.min()<<endl;
        st.pop();
    }
}