Data structures problem 14 of 30

Queue from two stacks

Data structures
Medium

Implement a first-in, first-out queue with push(x) and pop(), using only two stacks (Python lists where you only call append and pop()).

Each operation should be O(1) on average.

Show hint

Pouring one stack into another reverses its order. You only need to pour when the "out" stack is empty.

Show solution

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

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

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

New items go on inbox. When outbox is empty, move everything across, which reverses it so the oldest item is on top. Each item is moved at most once, so the cost averages out to O(1) per operation (amortised).

Want a problem like this every day? See today's problem and keep a streak going.