2. Max Stack

Description

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

Input:
push(5)
push(1)
push(5)
top()
popMax()
top()
peekMax()
pop()
top()

Output:551515

Solution:

class MaxStack
{
public:
    stack<int> s;
    stack<int> ms;

    MaxStack()
    {
        // do intialization if necessary
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    void push(int number)
    {
        s.push(number);

        if(ms.empty()){
            ms.push(number);
        }
        else if (!ms.empty() && number >= ms.top())
        {
            ms.push(number);
        }

        return;
    }

    /*
     * @return: An integer
     */
    int pop()
    {
        int n;

        if (!s.empty())
        {
            n = s.top();
            s.pop();
        }

        if (!ms.empty() && ms.top() == n)
        {
            ms.pop();
        }

        return n;
    }

    /*
     * @return: An integer
     */
    int top()
    {
        // write your code here
        return s.top();
    }

    /*
     * @return: An integer
     */
    int peekMax()
    {
        // write your code here
        return ms.top();
    }

    /*
     * @return: An integer
     */
    int popMax()
    {
        // write your code here
        int n;

        if (!ms.empty())
        {
            n = ms.top();
            ms.pop();
        }

        while (!s.empty() && s.top() != n)
        {
            s.pop();
        }
        s.pop();

        return n;
    }
};