Queue Using Two Stacks in DSA Go - 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 adds elements to Stack1. Dequeue removes from Stack2. If Stack2 is empty, elements from Stack1 are moved to Stack2 to reverse order.

Execution Sample

DSA Go

enqueue(1)
enqueue(2)
dequeue()
enqueue(3)
dequeue()
dequeue()

This code adds 1 and 2 to the queue, removes one element, adds 3, then removes two elements.

Execution Table

Step	Operation	Stack1 State	Stack2 State	Action Taken	Queue Visual State
1	enqueue(1)	1	empty	Push 1 to Stack1	1 -> null
2	enqueue(2)	1, 2	empty	Push 2 to Stack1	1 -> 2 -> null
3	dequeue()	empty	2, 1	Stack2 empty, transfer Stack1 to Stack2, pop from Stack2	2 -> 1 -> null after transfer, dequeue 1
4	enqueue(3)	3	2	Push 3 to Stack1	2 -> 3 -> null
5	dequeue()	3	empty	Pop from Stack2 (2)	3 -> null
6	dequeue()	empty	3	Stack2 empty, transfer Stack1 to Stack2, pop from Stack2	3 -> null after transfer, dequeue 3
7	dequeue()	empty	empty	Both stacks empty, queue empty	null

💡 Execution stops after all operations are done; queue is empty at last step.

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
Stack1	empty	[1]	[1,2]	empty	[3]	[3]	empty	empty
Stack2	empty	empty	empty	[2,1]	[2]	empty	[3]	empty
Queue Size	0	1	2	1	2	1	0	0

Key Moments - 3 Insights

Why do we transfer all elements from Stack1 to Stack2 during dequeue when Stack2 is empty?

Because Stack1 stores elements in enqueue order (newest on top), transferring to Stack2 reverses order so oldest element is on top for dequeue. See Step 3 in execution_table where transfer happens before popping.

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

The queue is empty, so no element can be dequeued. Step 7 in execution_table shows both stacks empty and queue visual state as null.

Why do we push new elements only to Stack1 and never directly to Stack2?

Stack1 is used to collect new elements in enqueue order. Stack2 is only used for dequeue to maintain correct order. Pushing to Stack2 directly would break the queue order. See Steps 1, 2, and 4 where enqueue pushes to Stack1.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the state of Stack2 after transferring elements from Stack1?

A [2, 1]

B [1, 2]

C empty

D [3]

💡 Hint

Check the 'Stack2 State' column at Step 3 in execution_table.

At which step does the queue become empty according to the variable_tracker?

A After Step 5

B After Step 6

C After Step 7

D After Step 4

💡 Hint

Look at 'Queue Size' row in variable_tracker to find when it reaches 0.

If we enqueue(4) after Step 7, what will be the state of Stack1?

A empty

B [4]

C [3,4]

D [2,4]

💡 Hint

New enqueues always push to Stack1 as shown in Steps 1, 2, and 4.

Concept Snapshot

Queue Using Two Stacks:
- Enqueue: push element onto Stack1
- Dequeue: if Stack2 empty, transfer all from Stack1 to Stack2, then pop Stack2
- Stack2 holds elements in dequeue order
- Efficient amortized queue using two stacks
- Maintains FIFO order using LIFO stacks

Full Transcript

This concept shows how to build a queue 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 to reverse their order, ensuring the oldest element is dequeued first. The execution table traces each operation step-by-step, showing the states of both stacks and the resulting queue order. The variable tracker monitors the stacks and queue size after each step. Key moments clarify why transferring elements is necessary, what happens when the queue is empty, and why new elements only go to the first stack. Visual quizzes test understanding of stack states and queue emptiness. The snapshot summarizes the method for quick reference.

Practice

1. What is the main idea behind implementing a Queue Using Two Stacks?

easy

A. Use two stacks to store elements in sorted order

B. Use one stack for enqueue and another for dequeue to reverse order

C. Use two stacks to store elements in a tree structure

D. Use one stack to store even elements and another for odd elements

Solution

1. Step 1: Understand queue and stack behavior

   A queue follows FIFO (first in, first out), while a stack follows LIFO (last in, first out).

2. Step 2: Use two stacks to reverse order

   By pushing elements into one stack and popping them into another, the order reverses, simulating queue behavior.

3. Final Answer:

   Use one stack for enqueue and another for dequeue to reverse order -> Option B

4. Quick Check:

   Two stacks reverse order to mimic queue = B [OK]

Hint: Remember: two stacks reverse order to simulate queue [OK]

Common Mistakes:

• Thinking both stacks store elements in sorted order
• Confusing stack behavior with queue behavior
• Using stacks to separate even and odd elements

2. Which of the following is the correct syntax to push an element x into a stack named stack1 in Go?

easy

A. stack1 = append(stack1, x)

B. stack1.Push(x)

C. stack1.add(x)

D. stack1.insert(x)

Solution

1. Step 1: Understand Go slice push operation

   In Go, stacks are often implemented using slices, and pushing means appending an element.

