Solution: Max Stack

Statement

Design a custom stack class, Max Stack, that supports the basic stack operations and can find the maximum element present in the stack.

Implement the following methods for Max Stack:

• Constructor: This initializes the Max Stack object.

• Void Push(int x): This pushes the provided element, x, onto the stack.

• Int Pop( ): This removes and returns the element on the top of the stack.

• Int Top( ): This retrieves the most recently added element on the top of the stack without removing it.

• Int peekMax( ): This retrieves the maximum element in the stack without removing it.

• Int popMax( ): This retrieves the maximum element in the stack and removes it. If there is more than one maximum element, remove the most recently added one (the topmost).

Constraints:

• $-1000 \leq$ x $\leq 1000$

• A maximum of $100$ calls can be made to Push( ), Pop( ), Top( ), peekMax( ) and popMax( ).

• The Pop( ), Top( ), peekMax( ), and popMax( ) methods will always be called on a non-empty stack.

Solution

One straightforward approach is to use two stacks: one to handle the standard stack operations and another to keep track of the maximum values. While this method is intuitive and relatively simple, it can become inefficient when implementing the popMax( ) operation. Finding and removing the maximum element from the stack can take $O(n)$ time in the worst case, as we might need to search through the entire stack to identify and remove the maximum value.