New update is available. Click here to update.

Two Stacks

Posted: 23 Dec, 2020
Difficulty: Moderate


Try Problem

Design a data structure, which represents two stacks using only one array common for both stacks. The data structure should support the following operations:

push1(NUM) - Push ‘NUM’ into stack1.
push2(NUM) - Push ‘NUM’ into stack2.
pop1() - Pop out a top element from stack1 and return popped element, in case of underflow return -1.
pop2() - Pop out a top element from stack2 and return popped element, in case of underflow return -1.

There are 2 types of queries in the input

Type 1 - These queries correspond to Push operation.
Type 2 - These queries correspond to Pop operation.


1. You are given the size of the array.

2. You need to perform push and pop operations in such a way that we are able to push elements in the stack until there is some empty space available in the array.

3. While performing Push operations, do nothing in the situation of the overflow of the stack.
Input format:
The first line of the input contains two space-separated integers 'S' and 'Q', denoting the size of the array and number of operations to be performed respectively.

The next 'Q' lines contain operations, one per line. Each line begins with two integers ‘type’ and ‘stackNo’, denoting the type of query as mentioned above and the stack number on which this operation is going to be performed.

If the ‘type’ is 1 then it will be followed by one more integer ‘NUM’ denoting the element needed to be pushed to stack ‘stackNo’.
Output format:
For each operation of Type 2, print an integer on a single line - popped element from the stack, if the stack is already empty print -1.
You do not need to print anything, it has already been taken care of. Just implement the given function.
0 <= S <= 10^5
1 <= Q <= 5*10^5
1 <= type, stackNo <= 2
0 <= NUM <= 10^9

Time Limit: 1 sec.