Queue Using Two Stacks in DSA Java - Execution Trace

Concept Flow - Queue Using Two Stacks

Enqueue Operation

↓

Push element onto Stack1

↓

Done

↓

Dequeue Operation

↓

Is Stack2 empty?

No→Pop from Stack2

Yes↓

Transfer all elements from Stack1 to Stack2

↓

Pop from Stack2

↓

Done

Enqueue pushes elements onto the first stack. Dequeue pops from the second stack; if empty, elements are moved from the first stack to the second to reverse order.

Execution Sample

DSA Java

Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();

// Enqueue 1
stack1.push(1);

// Enqueue 2
stack1.push(2);

// Dequeue
if(stack2.isEmpty()) {
  while(!stack1.isEmpty()) stack2.push(stack1.pop());
}
int val = stack2.pop();

This code enqueues 1 and 2, then dequeues the first element (1) using two stacks.

Execution Table

Step	Operation	Stack1 State (top→bottom)	Stack2 State (top→bottom)	Pointer Changes	Visual State
1	Enqueue 1: push 1 to stack1	[1]	[]	stack1 top points to 1	stack1: 1 → null, stack2: empty
2	Enqueue 2: push 2 to stack1	[2, 1]	[]	stack1 top points to 2	stack1: 2 → 1 → null, stack2: empty
3	Dequeue: stack2 empty, transfer all from stack1 to stack2	[]	[2, 1]	stack1 emptied, stack2 top points to 2	stack1: empty, stack2: 2 → 1 → null
4	Dequeue: pop from stack2	[]	[1]	stack2 top points to 1	stack1: empty, stack2: 1 → null
5	Dequeue complete, returned 2	[]	[1]	No pointer change	stack1: empty, stack2: 1 → null
6	Dequeue: pop from stack2	[]	[]	stack2 empty	stack1: empty, stack2: empty
7	Dequeue complete, returned 1	[]	[]	No pointer change	stack1: empty, stack2: empty
8	Dequeue: both stacks empty, queue empty	[]	[]	No pointer change	stack1: empty, stack2: empty

💡 Execution stops when both stacks are empty and no elements remain to dequeue.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
stack1	[]	[1]	[2, 1]	[]	[]	[]	[]	[]	[]
stack2	[]	[]	[]	[2, 1]	[1]	[1]	[]	[]	[]
Dequeued Value	null	null	null	null	2	2	1	1	null

Key Moments - 3 Insights

Why do we transfer all elements from stack1 to stack2 only when stack2 is empty?

Because stack2 holds elements in correct dequeue order. Transferring only when stack2 is empty avoids unnecessary moves and preserves order, as shown in step 3 of execution_table.

What happens if we try to dequeue when both stacks are empty?

The queue is empty, so no element can be dequeued. This is shown in step 8 where both stacks are empty and dequeue operation stops.

Why does popping from stack2 give the correct queue front element?

Because transferring elements from stack1 to stack2 reverses their order, making the oldest element on top of stack2. Step 4 shows popping from stack2 returns the first enqueued element.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the state of stack1 and stack2 after transferring elements?

A stack1 has [1, 2], stack2 is empty

B stack1 is empty, stack2 has [2, 1] with 2 on top

C stack1 is empty, stack2 has [1, 2] with 1 on top

D stack1 has [2], stack2 has [1]

💡 Hint

Check the 'Stack1 State' and 'Stack2 State' columns at step 3 in execution_table.

At which step does the first dequeue operation return the value 2?

A Step 5

B Step 2

C Step 4

D Step 6

💡 Hint

Look at the 'Dequeued Value' row in variable_tracker and the 'Operation' column in execution_table.

If we enqueue 3 after step 5, what will be the top of stack1?

A empty

B 2

C 3

D 1

💡 Hint

Enqueue pushes onto stack1; see steps 1 and 2 for how stack1 changes.

Concept Snapshot

Queue Using Two Stacks:
- Enqueue: push element onto stack1
- Dequeue: if stack2 empty, move all from stack1 to stack2
- Pop from stack2 to dequeue
- stack2 reverses order to maintain FIFO
- Efficient amortized operations

Full Transcript

This visualization shows how a queue can be implemented using two stacks. Enqueue operations push elements onto the first stack. Dequeue operations pop elements from the second stack. If the second stack is empty during dequeue, all elements from the first stack are moved to the second stack, reversing their order to maintain the queue's FIFO behavior. The execution table traces each step, showing stack states and pointer changes. Key moments clarify why transfer happens only when needed and how the order is preserved. The visual quiz tests understanding of stack states and dequeue results. The concept snapshot summarizes the method in simple steps.

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