Build a Queue From Two Stacks
Problem statement
Build a first-in, first-out queue using only stacks: the only actions allowed on each stack are push on top, pop from the top, look at the top, and check its size. The queue supports:
push: addvalues[i]at the back of the queue.pop: remove the value at the front and output it.peek: output the value at the front without removing it.empty: output 1 if the queue holds no values, otherwise 0.
Run operations in order, starting from an empty queue, and return the outputs in order (push outputs nothing). Try to make every operation take O(1) time on average. The judge only checks the outputs.
Function
runQueue(operations: String[], values: int[]) → int[]Examples
Example 1
operations = ["push","push","pop","push","peek","pop","pop","empty"]values = [8,3,0,5,0,0,0,0]return = [8,3,3,5,1]8 and 3 join; pop removes 8, the oldest. 5 joins behind 3. peek sees 3, then two pops remove 3 and 5. The queue is now empty, so empty gives 1. Outputs: 8, 3, 3, 5, 1.
Example 2
operations = ["empty","push","empty","peek","peek"]values = [0,42,0,0,0]return = [1,0,42,42]The queue starts empty (1). After 42 joins it is not empty (0). peek does not remove anything, so both peeks see 42.
Example 3
operations = ["push","push","push","pop","push","push","pop","pop","pop","pop"]values = [1,2,3,0,4,5,0,0,0,0]return = [1,2,3,4,5]Values leave in the order they joined, even when new values join between removals: 1, then 2, 3, 4, 5.
Constraints
1 <= operations.length <= 2000andvalues.length == operations.length- each
operations[i]is one ofpush,pop,peek,empty 1 <= values[i] <= 10^9whenoperations[i]ispush, andvalues[i] == 0otherwisepopandpeekare only called when the queue is not empty