443. Stack From Queues
A cafeteria has a single conveyor lane where trays can only be added at the back and taken from the front. The staff, however, want to stack trays in a last-in-first-out fashion: the tray placed most recently must be the first one to come out again.
Implement QueueStack, a last-in-first-out stack that may use only standard queue operations internally (add to the back, remove from the front, look at the front, size, emptiness check). The constructor takes no arguments. push(x) puts x on top, pop() removes and returns the top element, top() returns the top element without removing it and empty() tells whether the stack has no elements. pop and top are only called on a non-empty stack.
Example 1
- Input:
- operations = ["QueueStack","push","push","top","push","pop","pop","top"]arguments = [[],[12],[47],[],[5],[],[],[]]
- Output:
- [null,null,null,47,null,5,47,12]
- Explanation:
The most recent value is on top: top returns 47, then the two pops return 5 and 47, leaving 12 on top.
Example 2
- Input:
- operations = ["QueueStack","push","empty","pop","empty","push","push","pop"]arguments = [[],[-6],[],[],[],[33],[34],[]]
- Output:
- [null,null,false,-6,true,null,null,34]
- Explanation:
After popping the only element the stack is empty again; later 33 and 34 are pushed and 34 comes out first.
Constraints
-109 ≤ x ≤ 109
At most 104 calls in totalpop and top are never called when the stack 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(n) push, O(1) other
- Space
- O(n)