 New update is available. Click here to update.

# Max Stack

Posted: 25 Dec, 2020
Difficulty: Easy

## PROBLEM STATEMENT

#### You have to implement a special data structure “MAX_STACK” it would be a hybrid data structure of max heap and stack. Basically, it will have all the functionality of a stack in addition to it the max stack should also give max element in a stack in O(1). you have to implement the following functions:

``````specialPush(value): should push the value in the stack in O(1).
specialPop( ) : should pop the last element from the stack in O(1).
specialTop( ): should give the element at the top of the stack in O(1).
specialMax( ): should give the maximum element from all the elements that are currently present in the stack in O(1).
``````

#### In addition it tries to construct it only using the stack data structure.

``````Four types of queries denote these operations:

Type 1 : for specialPush(value) operation.
Type 2 : for specialPop( ) operation.
Type 3 : for specialTop( ) operation.
Type 4 : for specialMax( ) operation.
``````
##### Input format:
``````The first line of input contains a single integer 'Q', denoting the number of queries.

The next 'Q' line contains one operation per line.

Each operation starts with a single positive integer representing the type of operation.

If it is 1 then the operation is of type 1 and it is followed by a positive integer value.
If it is 2, 3, or 4 then it represents the operation of type 2, 3, and 4 respectively.
``````
##### Output format :
``````For each operation of type 2, return an integer on a single line - the element popped from the stack, and if there is underflow i.e. there is no element in the stack then return -1.
For each operation of type 3, return an integer on a single line - the top element of the stack and if the stack is empty return -1.
For each operation of type 4, return an integer on a single line - the maximum element on the stack and if the stack is empty return -1.
``````
##### Note :
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraint :
``````1 <= Q <= 10^6
1 <= type <= 4
1 <= value <= 10^9

Time Limit : 1 sec
``````