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).
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.
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.
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.
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= Q <= 10^6
1 <= type <= 4
1 <= value <= 10^9
Time Limit : 1 sec
Postorder Traversal
Min Stack
Stock Span
Hills and Soldier
Hills and Soldier
Next Greater Element II