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.

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