184. Queue From Two Stacks
Core1000 ms256 MBSolved by 0%
Build a working queue using only STACKS. You may push, pop and peek; you may not index into them or use a queue.
A stack reverses order, so one stack alone gives the wrong end. Reversing twice, however, gives the original order back — and that is the whole idea.
Done carelessly this is O(n) per removal. Done correctly, each value moves between the two stacks at most once, which makes the average cost constant.
Constraints - `1 ≤ q ≤ 200000` - `-1000000 ≤ x ≤ 1000000`
Input
The first line contains an integer q, the number of operations.
Each of the next q lines is one operation:
- 1 x — add x to the back of the queue
- 2 — remove the front value and print it
- 3 — print the front value without removing it
Output
Print one line for each 2 and 3 operation — the value, or Empty if the queue holds nothing.
Input5
1 10
1 20
3
2
3
Output10
10
20
Noteconfirms the FIRST value added leaves first
Input2
2
3
OutputEmpty
Empty
Notereads an empty queue, where BOTH stacks are empty
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution