Queue Using Two Stacks in DSA Java

Mental Model

Use two stacks to make a queue that adds items at one end and removes from the other, by reversing order twice.

Analogy: Imagine two trays of plates: you put plates on the first tray stacked up, then to serve, you flip all plates onto the second tray to get them in the right order to serve first-in-first-out.

stack1: top -> [5,4,3,2,1] -> bottom
stack2: top -> [] -> bottom

Dry Run Walkthrough

Input: enqueue 1, enqueue 2, enqueue 3, dequeue, enqueue 4, dequeue

Goal: Show how two stacks work together to behave like a queue with FIFO order

Step 1: enqueue 1: push 1 onto stack1

stack1: top -> [1] -> bottom
stack2: top -> [] -> bottom

Why: Add new item to stack1 to keep insertion order

Step 2: enqueue 2: push 2 onto stack1

stack1: top -> [2,1] -> bottom
stack2: top -> [] -> bottom

Why: Keep adding new items on top of stack1

Step 3: enqueue 3: push 3 onto stack1

stack1: top -> [3,2,1] -> bottom
stack2: top -> [] -> bottom

Why: Stack1 holds all new items in order

Step 4: dequeue: stack2 empty, move all from stack1 to stack2 reversing order

stack1: top -> [] -> bottom
stack2: top -> [1,2,3] -> bottom

Why: Reversing stack1 into stack2 makes oldest item on top for dequeue

Step 5: dequeue: pop top of stack2 (1)

stack1: top -> [] -> bottom
stack2: top -> [2,3] -> bottom

Why: Remove oldest item from queue

Step 6: enqueue 4: push 4 onto stack1

stack1: top -> [4] -> bottom
stack2: top -> [2,3] -> bottom

Why: New items always go to stack1

Step 7: dequeue: pop top of stack2 (2)

stack1: top -> [4] -> bottom
stack2: top -> [3] -> bottom

Why: Continue removing from stack2 until empty

Result:

stack1: top -> [4] -> bottom
stack2: top -> [3] -> bottom
Dequeued items: 1, 2

Annotated Code

DSA Java

import java.util.Stack;

public class QueueUsingTwoStacks {
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();

    public void enqueue(int x) {
        stack1.push(x); // add new item to stack1
    }

    public int dequeue() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop()); // move all from stack1 to stack2 to reverse order
            }
        }
        if (stack2.isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return stack2.pop(); // pop from stack2 which has oldest item on top
    }

    public static void main(String[] args) {
        QueueUsingTwoStacks queue = new QueueUsingTwoStacks();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue.dequeue()); // should print 1
        queue.enqueue(4);
        System.out.println(queue.dequeue()); // should print 2
    }
}

stack1.push(x); // add new item to stack1

push new element to stack1 to keep insertion order

while (!stack1.isEmpty()) { stack2.push(stack1.pop()); // move all from stack1 to stack2 to reverse order }

transfer all elements from stack1 to stack2 to reverse order for dequeue

return stack2.pop(); // pop from stack2 which has oldest item on top

pop oldest element from stack2 to simulate queue dequeue

Output

1

2

Complexity Analysis

Time: O(1) amortized per operation because each element is moved at most twice between stacks

Space: O(n) because all elements are stored in two stacks combined

vs Alternative: Compared to a simple queue using linked list with O(1) enqueue and dequeue, this uses two stacks but still achieves amortized O(1) dequeue by reversing order only when needed

Edge Cases

dequeue from empty queue

throws RuntimeException with message 'Queue is empty'

DSA Java

if (stack2.isEmpty()) {
    throw new RuntimeException("Queue is empty");
}

enqueue then dequeue single element

returns the single element correctly

DSA Java

stack1.push(x); // add new item to stack1

multiple enqueues before any dequeue

all elements stored in stack1 until first dequeue triggers transfer

DSA Java

while (!stack1.isEmpty()) {
    stack2.push(stack1.pop());
}

When to Use This Pattern

When you need a queue but only have stacks, use two stacks to reverse order twice and simulate FIFO behavior.

Common Mistakes

Mistake: Trying to dequeue directly from stack1 without transferring to stack2
Fix: Always transfer all elements from stack1 to stack2 if stack2 is empty before dequeue

Mistake: Transferring elements from stack1 to stack2 on every dequeue
Fix: Only transfer when stack2 is empty to keep amortized O(1) complexity

Summary

Implements a queue using two stacks by reversing element order twice.

Use when you want queue behavior but only have stack operations available.

The key insight is that reversing twice restores the original order for FIFO.

Practice

1. What is the main idea behind implementing a Queue using two stacks?

easy

A. Use two stacks to reverse the order twice to maintain queue order

B. Use two stacks to store elements in sorted order

C. Use one stack and a linked list to simulate queue behavior

D. Use one stack for enqueue and another for dequeue operations

Solution

1. Step 1: Understand queue order

   A queue follows First-In-First-Out (FIFO) order, meaning the first element added is the first removed.

2. Step 2: Use two stacks to reverse order twice

   Stacks are Last-In-First-Out (LIFO). Using two stacks, we reverse the order twice, restoring FIFO behavior.

3. Final Answer:

   Use two stacks to reverse the order twice to maintain queue order -> Option A

4. Quick Check:

   Two stacks reverse twice = queue order [OK]

Hint: Two stacks reverse order twice to simulate queue [OK]

Common Mistakes:

• Thinking one stack alone can maintain queue order
• Assuming stacks keep elements sorted
• Confusing enqueue and dequeue operations

2. Which of the following is the correct Java method signature for enqueue operation in a queue implemented using two stacks?

easy

A. public int enqueue(int x)

B. void enqueue(int x)

C. public void enqueue() int x

D. public void enqueue(int x)

Solution

1. Step 1: Identify correct Java method signature

   In Java, method signature includes access modifier, return type, method name, and parameters. Enqueue adds an element and returns nothing, so return type is void.

2. Step 2: Check each option

   public void enqueue(int x) has public access, void return type, method name enqueue, and int parameter. This is correct syntax.

3. Final Answer:

   public void enqueue(int x) -> Option D

4. Quick Check:

   Method signature with void return and int parameter [OK]

Hint: Enqueue returns void and takes element parameter [OK]

Common Mistakes:

• Missing return type or wrong return type
• Incorrect parameter placement
• Syntax errors like misplaced braces

3. Consider the following Java code snippet implementing dequeue operation using two stacks. What will be the output after these operations?

QueueUsingTwoStacks q = new QueueUsingTwoStacks();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
System.out.println(q.dequeue());
q.enqueue(40);
System.out.println(q.dequeue());

medium

A. 10\n20

B. 30\n10

C. 10\n30

D. 20\n30

Solution

1. Step 1: Trace enqueue operations

   Elements enqueued in order: 10, 20, 30. Queue order is [10, 20, 30].

2. Step 2: Dequeue and enqueue operations

   First dequeue removes 10 (front). Then enqueue 40, queue is [20, 30, 40]. Second dequeue removes 20.

3. Final Answer:

   10 20 -> Option A

4. Quick Check:

   Dequeue order matches enqueue FIFO [OK]

Hint: Dequeue returns oldest enqueued element [OK]

Common Mistakes:

• Assuming stack order instead of queue order
• Mixing up enqueue and dequeue sequence
• Forgetting to enqueue after dequeue

4. The following code snippet for dequeue operation in a queue using two stacks throws an error. What is the error and how to fix it?

public int dequeue() {
  if (stack2.isEmpty()) {
    while (!stack1.isEmpty()) {
      stack2.push(stack1.pop());
    }
  }
  return stack1.pop();
}

medium

A. Missing check for empty queue before popping

B. Returns from wrong stack; should pop from stack2

C. Should push from stack2 to stack1 instead

D. Syntax error: missing semicolon after while loop

Solution

1. Step 1: Analyze dequeue logic

   When stack2 is empty, elements are moved from stack1 to stack2 to reverse order. Dequeue should pop from stack2 to get the front element.

2. Step 2: Identify error in return statement

   Code returns stack1.pop(), which is incorrect. It should return stack2.pop() to dequeue correctly.

3. Final Answer:

   Returns from wrong stack; should pop from stack2 -> Option B

4. Quick Check:

   Dequeue pops from stack2 after transfer [OK]

Hint: Dequeue pops from stack2 after transfer [OK]

Common Mistakes:

• Popping from stack1 instead of stack2
• Not transferring elements when stack2 is empty
• Ignoring empty queue condition

5. You want to implement a queue using two stacks where enqueue is O(1) time and dequeue is amortized O(1). Which approach is best?

Options:
A) Push new elements to stack1 on enqueue; on dequeue, if stack2 empty, move all from stack1 to stack2, then pop stack2.
B) Push new elements to stack2 on enqueue; on dequeue, pop from stack1.
C) Push new elements to stack1 on enqueue; on dequeue, pop from stack1 directly.
D) Push new elements to stack2 on enqueue; on dequeue, if stack1 empty, move all from stack2 to stack1, then pop stack1.

hard

A. Push to stack1 on enqueue; dequeue from stack1 directly

B. Push to stack2 on enqueue; dequeue from stack1 directly

C. Push to stack1 on enqueue; transfer to stack2 on dequeue if empty

D. Push to stack2 on enqueue; transfer to stack1 on dequeue if empty

Solution

1. Step 1: Understand enqueue and dequeue costs

   Enqueue should be O(1), so pushing to a stack directly is best. Dequeue can be amortized O(1) by transferring elements only when needed.

2. Step 2: Identify correct approach

   Push to stack1 on enqueue; transfer to stack2 on dequeue if empty pushes to stack1 on enqueue (O(1)). On dequeue, if stack2 is empty, transfer all from stack1 to stack2 (reversing order), then pop from stack2. This gives amortized O(1) dequeue.

3. Final Answer:

   Push to stack1 on enqueue; transfer to stack2 on dequeue if empty -> Option C

4. Quick Check:

   Enqueue O(1), dequeue amortized O(1) with two stacks [OK]

Hint: Enqueue to stack1; dequeue from stack2 after transfer [OK]

Common Mistakes:

• Pushing to wrong stack on enqueue
• Popping from wrong stack on dequeue
• Not transferring elements when needed