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.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.