Implement Stack Using Queue in DSA Java

Mental Model

A stack works like a pile where you add and remove from the top. A queue works like a line where you add at the end and remove from the front. To make a stack using a queue, we reorder the queue so the newest item is always at the front.

Analogy: Imagine a line of people where the last person to join wants to be served first. To do this, after a new person joins at the end, everyone in front moves behind them so the new person is now at the front of the line.

Queue: front -> [1] -> 2 -> 3 -> null
Stack top is the front of the queue
↑

Dry Run Walkthrough

Input: Push 1, Push 2, Push 3, Pop

Goal: Use one queue to behave like a stack and show the top element after each operation

Step 1: Push 1: enqueue 1

Queue: front -> [1] -> null

Why: Add first element normally

Step 2: Push 2: enqueue 2, then rotate queue to move 2 to front

Queue: front -> [2] -> 1 -> null

Why: Rotate so newest element is at front to simulate stack top

Step 3: Push 3: enqueue 3, then rotate queue to move 3 to front

Queue: front -> [3] -> 2 -> 1 -> null

Why: Newest element must be at front for stack behavior

Step 4: Pop: dequeue front element (3)

Queue: front -> [2] -> 1 -> null

Why: Remove top element of stack which is front of queue

Result:

Queue: front -> [2] -> 1 -> null
Popped element: 3

Annotated Code

DSA Java

import java.util.LinkedList;
import java.util.Queue;

public class StackUsingQueue {
    private Queue<Integer> queue = new LinkedList<>();

    public void push(int x) {
        queue.offer(x); // add new element at end
        int size = queue.size();
        // rotate queue to move new element to front
        for (int i = 0; i < size - 1; i++) {
            int val = queue.poll(); // remove front
            queue.offer(val); // add it back at end
        }
    }

    public int pop() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return queue.poll(); // remove front which is top of stack
    }

    public int top() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return queue.peek(); // front is top
    }

    public boolean empty() {
        return queue.isEmpty();
    }

    public static void main(String[] args) {
        StackUsingQueue stack = new StackUsingQueue();
        stack.push(1);
        System.out.println("Top after push 1: " + stack.top());
        stack.push(2);
        System.out.println("Top after push 2: " + stack.top());
        stack.push(3);
        System.out.println("Top after push 3: " + stack.top());
        int popped = stack.pop();
        System.out.println("Popped element: " + popped);
        System.out.println("Top after pop: " + stack.top());
    }
}

queue.offer(x); // add new element at end

enqueue new element at queue's end

for (int i = 0; i < size - 1; i++) { int val = queue.poll(); queue.offer(val); }

rotate queue to move new element to front simulating stack top

return queue.poll(); // remove front which is top of stack

pop removes the front element which is stack top

return queue.peek(); // front is top

top returns front element without removing

Output

Top after push 1: 1

Top after push 2: 2

Top after push 3: 3

Popped element: 3

Top after pop: 2

Complexity Analysis

Time: O(n) for push because we rotate all elements to move new element to front; O(1) for pop and top

Space: O(n) because all elements are stored in the queue

vs Alternative: Compared to using two queues, this single queue approach uses less space but push is slower due to rotation

Edge Cases

Pop or top on empty stack

Throws RuntimeException with message 'Stack is empty'

DSA Java

if (queue.isEmpty()) {
    throw new RuntimeException("Stack is empty");
}

Push single element

Element is added and becomes top immediately

DSA Java

queue.offer(x);

When to Use This Pattern

When you need last-in-first-out behavior but only have a first-in-first-out structure, use queue rotation to simulate stack operations.

Common Mistakes

Mistake: Not rotating the queue after push, so the newest element is not at the front
Fix: Rotate the queue by dequeuing and enqueuing all elements except the last pushed one

Mistake: Using two queues unnecessarily when one queue with rotation suffices
Fix: Use a single queue and rotate it after each push to keep newest element at front

Summary

Implements a stack using a single queue by rotating elements to keep the newest on front.

Use when only queue operations are allowed but stack behavior is needed.

The key is rotating the queue after each push to simulate stack's top at the queue's front.

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use one queue and reorder elements to simulate stack behavior

B. Use two stacks to simulate a queue

C. Use a linked list to implement both stack and queue

D. Use an array to simulate queue operations

Solution

