Queue from two stacks

Build first in, first out behaviour using only two last in, first out stacks.

Time O(1) amortisedSpace O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Pouring one stack into another reverses its order. Push new items onto the inbox. When the outbox runs dry, pour the whole inbox into it, and the oldest item ends up on top.

Code

C++PythonC#

class MyQueue {
    stack<int> inbox, outbox;
public:
    void enqueue(int x) { inbox.push(x); }

    int dequeue() {
        if (outbox.empty())
            while (!inbox.empty()) { outbox.push(inbox.top()); inbox.pop(); }
        int x = outbox.top(); outbox.pop(); return x;
    }
};

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

    def enqueue(self, x: int) -> None:
        self.inbox.append(x)

    def dequeue(self) -> int:
        if not self.outbox:
            while self.inbox: self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

public class MyQueue {
    readonly Stack<int> inbox = new(), outbox = new();

    public void Enqueue(int x) => inbox.Push(x);

    public int Dequeue() {
        if (outbox.Count == 0)
            while (inbox.Count > 0) outbox.Push(inbox.Pop());
        return outbox.Pop();
    }
}

Tips

Only pour when the outbox is empty. Pouring early would put newer items on top of older ones.
Each item is moved at most once, so the average cost per operation is constant.

In the .NET library

Use Queue<T> in real code. It is a circular buffer with O(1) Enqueue and Dequeue. This exercise is about understanding amortised cost.