Anish and Stacks!

Moderate

0/80

Average time to solve is 30m

Contributed by

9 upvotes

Asked in company

Problem statement

Anish has become very attentive in his data structures classes. Now his teacher has given the assignment to implement N stacks in a single array of length L. Since he has been very inattentive in his data structure classes, he can’t solve the problem on his own. Can you help him out?

Example:-

Let, 

N = 5
L = 10
1 1 3 [PUSH (1 ,4)]
1 1 4 [PUSH (1 ,3)] 
2 1 [POP(1)] 
2 2 2 [PUSH(2,2)] 
2 2 [POP(2)]

Answer:- [0, 0, 4, 0, 2]
 (The first stack has 4 and 3 so 4 is popped out from stack 1 and stack 2 has integer 2 in it, so 2 is popped out from stack 2) .

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case contains three integers ‘L’, ‘N’, and ‘Q’ denoting the number of stacks to be implemented and the number of queries to be performed.

The next ‘Q’ lines of every test case contain 3 integers ‘A’, ‘B’, and ‘C’ denoting the type of operation, the stack number on which the operation is to be achieved, and the number to be pushed if ‘A’ is 1.

The next ‘Q’ lines of every test case contain 2 integers ‘A’, and ‘B’ denoting the type of operation, and the stack number on which the operation is to be achieved if 'A' is 2.

Output Format :

For each test case, print an integer denoting the number popped out if ‘A’ is 2 if there exists a number in the stack otherwise print -1. If ‘A’ is 1, if the push operation is successful, print 0, otherwise print -1 if the stack is full.

The output of each test case should be printed in a separate line.

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 5
1 <= L <= 10^5
1 <= N <= 10^5
1 <= Q <= 10^5
1 <= A <= 2
1 <= B <= N
1 <= C <= 10^9  

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

Explanation for Sample Output 1 :

In the first two operations, the answer should be 0 because the push operations are performed successfully. Then for the next two operations, the numbers 3 and 1 are popped out and they are printed. In the last operation, -1 is printed because the stack is already empty.

Sample Input 2 :

1
10 2 1
2 2

Sample Output 2 :

-1

Console