1. Step 1: Understand stack and queue behaviors

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue

   By reordering elements in a single queue after each push, we can simulate LIFO behavior of a stack.

3. Final Answer:

   Use one queue and reorder elements to simulate stack behavior -> Option A

4. Quick Check:

   Stack via queue = reorder in one queue [OK]

Hint: Remember stack is LIFO; reorder queue to mimic it [OK]

Common Mistakes:

• Confusing stack with queue behavior
• Using two stacks instead of queues
• Ignoring element order after push

2. Which of the following is the correct Java syntax to declare a queue of integers using LinkedList?

easy

A. LinkedList<Integer> queue = new Queue<>();

B. Queue<int> queue = new LinkedList<>();

C. Queue<Integer> queue = new LinkedList<>();

D. Queue<Integer> queue = new Queue<>();

Solution

1. Step 1: Use interface Queue with LinkedList implementation

   In Java, Queue is an interface and LinkedList implements it. Use generics with wrapper class Integer.

2. Step 2: Check syntax correctness

   Queue<Integer> queue = new LinkedList<>(); is correct syntax for declaring a queue of integers.

3. Final Answer:

   Queue<Integer> queue = new LinkedList<>(); -> Option C

4. Quick Check:

   Queue<Integer> with LinkedList = correct syntax [OK]

Hint: Use wrapper classes and interface for queue declaration [OK]

Common Mistakes:

• Using primitive int instead of Integer
• Trying to instantiate interface Queue directly
• Confusing LinkedList and Queue syntax

3. What will be the output of the following code snippet implementing stack push using one queue?

Queue<Integer> q = new LinkedList<>();
// Push 1
q.add(1);
// Push 2
q.add(2);
// Reorder queue to simulate stack push
for (int i = 0; i < q.size() - 1; i++) {
  q.add(q.remove());
}
System.out.println(q.remove());

medium

A. 1

B. 2

C. Queue is empty

D. Runtime error

Solution

1. Step 1: Add elements 1 and 2 to queue

   Queue after adds: front -> 1, 2 -> rear

2. Step 2: Reorder queue to simulate stack push

   Loop runs q.size()-1 = 1 time: remove 1, add 1 back. Queue becomes front -> 2, 1 -> rear

3. Step 3: Remove and print element

   q.remove() removes front element 2, which is printed.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   Reordered queue front = last pushed = 2 [OK]

Hint: After push reorder, front is last pushed element [OK]

Common Mistakes:

• Not reordering queue after push
• Printing wrong element without remove
• Confusing queue front with rear

4. Identify the error in this stack pop implementation using one queue:

public int pop() {
  if (queue.isEmpty()) return -1;
  return queue.remove();
}

medium

A. No error, code works correctly

B. Queue should be cleared after pop

C. Should use queue.peek() instead of remove()

D. Pop removes the oldest element, not the last pushed

Solution

1. Step 1: Understand queue remove() behavior

   queue.remove() removes the front element, which is the oldest inserted, not the last pushed.

2. Step 2: Check stack pop requirement

   Stack pop must remove the last pushed element (LIFO), but this code removes FIFO element.

3. Final Answer:

   Pop removes the oldest element, not the last pushed -> Option D

4. Quick Check:

   Queue remove() = FIFO, stack pop = LIFO [OK]

Hint: Pop must remove last pushed, not queue front [OK]

Common Mistakes:

• Using queue.remove() directly for pop
• Ignoring element order after push
• Not reordering queue to simulate stack

5. You want to implement a stack using two queues. Which sequence of operations correctly simulates the pop() method?

hard

A. Move all but last element from queue1 to queue2, remove last from queue1, swap queues

B. Remove front element from queue1 directly

C. Add element to queue2, then remove from queue1

D. Swap queues without removing any element

Solution

1. Step 1: Understand two-queue stack pop logic

   To pop last pushed element, move all except last from queue1 to queue2, then remove last from queue1.

2. Step 2: Swap queues for next operations

   After removal, swap queue1 and queue2 references to maintain stack state.

3. Final Answer:

   Move all but last element from queue1 to queue2, remove last from queue1, swap queues -> Option A

4. Quick Check:

   Pop with two queues = move all but last, remove last, swap [OK]

Hint: Pop = move all but last, remove last, then swap queues [OK]

Common Mistakes:

• Removing front element directly
• Not swapping queues after pop
• Adding elements to wrong queue during pop