174. Two Stacks in One Array
Challenge1000 ms256 MBSolved by 0%
Hold TWO stacks inside a single array of size n, using no other storage.
Neither stack has a fixed capacity, the only limit is that together they must fit.
Read n, then q operations, one per line:
1 s x, pushxonto stacks(sis 1 or 2); printFullif the array is full and ignore the push2 s, pop from stacksand print the value, orEmptyif that stack has none
Print one line per 2 operation, plus a line for each rejected push.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `-1000000 ≤ x ≤ 1000000`
Input
The first line contains an integer n, the size of the shared array.
The second line contains an integer q, the number of operations.
Each of the next q lines is one operation:
- 1 s x, push x onto stack s, where s is 1 or 2
- 2 s, pop from stack s and print the value
Output
Print one line for each 2 operation, the value, or Empty, plus a line reading Full for each rejected push.
Input5
4
1 1 10
1 2 20
2 1
2 2
Output10
20
Noteuses both stacks independently
Input2
3
1 1 1
1 1 2
1 1 3
OutputFull
Notefills the array with ONE stack, so the third push is rejected
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.