# Max Stack

Implement a stack that is able to return the maximum of the stack at any moment. All operations must be O(1), or amortized O(1) on the push operation.

**The Idea:**

* We maintain a secondary stack, that which we will call MaxStack. It is a special kind of stack, so it should have very similar methods, with a few exceptions. 
* We will encapsulate a regular stack, that will be used to maintain the `MaxStack` ordinary operators like `push`, `pop`, `top`.
* `MaxStack` will interface with another stack we will call `max_s` that overwrites a few operators.
  * `push` will add the new integer to max stack iff it exceeds the current size of its current max. This has the effect of maintaining a history of the max elements pushed in.
  * So when we `pop` we will naturally obtain the previous max element that will always be inline with the ordinary stack, since we pop from both containers.

```cpp
class Stack
{
public:
    Stack(const size_t n) {
        s.reserve(n);
        iter = 0;
    }

    Stack() { iter = 0; }

    void reserve(const size_t n) { s.reserve(n); }
    virtual bool empty() { return iter == 0; }
    int top()
    {
        if (!empty()) return (s.at(iter - 1));
        else throw "empty";
    }

    virtual void push(const int n) 
    { 
        if (iter >= s.size()) {
            s.push_back(n);
            iter++;
        }
        else s.at(iter++) = n; 
    }
    virtual void pop()
    {
        if (!empty()) iter--;
        else throw "empty";
    }

private:
    vector<int> s;
    int iter;
};

class MaxStack : public Stack
{
public:
    MaxStack(const size_t size) {
        Stack::reserve(size);
        max_s.reserve(size);
        iter = 0;
    }

    void push(const int n)
    {
        Stack::push(n);
        if (empty()) max_s.push(n);
        else if (!empty() && n < max_s.top()) {
            max_s.push(max_s.top());
        }
        else max_s.push(n);
        iter++;
    }

    void pop()
    {
        if (!empty()) {
            Stack::pop();
            max_s.pop();
            iter--;
        }
        else throw "empty";
    }

    int max()
    {
        if (!empty()) 
            return max_s.top();
        else throw "empty";
    }

    bool empty() { return iter == 0; }

private:
    Stack max_s;
    int iter;
};

int main()
{
    cout << "ascending" << endl;
    MaxStack s(30);
    vector<int> elements = {1,2,3,4,5,6,7,8,9,9,9};
    for (int i : elements) {
        s.push(i);
        cout << s.max() << " ";
    }
    cout << "\n\n";

    try
    {
        while (!s.empty()) {
            s.pop();
            cout << s.max() << " ";
        }
    }
    catch (const char* msg) {
        cerr << msg << endl;
    }
    cout << "\n\n\n";

    cout << "descending" << endl;
    MaxStack s2(30);
    vector<int> elements2 = { 9,9,9,8,7,6,5,4,3,2,1 };
    for (int i : elements2) {
        s2.push(i);
        cout << s2.max() << " ";
    }
    cout << "\n\n";

    try
    {
        while (!s2.empty()) {
            s2.pop();
            cout << s2.max() << " ";
        }
    }
    catch (const char* msg) {
        cerr << msg << endl;
    }
}
```

output

```
ascending
1 2 3 4 5 6 7 8 9 9 9

9 9 8 7 6 5 4 3 2 1 empty



descending
9 9 9 9 9 9 9 9 9 9 9

9 9 9 9 9 9 9 9 9 9 empty
```