184. Queue From Two Stacks
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.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.