Implement a Stack Using Two Queues

Easy20–25 min

Topics

StackQueueDesign

Companies

AmazonMicrosoftAdobe

Implement a LIFO stack using only queue operations — enqueue at the back, dequeue from the front, peek the front — supporting push(v), pop(), top(), isEmpty(), and size(). As with the array and linked-list versions, this takes a fixed sequence of operations and replays them, returning the result of every pop, top, isEmpty, and size call as an array. A queue naturally hands back its oldest element first — the opposite of what a stack needs. Two classic techniques bridge that gap, and they're complementary rather than one strictly beating the other: rotate the queue after every push so the newest value ends up at the front (cheap pop, expensive push), or drain the queue down to just its last element whenever something needs to come off the top (cheap push, expensive pop). Neither approach avoids the reordering work a real stack never needs in the first place — they just disagree about which operation should pay for it.

Test Case 1:

Input:ops = [push, push, push, pop, pop, top], args = [5, 10, 15, -, -, -]

Output:[15, 10, 5]

Explanation:push 5, 10, 15; pop returns 15 (last in), pop returns 10, top peeks at 5 without removing it.

Test Case 2:

Input:ops = [isEmpty, push, isEmpty, pop, isEmpty], args = [-, 7, -, -, -]

Output:[1, 0, 7, 1]

Explanation:Starts empty (isEmpty→1). After push(7) it's non-empty (isEmpty→0). pop removes and returns 7. Now it's empty again (isEmpty→1).

Test Case 3:

Input:ops = [push, push, size, pop, size], args = [1, 2, -, -, -]

Output:[2, 2, 1]

Explanation:After two pushes, size→2. pop removes the top (2) and returns it. size→1 afterward.

Constraints

◆1 ≤ number of operations ≤ 12
◆Each operation is one of push, pop, top, isEmpty, or size
◆0 ≤ pushed value ≤ 1000
◆pop and top return -1 when the stack is empty
◆Only queue operations (enqueue at the back, dequeue from the front, peek the front) may be used to store elements — no direct indexing into the middle
◆This version replays a fixed sequence of operations and reports the result of every pop, top, isEmpty, and size call, in order (push has no return value)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Push Costly — Rotate the Queue After Every Push

Good

Keep everything in a single queue. To push a value, enqueue it at the back like normal, then rotate the whole queue — dequeue from the front and immediately enqueue it at the back — exactly (size - 1) times. That walks every older element around to the back, one at a time, leaving the brand-new value sitting at the front. From then on, the queue's front is always the most recently pushed value, so pop and top are trivial O(1) reads from the front. The cost is pushed entirely onto push itself: it does O(size) work every time.

TimeO(n) per push, O(1) per pop/top

SpaceO(n)

Java

Try it out

class Solution {
    public int[] stackOpsFromQueues(String[] ops, int[] args) {
        Queue<Integer> q = new LinkedList<>();
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < ops.length; i++) {
            String op = ops[i];
            if (op.equals("push")) {
                q.add(args[i]);
                int rotations = q.size() - 1;
                for (int r = 0; r < rotations; r++) {
                    q.add(q.poll());
                }
            } else if (op.equals("pop")) {
                results.add(q.isEmpty() ? -1 : q.poll());
            } else if (op.equals("top")) {
                results.add(q.isEmpty() ? -1 : q.peek());
            } else if (op.equals("isEmpty")) {
                results.add(q.isEmpty() ? 1 : 0);
            } else {
                results.add(q.size());
            }
        }
        int[] output = new int[results.size()];
        for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
        return output;
    }
}

Pop Costly — Two Queues, Transfer on Pop

Optimal

The complementary trade-off: keep push cheap instead of pop. Every push is a plain enqueue onto q1 — O(1), no rotation. All the work happens when something needs to come off the top: drain every element except the last from q1 into a second queue q2 (dequeue from q1, enqueue into q2), leaving only the most-recently-pushed value in q1 — dequeue that one as the answer, then swap the roles of q1 and q2 so the next push continues on the (now-repopulated) main queue. Tracking the most recent value in a separate variable, updated on every push, makes top() an O(1) read too instead of repeating the drain-and-restore dance.

TimeO(1) per push, O(n) per pop