442. Queue From Two Stacks
A ticket office only owns two spring-loaded plate dispensers, and each one can only hand back the plate that was placed on it last. The manager still wants customers to be served strictly in the order they arrived, so the two dispensers have to cooperate to behave like a single waiting line.
Implement TwoStackQueue, a first-in-first-out queue that may only use two stacks internally. The constructor takes no arguments. push(x) adds x to the back of the queue, pop() removes the front element and returns it, peek() returns the front element without removing it and empty() tells whether the queue holds no elements. pop and peek are only called on a non-empty queue.
Example 1
- Input:
- operations = ["TwoStackQueue","push","push","peek","push","pop","pop","empty"]arguments = [[],[21],[8],[],[35],[],[],[]]
- Output:
- [null,null,null,21,null,21,8,false]
- Explanation:
The queue holds 21, 8 and 35 in arrival order. peek shows 21, the two pops return 21 and then 8, and 35 is still waiting, so empty is false.
Example 2
- Input:
- operations = ["TwoStackQueue","empty","push","pop","empty","push","peek"]arguments = [[],[],[-4],[],[],[90],[]]
- Output:
- [null,true,null,-4,true,null,90]
- Explanation:
A fresh queue is empty. After one push and one pop it is empty again; later 90 becomes the front.
Constraints
-109 ≤ x ≤ 109
At most 104 calls in totalpop and peek are never called when the queue is empty.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(1) amortized per operation
- Space
- O(n)