Queue Using Two Stacks in DSA Go

Mental Model

Use two stacks to make a queue by reversing order twice so the first inserted item comes out first.

Analogy: Imagine two trays where you stack plates. You put plates on the first tray, then flip them onto the second tray to get them in the right order to serve.

stack1: top -> [5, 4, 3, 2, 1] bottom
stack2: empty
queue front is top of stack2 if not empty, else bottom of stack1

Dry Run Walkthrough

Input: enqueue 1, enqueue 2, enqueue 3, dequeue, enqueue 4, dequeue, 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: [1]
stack2: []

Why: New items go to stack1 to keep insertion order

Step 2: enqueue 2: push 2 onto stack1

stack1: [1, 2]
stack2: []

Why: Keep adding new items on top of stack1

Step 3: enqueue 3: push 3 onto stack1

stack1: [1, 2, 3]
stack2: []

Why: Stack1 holds all new items in order

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

stack1: []
stack2: [3, 2, 1]

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

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

stack1: []
stack2: [3, 2]

Why: Remove oldest item from queue

Step 6: enqueue 4: push 4 onto stack1

stack1: [4]
stack2: [3, 2]

Why: New items always go to stack1

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

stack1: [4]
stack2: [3]

Why: Continue dequeue from stack2 while not empty

Step 8: dequeue: pop top of stack2 (3)

stack1: [4]
stack2: []

Why: Dequeue last item from stack2

Result:

stack1: [4]
stack2: []
Queue front is 4
Dequeued items in order: 1, 2, 3

Annotated Code

DSA Go

package main

import (
	"fmt"
)

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

func (q *Queue) Enqueue(val int) {
	q.stack1 = append(q.stack1, val) // push val to stack1
}

func (q *Queue) Dequeue() (int, bool) {
	if len(q.stack2) == 0 {
		// move all from stack1 to stack2 to reverse order
		for len(q.stack1) > 0 {
			val := q.stack1[len(q.stack1)-1]
			q.stack1 = q.stack1[:len(q.stack1)-1]
			q.stack2 = append(q.stack2, val)
		}
	}
	if len(q.stack2) == 0 {
		return 0, false // queue empty
	}
	val := q.stack2[len(q.stack2)-1]
	q.stack2 = q.stack2[:len(q.stack2)-1]
	return val, true
}

func main() {
	q := Queue{}
	q.Enqueue(1)
	q.Enqueue(2)
	q.Enqueue(3)

	val, ok := q.Dequeue()
	if ok {
		fmt.Println(val)
	}

	q.Enqueue(4)

	val, ok = q.Dequeue()
	if ok {
		fmt.Println(val)
	}

	val, ok = q.Dequeue()
	if ok {
		fmt.Println(val)
	}
}

q.stack1 = append(q.stack1, val) // push val to stack1

push new item to stack1 to keep insertion order

if len(q.stack2) == 0 {

check if stack2 is empty before moving items

for len(q.stack1) > 0 {

move all items from stack1 to stack2 to reverse order

val := q.stack1[len(q.stack1)-1]

pop top item from stack1

q.stack1 = q.stack1[:len(q.stack1)-1]

remove popped item from stack1

q.stack2 = append(q.stack2, val)

push popped item to stack2

val := q.stack2[len(q.stack2)-1]

pop top item from stack2 for dequeue

q.stack2 = q.stack2[:len(q.stack2)-1]

remove popped item from stack2

Output

1

2

3

Complexity Analysis

Time: O(1) amortized per operation because each element moves between stacks at most once

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

vs Alternative: Compared to a linked list queue 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

returns false indicating queue is empty without error

DSA Go

if len(q.stack2) == 0 { return 0, false }

enqueue then dequeue single element

correctly returns the single element

DSA Go

q.stack1 = append(q.stack1, val)

multiple enqueues before any dequeue

all elements stored in stack1 until first dequeue triggers transfer

DSA Go

for len(q.stack1) > 0 { ... }

When to Use This Pattern

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

Common Mistakes

Mistake: Not transferring all elements from stack1 to stack2 before dequeue when stack2 is empty
Fix: Add a loop to move all items from stack1 to stack2 before popping from stack2

Mistake: Popping from stack1 directly on dequeue instead of stack2
Fix: Always pop from stack2 if not empty; only transfer from stack1 when stack2 is empty

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 is transferring all elements from one stack to another to reverse order and get FIFO.

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