Implement Stack Using Queue — Two Approaches Explained With Java
Every data structures interview has at least one 'simulate this with that' question, and implementing a stack using a queue is one of the most popular. It's not just a puzzle — it reveals whether you truly understand how both structures work at their core, not just how to call .push() and .pop(). Companies like Google, Amazon, and Meta use this question specifically because it exposes shallow memorisers from real thinkers.
A stack is Last-In-First-Out (LIFO) — think browser back-button history or undo in a text editor. A queue is First-In-First-Out (FIFO) — think a print job queue or a message broker. Their access patterns are mirror opposites. The challenge here is to take only queue operations (enqueue at rear, dequeue from front, peek front, isEmpty) and compose them in a way that gives you LIFO behaviour. No cheating with arrays or linked lists directly.
By the end of this article you'll understand two distinct strategies — making push expensive vs making pop expensive — with full runnable Java code for each. You'll know when to choose one over the other, the gotchas that trip people up in interviews, and exactly how to explain your trade-off decision to an interviewer who is actively probing your thinking.
The Core Insight: Reversing Order Is the Whole Game
Before writing a single line of code, you need to lock in the mental model. A queue always gives you its oldest element. A stack always gives you its newest element. To fake a stack, you need to reverse the insertion order — the newest element must be at the front of the queue so it's the first one dequeued.
There are exactly two moments in the lifecycle of an element where you can pay the cost of reversal: when it arrives (push), or when it's requested (pop). This gives you two strategies:
Strategy 1 — Push-Heavy: Every new element is rotated to the front of the queue immediately after insertion. Pop is then O(1) because the newest item is already at the front.
Strategy 2 — Pop-Heavy: Push is O(1) — just enqueue normally. But when you pop, you drain all but the last element into a second queue, grab the last one, then swap the queues back.
Neither is universally better. Your choice should depend on your read/write ratio. If your use case reads far more than it writes (like a browser undo history that users rarely write to but frequently read from), push-heavy wins. If you write frequently and read occasionally, pop-heavy wins. Knowing this trade-off is what separates a good interview answer from a great one.
import java.util.LinkedList; import java.util.Queue; /** * This file is NOT the full implementation — it's a visual warm-up. * It demonstrates exactly WHY naive queue operations give you FIFO, * which is the OPPOSITE of what a stack needs. */ public class StackConceptDiagram { public static void main(String[] args) { Queue<Integer> naiveQueue = new LinkedList<>(); // Simulate three pushes: 1, then 2, then 3 naiveQueue.offer(1); // queue: [1] naiveQueue.offer(2); // queue: [1, 2] naiveQueue.offer(3); // queue: [1, 2, 3] System.out.println("=== What a plain Queue gives you ==="); System.out.println("(FIFO — oldest element comes out first)"); while (!naiveQueue.isEmpty()) { // poll() removes from the FRONT — so 1 comes out first System.out.println("Dequeued: " + naiveQueue.poll()); } System.out.println(); System.out.println("=== What a Stack should give you ==="); System.out.println("(LIFO — newest element comes out first)"); System.out.println("Expected order: 3, 2, 1"); System.out.println("Goal: make the queue behave this way."); } }
(FIFO — oldest element comes out first)
Dequeued: 1
Dequeued: 2
Dequeued: 3
=== What a Stack should give you ===
(LIFO — newest element comes out first)
Expected order: 3, 2, 1
Goal: make the queue behave this way.
Strategy 1 — Push-Heavy: Pay the Cost on the Way In
This approach keeps the queue permanently ordered so that the most recently pushed element always sits at the front. Every time you push a new element, you rotate all existing elements behind it. Here's exactly how the rotation works:
- Enqueue the new element — it lands at the rear.
- Rotate all elements that were already in the queue to behind the new element: dequeue each old element and re-enqueue it.
After the rotation, the new element is at the front. Pop simply calls poll(). Peek simply calls peek(). Both are O(1).
The cost is push, which is O(n) — for each push you do n dequeue-enqueue cycles where n is the current size. If you push 1000 elements, the last push does 999 rotations.
This is the right choice for read-dominated workloads. Think of an undo stack in a word processor — users type constantly (many pushes) but undo rarely (few pops). Wait — that's actually write-heavy, so you'd use pop-heavy there. A better fit for push-heavy is a recently-viewed items list where you display the last item constantly (many peeks) but add items infrequently.
import java.util.LinkedList; import java.util.Queue; /** * Stack implemented using a SINGLE Queue. * Strategy: Push is O(n), Pop and Peek are O(1). * * After every push, the queue is rotated so the newest * element sits permanently at the front. */ public class StackUsingQueuePushHeavy { // One queue is all we need for this strategy private Queue<Integer> mainQueue = new LinkedList<>(); /** * Push a new value onto the stack. * Time Complexity: O(n) — we rotate all existing elements. */ public void push(int value) { // Step 1: Add the new element to the rear of the queue mainQueue.offer(value); // At this point, 'value' is at the rear — wrong position. // We need it at the front. Rotate all PREVIOUS elements behind it. // Step 2: Rotate (size - 1) elements from front to rear // After this loop, 'value' will be at the front. int rotationsNeeded = mainQueue.size() - 1; for (int i = 0; i < rotationsNeeded; i++) { // Take the front element and put it at the back int frontElement = mainQueue.poll(); mainQueue.offer(frontElement); } // Now the queue front = most recently pushed element (LIFO order achieved) } /** * Remove and return the top element of the stack. * Time Complexity: O(1) — front of queue IS the stack top. */ public int pop() { if (isEmpty()) { throw new RuntimeException("Stack underflow — cannot pop from an empty stack"); } return mainQueue.poll(); // Front is always the most recently pushed element } /** * Look at the top element without removing it. * Time Complexity: O(1) */ public int peek() { if (isEmpty()) { throw new RuntimeException("Stack is empty — nothing to peek at"); } return mainQueue.peek(); // Front = top of our logical stack } public boolean isEmpty() { return mainQueue.isEmpty(); } public int size() { return mainQueue.size(); } // ─── Main: Walk through the internal state step by step ─────────────────── public static void main(String[] args) { StackUsingQueuePushHeavy stack = new StackUsingQueuePushHeavy(); System.out.println("=== Push-Heavy Strategy Demo ==="); System.out.println(); // Push 10 stack.push(10); System.out.println("Pushed 10 | Internal queue: " + stack.mainQueue); // Queue: [10] — only one element, no rotation needed // Push 20 stack.push(20); System.out.println("Pushed 20 | Internal queue: " + stack.mainQueue); // After offer: [10, 20]. Rotate 1 time: move 10 to rear → [20, 10] // Push 30 stack.push(30); System.out.println("Pushed 30 | Internal queue: " + stack.mainQueue); // After offer: [20, 10, 30]. Rotate 2 times: move 20 → [10, 30, 20], move 10 → [30, 20, 10] System.out.println(); System.out.println("Peek (top of stack): " + stack.peek()); // Should be 30 System.out.println(); System.out.println("--- Popping all elements (should be LIFO: 30, 20, 10) ---"); while (!stack.isEmpty()) { System.out.println("Popped: " + stack.pop()); } System.out.println(); System.out.println("Stack is empty: " + stack.isEmpty()); } }
Pushed 10 | Internal queue: [10]
Pushed 20 | Internal queue: [20, 10]
Pushed 30 | Internal queue: [30, 20, 10]
Peek (top of stack): 30
--- Popping all elements (should be LIFO: 30, 20, 10) ---
Popped: 30
Popped: 20
Popped: 10
Stack is empty: true
Strategy 2 — Pop-Heavy: Pay the Cost on the Way Out
Here, push is trivially O(1) — you just enqueue normally. The queue accumulates elements in insertion order. The expensive work happens when you pop or peek.
When pop is called, you drain all elements except the last one into a second helper queue. The single remaining element in the main queue is your stack top — dequeue it and return it. Then swap the two queues so the helper becomes the main queue for the next operation.
Pop and peek are O(n). Push is O(1).
This strategy fits write-heavy, read-light workloads. Imagine a task scheduler that accepts thousands of tasks per second but processes the most-recent task only every few minutes. Most of the time it's just pushing — so making push cheap and pop expensive is the right trade-off.
Note that you need two queues for this strategy, whereas strategy 1 only needs one. That's an additional space consideration — though both strategies are O(n) overall in space. The two-queue approach is more intuitive and is what most interview candidates reach for first, which is why understanding the single-queue push-heavy approach gives you an edge.
import java.util.LinkedList; import java.util.Queue; /** * Stack implemented using TWO Queues. * Strategy: Push is O(1), Pop and Peek are O(n). * * Elements are pushed normally. On pop/peek, all but the * last element are migrated to the helper queue, then the * queues are swapped. */ public class StackUsingQueuePopHeavy { private Queue<Integer> mainQueue = new LinkedList<>(); private Queue<Integer> helperQueue = new LinkedList<>(); /** * Push a new value onto the stack. * Time Complexity: O(1) — just a plain enqueue. */ public void push(int value) { mainQueue.offer(value); // Queue grows in FIFO order: oldest at front, newest at rear. // We accept this — we'll deal with the order reversal on pop. } /** * Remove and return the top element of the stack (the last-pushed element). * Time Complexity: O(n) — we must drain (n-1) elements to expose the last one. */ public int pop() { if (isEmpty()) { throw new RuntimeException("Stack underflow — cannot pop from an empty stack"); } // Step 1: Move all elements except the last one into the helper queue. // The last element in mainQueue = the most recently pushed = stack top. while (mainQueue.size() > 1) { helperQueue.offer(mainQueue.poll()); } // Step 2: The one remaining element in mainQueue is our stack top. int stackTop = mainQueue.poll(); // Step 3: Swap references — helperQueue becomes the new mainQueue. // This avoids copying all elements back; we just swap which name points where. Queue<Integer> temp = mainQueue; mainQueue = helperQueue; helperQueue = temp; // helperQueue is now empty and ready for the next pop operation. return stackTop; } /** * Look at the top element without removing it. * Time Complexity: O(n) — same drain-and-restore process as pop. */ public int peek() { if (isEmpty()) { throw new RuntimeException("Stack is empty — nothing to peek at"); } // Drain all but the last element while (mainQueue.size() > 1) { helperQueue.offer(mainQueue.poll()); } // Peek at the stack top (last remaining in mainQueue) int stackTop = mainQueue.peek(); // Move the top element to helperQueue as well, then swap // so ALL elements are preserved after peek. helperQueue.offer(mainQueue.poll()); Queue<Integer> temp = mainQueue; mainQueue = helperQueue; helperQueue = temp; // After swap, mainQueue has all elements back but in reversed order — that's fine, // because peek doesn't change the logical stack state. return stackTop; } public boolean isEmpty() { return mainQueue.isEmpty(); } public int size() { return mainQueue.size(); } // ─── Main: Demonstrate the internal state at each step ─────────────────── public static void main(String[] args) { StackUsingQueuePopHeavy stack = new StackUsingQueuePopHeavy(); System.out.println("=== Pop-Heavy Strategy Demo ==="); System.out.println(); stack.push(10); System.out.println("Pushed 10 | mainQueue: " + stack.mainQueue); stack.push(20); System.out.println("Pushed 20 | mainQueue: " + stack.mainQueue); stack.push(30); System.out.println("Pushed 30 | mainQueue: " + stack.mainQueue); // Queue is in FIFO order: [10, 20, 30] — 30 is at the rear (stack top) System.out.println(); System.out.println("Peek (top of stack): " + stack.peek()); // Should be 30 System.out.println("mainQueue after peek: " + stack.mainQueue); // All elements intact System.out.println(); System.out.println("--- Popping all elements (should be LIFO: 30, 20, 10) ---"); while (!stack.isEmpty()) { System.out.println("Popped: " + stack.pop()); } System.out.println(); System.out.println("Stack is empty: " + stack.isEmpty()); } }
Pushed 10 | mainQueue: [10]
Pushed 20 | mainQueue: [10, 20]
Pushed 30 | mainQueue: [10, 20, 30]
Peek (top of stack): 30
mainQueue after peek: [10, 20, 30]
--- Popping all elements (should be LIFO: 30, 20, 10) ---
Popped: 30
Popped: 20
Popped: 10
Stack is empty: true
Complexity Comparison and When to Use Each Strategy
Now that you've seen both implementations working, let's lock in the decision framework. Time complexity alone doesn't tell the whole story — you need to consider your workload's push-to-pop ratio.
For interview purposes, both approaches are valid answers. What makes you stand out is immediately volunteering the trade-off and asking 'what's the expected operation distribution?' That question signals senior-level thinking.
In practice, the push-heavy single-queue approach is slightly cleaner for implementations where you control the entire data flow (e.g., a function call stack simulator). The pop-heavy two-queue approach maps more naturally to producer-consumer patterns where items are produced rapidly and consumed occasionally.
One subtle real-world note: Java's Stack class is actually built on Vector and is considered legacy. In production Java, you'd use ArrayDeque as a stack. This exercise's value is entirely conceptual — it forces you to truly understand LIFO vs FIFO mechanics, which is the real interview goal.
/** * A test harness that runs BOTH implementations against identical * inputs and confirms they produce identical LIFO output. * Run this to verify both strategies work correctly. */ import java.util.LinkedList; import java.util.Queue; public class StackOperationsTest { // ── Minimal Push-Heavy Stack (self-contained for testing) ────────────── static class PushHeavyStack { private Queue<Integer> queue = new LinkedList<>(); public void push(int value) { queue.offer(value); for (int i = 0; i < queue.size() - 1; i++) { queue.offer(queue.poll()); } } public int pop() { return queue.poll(); } public int peek() { return queue.peek(); } public boolean isEmpty() { return queue.isEmpty(); } } // ── Minimal Pop-Heavy Stack (self-contained for testing) ─────────────── static class PopHeavyStack { private Queue<Integer> mainQueue = new LinkedList<>(); private Queue<Integer> helperQueue = new LinkedList<>(); public void push(int value) { mainQueue.offer(value); } public int pop() { while (mainQueue.size() > 1) helperQueue.offer(mainQueue.poll()); int top = mainQueue.poll(); Queue<Integer> temp = mainQueue; mainQueue = helperQueue; helperQueue = temp; return top; } public int peek() { while (mainQueue.size() > 1) helperQueue.offer(mainQueue.poll()); int top = mainQueue.peek(); helperQueue.offer(mainQueue.poll()); Queue<Integer> temp = mainQueue; mainQueue = helperQueue; helperQueue = temp; return top; } public boolean isEmpty() { return mainQueue.isEmpty(); } } // ── Test Runner ──────────────────────────────────────────────────────── public static void main(String[] args) { int[] valuesToPush = {5, 15, 25, 35, 45}; PushHeavyStack pushHeavy = new PushHeavyStack(); PopHeavyStack popHeavy = new PopHeavyStack(); // Push the same values into both stacks for (int value : valuesToPush) { pushHeavy.push(value); popHeavy.push(value); } System.out.println("Both stacks loaded with: [5, 15, 25, 35, 45]"); System.out.println("Expected LIFO pop order: 45, 35, 25, 15, 5"); System.out.println(); System.out.printf("%-20s %-20s %-10s%n", "Push-Heavy Pop", "Pop-Heavy Pop", "Match?"); System.out.println("-".repeat(52)); boolean allMatch = true; while (!pushHeavy.isEmpty() && !popHeavy.isEmpty()) { int fromPushHeavy = pushHeavy.pop(); int fromPopHeavy = popHeavy.pop(); boolean match = (fromPushHeavy == fromPopHeavy); if (!match) allMatch = false; System.out.printf("%-20d %-20d %-10s%n", fromPushHeavy, fromPopHeavy, match ? "✓" : "✗ MISMATCH"); } System.out.println("-".repeat(52)); System.out.println("All results match: " + allMatch); } }
Expected LIFO pop order: 45, 35, 25, 15, 5
Push-Heavy Pop Pop-Heavy Pop Match?
----------------------------------------------------
45 45 ✓
35 35 ✓
25 25 ✓
15 15 ✓
5 5 ✓
----------------------------------------------------
All results match: true
| Feature / Aspect | Push-Heavy (1 Queue) | Pop-Heavy (2 Queues) |
|---|---|---|
| Number of queues needed | 1 | 2 |
| Push time complexity | O(n) — rotates all elements | O(1) — plain enqueue |
| Pop time complexity | O(1) — front is always stack top | O(n) — drains all but last |
| Peek time complexity | O(1) — front is always stack top | O(n) — same drain as pop |
| Space complexity | O(n) total | O(n) total |
| Best workload fit | Read-heavy (many peeks/pops) | Write-heavy (many pushes) |
| Implementation complexity | Slightly tricky (rotation loop) | Intuitive (drain and swap) |
| Beginner-friendliness | Harder to visualise initially | Easier to reason about |
| Real-world analogy | Sorting mail as it arrives | Sorting mail only when needed |
🎯 Key Takeaways
- The core problem is order reversal — a queue gives you the oldest element, a stack needs to give you the newest. Every line of code in both strategies exists purely to bridge that gap.
- Push-heavy (single queue) makes pop O(1) by paying the rotation cost upfront on every push — choose this when reads dominate writes.
- Pop-heavy (two queues) makes push O(1) by deferring the reversal cost until pop — choose this when writes dominate reads, like a high-throughput task queue.
- Peek in the pop-heavy approach must move the top element into the helper queue before swapping — skipping this step silently deletes the stack top, a bug that only surfaces on the next operation.
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Getting the rotation count wrong in push-heavy — rotating (queue.size()) times instead of (queue.size() - 1) — this moves the newly added element back to the rear instead of leaving it at the front. Fix: always snapshot the rotation count AFTER the offer() call and subtract 1, or use the for-loop condition
i < queue.size() - 1evaluated once before the loop with a pre-stored size variable. - ✕Mistake 2: Implementing peek() as pop() + push() in the pop-heavy approach — this technically returns the right value but silently corrupts the stack order because re-pushing the element puts it at the rear, not its original logical position. Fix: implement peek() with its own drain-observe-restore cycle that moves the top element into the helper queue before swapping, as shown in the StackUsingQueuePopHeavy example.
- ✕Mistake 3: Forgetting to throw an exception (or check isEmpty) before pop/peek — popping from an empty LinkedList-backed queue returns null in Java, which causes a NullPointerException the moment you try to unbox it into an int. Fix: always guard pop() and peek() with an isEmpty() check and throw an IllegalStateException or a custom runtime exception with a meaningful message like 'Stack underflow'.
Interview Questions on This Topic
- QCan you implement a stack using only one queue instead of two? Walk me through how push would work and what the time complexity trade-off is.
- QYou've implemented a stack using two queues where pop is O(n). Your interviewer says the system does 10,000 pushes per second but only 1 pop per minute. Should you switch strategies? Why?
- QIf I call peek() immediately after pop() on your pop-heavy implementation, will it return the correct element? Trace through the internal queue state after each call to prove it.
Frequently Asked Questions
Can I implement a stack using just one queue?
Yes — the push-heavy strategy does exactly this. After enqueuing the new element, you rotate all previous elements to the rear, leaving the newest element at the front. Pop and peek then become O(1) plain dequeue operations. The trade-off is that push becomes O(n).
Why would anyone implement a stack using a queue in the real world?
In practice you'd just use ArrayDeque directly in Java. The real value of this exercise is conceptual — it forces you to deeply understand LIFO vs FIFO mechanics, which is directly applicable when designing systems like message brokers, task schedulers, or undo systems where you choose between queue-like and stack-like access patterns.
What's the difference between the two strategies in terms of when to use them?
Use push-heavy when your application reads (pops or peeks) more than it writes — the O(n) cost is paid once on push so every read is O(1). Use pop-heavy when your application writes (pushes) far more than it reads — pushes are O(1) and the expensive O(n) drain only happens on the rare pop operation. Always ask about the expected operation ratio before deciding.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.