Building a Queue from Stacks

Use one stack as an inbox for incoming items and one as an outbox for outgoing ones. To push, you push onto the inbox. To pop, if the outbox is empty you move everything from the inbox to the outbox, which reverses the order, and then pop from the outbox.

class MyQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []

    def push(self, value):
        self.inbox.append(value)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

    def peek(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox


queue = MyQueue()
queue.push(1)
queue.push(2)
print(queue.pop())
queue.push(3)
print(queue.pop())
print(queue.peek())

The outputs are 1, 2 and 3. Pushing one and two and then popping gives back 1, because the transfer to the outbox reversed the order. Pushing three afterwards does not disturb the outbox, so the next pop still returns 2.

The mechanism is that the reversal happens exactly once per item. An item is pushed onto the inbox, moved to the outbox at most once, and then removed from the outbox. The outbox is only refilled when it is empty, so the first pop after a refill pays for the transfer and every later pop is free.

The trade-off to name is the amortised cost. A single pop can be linear because it might transfer the whole inbox, but the total work over n pushes and n pops is linear, so the amortised cost per operation is constant. The second point is that this structure is really a deque, since you could also push to and pop from the outbox end and get a different behaviour. In practice, of course, you would just use a list with an index or a collections.deque rather than implement this yourself, but knowing the trick is what the question is testing.

The reverse trick: to pop, move every element from the main queue to the helper queue, inserting each at the front. That reverses the order, so the element at the front of the helper queue is the most recently pushed one, and you remove it from there.

from collections import deque


class MyStack:
    def __init__(self):
        self.main = deque()
        self.helper = deque()

    def push(self, value):
        self.main.append(value)

    def pop(self):
        if not self.helper:
            while self.main:
                self.helper.appendleft(self.main.popleft())
        return self.helper.popleft()

    def top(self):
        if not self.helper:
            while self.main:
                self.helper.appendleft(self.main.popleft())
        return self.helper[0]


stack = MyStack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())
print(stack.top())

The outputs are 3 and 2. The most recently pushed value comes off first, which is the stack behaviour we want even though the underlying structure is a queue.

The mechanism is the reversal during the transfer. Pushing one, two and three leaves the main queue holding them in that order. Moving each one to the front of the helper queue puts three at the front, then two, then one, so the front of the helper queue is three and popping it gives the last pushed element.

The trade-off to name is the amortised cost. Pushing is constant time, but popping can be linear because it may move every element across. Each element is moved at most once, because the helper queue is only refilled when it is empty and the main queue is only refilled from it. So over n pushes and n pops the total work is linear and the amortised cost per operation is constant, but the worst case for a single pop is linear. That is worse than the stack-based queue in the previous answer, where the transfer happens on the push side and popping is always cheap.