An old printer's firmware only offers stacks: you can push onto the top, pop from the top, look at the top, and ask for the size. Jobs, however, must print in the order they arrived. Build a first-in, first-out queue of job ids on top of stacks.
Write a class StackQueue:
StackQueue()creates an empty queue.push(x)adds jobxto the back of the queue.pop()removes the job at the front and returns it.peek()returns the job at the front without removing it.is_empty()returnsTrueif no jobs are waiting.
pop and peek are only called when the queue is non-empty.
Use Python lists only as stacks: append, pop() with no argument, [-1] and len. No pop(0), no insert, no indexing into the middle, no deque.
q = StackQueue()
q.push(1)
q.push(2)
q.peek() # 1
q.pop() # 1
q.push(3)
q.pop() # 2
q.is_empty() # False
q.pop() # 3
q.is_empty() # True
Constraints: up to 4 * 10^5 calls in total; job ids fit in a 32-bit signed integer.
Each call may occasionally be slow, but any sequence of m calls should take O(m) time in total (amortized O(1) per call).
Show hint
pouring one stack into another reverses its order. If you only pour when the second stack runs dry, how many times can a single job be moved?