Last Updated: 31 Oct, 2021
Anish and Stacks!
Moderate
Asked in company
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) .
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
Approaches
We can divide the full array into equal sizes of N and perform push operations if the mentioned stack is not full and pop the top element if the stack is not empty.
Algorithm:-
- Initialize an empty array named ANS to store all the answers.
- Initialize an array name SIZE of length N with 0 to store the current size of all the stacks.
- Initialize a variable name FULL and update it with L divided by N
- Iterate from 0 to Q. (Let’s say the iterator be i).
- If A is equal to 1,
- If SIZE[B] is FULL, add -1 to the ANS.
- Else, update ARR[B*FULL+SIZE[B]] to C,increment SIZE[B] by 1 and return 0.
- Else,
- If SIZE[B] is 0, add -1 to ANS.
- Else, add ARR[B*FULL+SIZE[B]-1] to the answer and decrement SIZE[B] by 1.
- If A is equal to 1,
- Return ANS.
We can store the top element of every stack and every next free index of every index so that we can process the queries in constant time.
Algorithm:-
- Initialize an empty array named ANS to store all the answers.
- Initialize an array name TOP of length N with -1 to store the top element index of all the stacks.
- Initialize an array NEXT of length N with NEXT[i] initialized as i + 1.
- Initialize a variable named FREE with 0 to store the free index in ARR.
- Iterate from 0 to Q. (Let’s say the iterator be i).
- If A is equal to 1,
- If FREE is -1, add -1 to ANS.
- Else,
- Make a copy of FREE at a variable named INSERT_AT.
- Update FREE to NEXT[FREE].
- Update ARR[FREE] to C.
- UPDATE NEXT[INSERT_AT] to TOP[B].
- Update TOP[B] to INSERT_AT.
- Return 0.
- Else,
- If TOP[B] is -1, add -1 to ANS.
- Else,
- Make a copy of TOP[B] at a variable named TOPS.
- Add ARR[TOPS] to the answer.
- Update TOP[B] by NEXT[TOP[B]].
- Update NEXT[TOPS] by FREE.
- Update FREE by TOPS.
- If A is equal to 1,
- Return ANS.