2. Step 2: Use append to add element

   The correct way to push is using stack1 = append(stack1, x) to add x at the end.

3. Final Answer:

   stack1 = append(stack1, x) -> Option A

4. Quick Check:

   Go slice push uses append = A [OK]

Hint: Use append(slice, x) to push in Go stack [OK]

Common Mistakes:

• Using non-existent Push() method on slice
• Using add() or insert() which are not Go slice methods
• Trying to push without reassigning slice

3. Given the following Go code implementing a queue using two stacks, what will be printed?

type Queue struct {
  stack1 []int
  stack2 []int
}

func (q *Queue) Enqueue(x int) {
  q.stack1 = append(q.stack1, x)
}

func (q *Queue) Dequeue() int {
  if len(q.stack2) == 0 {
    for len(q.stack1) > 0 {
      n := len(q.stack1) - 1
      q.stack2 = append(q.stack2, q.stack1[n])
      q.stack1 = q.stack1[:n]
    }
  }
  n := len(q.stack2) - 1
  val := q.stack2[n]
  q.stack2 = q.stack2[:n]
  return val
}

func main() {
  q := Queue{}
  q.Enqueue(10)
  q.Enqueue(20)
  q.Enqueue(30)
  fmt.Println(q.Dequeue())
  fmt.Println(q.Dequeue())
  q.Enqueue(40)
  fmt.Println(q.Dequeue())
  fmt.Println(q.Dequeue())
}

medium

A. 20
10
30
40

B. 30
20
10
40

C. 10
20
40
30

D. 10
20
30
40

Solution

1. Step 1: Trace enqueue operations

   Enqueue 10, 20, 30 adds to stack1: [10, 20, 30]

2. Step 2: Dequeue operations transfer stack1 to stack2 and pop

   First dequeue moves all from stack1 to stack2 reversing order: stack2 = [30, 20, 10]. Pop from stack2 returns 10, then 20. Enqueue 40 adds to stack1: [40]. Next dequeue pops 30 from stack2. Last dequeue pops 40 from stack1 after transfer.

3. Final Answer:

   10 20 30 40 -> Option D

4. Quick Check:

   Queue order preserved by two stacks = A [OK]

Hint: Remember stack2 reverses stack1 to dequeue in FIFO order [OK]

Common Mistakes:

• Assuming stack1 pops directly for dequeue
• Not transferring all elements from stack1 to stack2
• Mixing order of elements after transfer

4. Identify the bug in this Go code snippet for dequeue operation in a queue using two stacks:

func (q *Queue) Dequeue() int {
  if len(q.stack2) == 0 {
    for len(q.stack1) > 0 {
      n := len(q.stack1) - 1
      q.stack2 = append(q.stack2, q.stack1[n])
      q.stack1 = q.stack1[:n]
    }
  }
  val := q.stack2[0]
  q.stack2 = q.stack2[1:]
  return val
}

medium

A. Appending elements to stack2 instead of pushing

B. Not checking if both stacks are empty before dequeue

C. Accessing q.stack2[0] instead of last element causes wrong dequeue order

D. Using len(q.stack1) - 1 incorrectly in loop

Solution

1. Step 1: Understand stack2 usage in dequeue

   stack2 stores elements in reversed order; popping should remove last element (end of slice).

2. Step 2: Identify incorrect element access

   Accessing q.stack2[0] removes first element, breaking LIFO order of stack2 and queue FIFO behavior.

3. Final Answer:

   Accessing q.stack2[0] instead of last element causes wrong dequeue order -> Option C

4. Quick Check:

   Dequeue must pop last stack2 element = C [OK]

Hint: Pop from end of stack slice, not from start [OK]

Common Mistakes:

• Removing first element of stack2 instead of last
• Not checking empty stacks before dequeue
• Misusing slice indices in loop

5. You want to implement a Peek() function for the queue using two stacks in Go that returns the front element without removing it. Which approach correctly returns the front element?

hard

A. If stack2 is empty, transfer all elements from stack1 to stack2, then return last element of stack2

B. Return first element of stack1 if not empty, else last element of stack2

C. Return last element of stack1 always

D. Transfer elements from stack2 to stack1 and return first element of stack1

Solution

1. Step 1: Understand peek logic in two-stack queue

   Peek must return the front element, which is at the top of stack2 if not empty.

2. Step 2: Transfer elements if stack2 empty and return last element

   If stack2 is empty, transfer all from stack1 to stack2 to reverse order, then peek last element of stack2 without removing.

3. Final Answer:

   If stack2 is empty, transfer all elements from stack1 to stack2, then return last element of stack2 -> Option A

4. Quick Check:

   Peek front = top of stack2 after transfer = D [OK]

Hint: Peek top of stack2 after transfer if empty [OK]

Common Mistakes:

• Peeking first element of stack1 which is wrong order
• Always returning last element of stack1 ignoring stack2
• Transferring elements in wrong direction