std::stack<int> with max function?

Question

How does one implement a stack<int> with a max operation which the max function has a complexity of O(1) and it uses O(n) extra memory?

Answer 1

The idea would be to keep track of the max through using pairs in the stack. If you insert something into the stack, you update the max accordingly.

class Stack {
private: 
    stack<pair<int,int>> s;

public:
    bool empty() const {
        return s.empty();
    }

    int max() const {
        assert (empty() == false);
        return s.top().second;
    }

    int pop() {
        int ans = s.top().first;
        s.pop();
        return ans;
    }

    void push(int x) {
        if (s.empty() || x > s.top().second)
        {
            s.emplace(x, x);
        }
        else
        {
            s.emplace(x, s.top().second);
        }
    }
};

Answer 2

Maintain a sorted list of int

Each stack node points to the list entry

max just returns the head (min would be the tail) of the list

When you push also do a sorted insert into the list (note that this will now be O(n) but that wasn't precluded)

When you pop do a delete of the associated entry in the list

Getting the head is O(1). The list will be of size O(n).