Queue from two stacks
Build a queue out of stacks. A queue hands items back in the order they arrived: first in, first out, like a line at a coffee shop. A stack hands back the newest item first: last in, first out, like a pile of plates.
Write a class MyQueue with four methods. The front of the queue is its oldest item, the next one to leave.
push(x)putsxat the back, behind every item already waiting.pop()takes the front item out and returns it.peek()returns the front item and leaves it in place.empty()returnsTrueif no items are waiting andFalseif any are.
Store the items only in Python lists used as stacks. On those lists you may call append(x), call pop() with no argument (it removes the last item), read the last item with [-1], and check the length or whether the list is empty. No pop(0), no insert, no other indexes, no deque. The tests cannot see which operations you use, so keeping this rule is up to you, as it would be with an interviewer watching.
In the examples, the calls run in order on one new MyQueue(). The output lists what the calls return, in order, leaving out push, which returns nothing.
push(4), push(7), push(9), peek(), pop(), pop(), empty()Output4, 4, 7, Falsepeek() and the first pop() both see 4, the oldest item. The second pop() gets 7. 9 is still inside, so empty() is False.
push(3), push(8), pop(), push(5), pop(), pop(), empty()Output3, 8, 5, True5 is pushed after the first pop(), but 8 arrived earlier, so 8 leaves first. After the last pop() nothing is left.
Pushed values are integers, 0 and negatives included.
pop()andpeek()are called only when the queue holds at least one item.At most 105 calls in total.
Only stack operations on lists:
append,pop(),[-1], and checking the length or emptiness.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.