Implement a Queue Using Stacks

Implement a first in, first out queue using only stacks. Support:

push(x): add x at the back
pop(): remove and return the front element
peek(): return the front element
empty(): return whether the queue is empty

You may only use stack operations: push to the top, pop from the top, peek at the top, size, and is-empty. In Java, a Deque<Integer> backed by ArrayDeque provides these as push, pop, peek, size, and isEmpty: push adds at the top and pop removes from the top. pop throws NoSuchElementException on an empty stack, so the queue below checks first and returns an OptionalInt, a container that holds one int or nothing.

LeetCode: 232. Implement Queue using Stacks

Example

Text

push(1), push(2), push(3)
peek() -> 1, pop() -> 1
push(4)
pop() -> 2, pop() -> 3, pop() -> 4, pop() -> empty

The core idea

A stack reverses the order of whatever passes through it. A queue needs the opposite order from a stack, so moving elements from one stack to another (reversing them once) turns stack order into queue order.

Brute force: keep the oldest element on top

Keep all elements in one stack, with the oldest on top, so pop is a plain stack pop. To push, move everything to a helper stack, push the new element, and move everything back on top of it.

Walkthrough of push(3) when the stack holds 1 and 2 (bottom → top: [2, 1], oldest on top):

step	main (bottom → top)	helper (bottom → top)
start	[2, 1]	[]
move all to helper	[]	[1, 2]
push 3	[3]	[1, 2]
move all back	[3, 2, 1]	[]

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.OptionalInt;

public class Main {
    static class MyQueue {
        private final Deque<Integer> stack = new ArrayDeque<>(); // oldest element on top

        void push(int x) {
            Deque<Integer> helper = new ArrayDeque<>();
            while (!stack.isEmpty()) {
                helper.push(stack.pop());
            }
            stack.push(x);
            while (!helper.isEmpty()) {
                stack.push(helper.pop());
            }
        }

        OptionalInt pop() {
            return stack.isEmpty() ? OptionalInt.empty() : OptionalInt.of(stack.pop());
        }

        OptionalInt peek() {
            return stack.isEmpty() ? OptionalInt.empty() : OptionalInt.of(stack.peek());
        }

        boolean empty() {
            return stack.isEmpty();
        }
    }

    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.push(1);
        q.push(2);
        q.push(3);
        System.out.println(q.peek() + " " + q.pop());
        q.push(4);
        System.out.println(q.pop() + " " + q.pop() + " " + q.pop() + " " + q.pop() + " " + q.empty());
    }
}

Output

OptionalInt[1] OptionalInt[1]
OptionalInt[2] OptionalInt[3] OptionalInt[4] OptionalInt.empty true

Time: push is O(n): it moves every element twice. pop, peek, and empty are O(1). Space: O(n).

Optimal: an inbox stack and an outbox stack

Do not move elements on every push. Use two stacks:

inbox: every push goes here, in O(1).
outbox: pop and peek read from here.

When outbox is empty and someone needs the front element, pour all of inbox into outbox. That reverses the elements, so the oldest one ends up on top of outbox. Do not pour while outbox still has elements: they are older than anything in inbox, so they have to come out first.

Walkthrough of the example (both stacks shown bottom → top):

operation	inbox	outbox	returns
push 1, 2, 3	[1, 2, 3]	[]
peek (outbox empty: pour)	[]	[3, 2, 1]	1
pop	[]	[3, 2]	1
push 4	[4]	[3, 2]
pop (outbox not empty: no pour)	[4]	[3]	2
pop	[4]	[]	3
pop (outbox empty: pour)	[]	[]	4

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.OptionalInt;

public class Main {
    static class MyQueue {
        private final Deque<Integer> inbox = new ArrayDeque<>();
        private final Deque<Integer> outbox = new ArrayDeque<>();

        void push(int x) {
            inbox.push(x);
        }

        // Refill the outbox only when it is empty.
        private void shift() {
            if (outbox.isEmpty()) {
                while (!inbox.isEmpty()) {
                    outbox.push(inbox.pop());
                }
            }
        }

        OptionalInt pop() {
            shift();
            return outbox.isEmpty() ? OptionalInt.empty() : OptionalInt.of(outbox.pop());
        }

        OptionalInt peek() {
            shift();
            return outbox.isEmpty() ? OptionalInt.empty() : OptionalInt.of(outbox.peek());
        }

        boolean empty() {
            return inbox.isEmpty() && outbox.isEmpty();
        }
    }

    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.push(1);
        q.push(2);
        q.push(3);
        System.out.println(q.peek() + " " + q.pop());
        q.push(4);
        System.out.println(q.pop() + " " + q.pop() + " " + q.pop() + " " + q.pop() + " " + q.empty());
    }
}

Output

OptionalInt[1] OptionalInt[1]
OptionalInt[2] OptionalInt[3] OptionalInt[4] OptionalInt.empty true

Time: push is O(1). pop and peek are amortized O(1): a single call can take O(n) when it pours, but each element is moved from inbox to outbox at most once in its lifetime, so n operations cost O(n) in total. Space: O(n).

peek may have to pour inbox into outbox, so it changes the internal state even though it removes nothing. empty has to check both stacks.

Edge cases

pop or peek on an empty queue: OptionalInt.empty().
Interleaved pushes and pops: correct, because the outbox is only refilled when it is empty.