Comment on page
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
Permission Management for a General Tree
Parking Lot
Last modified 4yr ago