Max Stack

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

Approach 1

We will use two stacks, one is the normal stack to perform normal stack operations and the other one is the max stack to perform max stack operations.
The key observation here is that we can store the element in the max stack only if it is greater than all the previous elements. This means the max stack has elements in ascending order.
Because of this, the current top in the max stack will be the biggest element in the normal stack.
So let’s see how we will implement the given functions.
Type 1 : specialPush('VALUE') operation
- Push the ‘VALUE’ in the normal stack.
- Push the ‘VALUE’ in the max stack if it is empty or if the top is less or equal to ‘VALUE’.
Type 2: specialPop( ) operation
- Pop the max stack if the top in the normal stack is equal to the top in the max stack.
- Pop the normal stack.
- Return the popped element.
Type 3 : specialTop( ) operation
- Return the top of the normal stack.
Type 4 : specialMax( ) operation
- Return the top of the max stack.
For example in the first test case that is :
- 10
- 1 5 // Stack.specialPush(5)
- 1 4 // Stack.specialPush(4)
- 1 6 // Stack.specialPush(6)
- 1 1 // Stack.specialPush(1)
- 3 // Stack.specialTop()
- 4 // Stack.specialMax()
- 2 // Stack.specialPop()
- 2 // Stack.specialPop()
- 3 // Stack.specialTop()
- 4 // Stack.specialMax()