# 716. Max Stack

Design a max stack that supports push, pop, top, peekMax and popMax.

1. push(x) -- Push element x onto stack.
2. pop() -- Remove the element on top of the stack and return it.
3. top() -- Get the element on the top.
4. peekMax() -- Retrieve the maximum element in the stack.
5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

**Example 1:**<br>

```
MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5
```

**Note:**<br>

1. -1e7 <= x <= 1e7
2. Number of operations won't exceed 10000.
3. The last four operations won't be called when stack is empty.

```cpp
// Two Stacks
class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {
        
    }
    
    void push(int x) {
        if (s2.empty() || s2.top() <= x) s2.push(x);
        s1.push(x);
    }
    
    int pop() {
        if (!s2.empty() && s1.top() == s2.top()) s2.pop();
        int val = s1.top(); s1.pop();
        return val;
    }
    
    int top() {
        return s1.top();
    }
    
    int peekMax() {
        return s2.top();
    }
    
    int popMax() {
        int maxVal = s2.top();
        stack<int> tmp;
        while (s1.top() != s2.top()) {
            tmp.push(s1.top()); s1.pop();
        }
        s1.pop(); s2.pop();
        while (!tmp.empty()) {
            push(tmp.top()); tmp.pop();
        }
        return maxVal;
    }
private:
    stack<int> s1, s2;
};
```

```cpp
class MaxStack {
public:
    /** initialize your data structure here. */
    MaxStack() {
        
    }
    
    void push(int x) {
        l.insert(l.begin(), x);
        m[x].push_back(l.begin());
    }
    
    int pop() {
        int val = *l.begin();
        m[val].pop_back();
        if (m[val].empty()) m.erase(val);
        l.erase(l.begin());
        return val;
    }
    
    int top() {
        return *l.begin();
    }
    
    int peekMax() {
        return m.rbegin()->first;
    }
    
    int popMax() {
        int val = m.rbegin()->first;
        auto it = m[val].back();
        m[val].pop_back();
        if (m[val].empty()) m.erase(val);
        l.erase(it);
        return val;
    }
private:
    list<int> l;
    map<int, vector<list<int>::iterator> > m;
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/design/716.-max-stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.