Premium

Queue Using Stacks

Basic Algorithms
≈ 2 min read

Turning LIFO into FIFO

Two stacks can implement a queue even though each stack by itself returns elements in reverse order. The idea is a double reversal: the first stack accepts new elements, and they are moved into the second stack for reading. After the transfer, the oldest element ends up on top of the second stack. 

class QueueWithStacks {
    private final Deque<Integer> input = new ArrayDeque<>();
    private final Deque<Integer> output = new ArrayDeque<>();

    void add(int value) {
        input.push(value);
    }

    int remove() {
        moveIfNeeded();
        return output.pop();
    }

    private void moveIfNeeded() {
        if (!output.isEmpty()) {
            return;
        }
        while (!input.isEmpty()) {
            output.push(input.pop());
        }
    }
}

Why we should not transfer after every insertion

As long as output contains elements, their order is already correct and does not need to change. New values can accumulate in input. A transfer happens only when an element must be removed and output is empty.

Amortized complexity

One particular remove() call may transfer many elements and take O(n) time. But each element follows the path input → output only once during the queue's lifetime, and is then removed once. Therefore a sequence of operations has an amortized cost of O(1) per operation.

Amortized analysis looks at a sequence of operations. It does not claim that every individual call takes constant time; it shows that rare expensive transfers are spread across many cheap operations.
Back Next