Queue Implementation Using Linked List in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Enqueue and Dequeue Operations

What is the printed state of the queue after the following operations in a linked list queue implementation?

Operations:
Enqueue(10), Enqueue(20), Dequeue(), Enqueue(30), Dequeue()

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type Queue struct {
    front *Node
    rear  *Node
}

func (q *Queue) Enqueue(val int) {
    newNode := &Node{value: val}
    if q.rear == nil {
        q.front = newNode
        q.rear = newNode
        return
    }
    q.rear.next = newNode
    q.rear = newNode
}

func (q *Queue) Dequeue() (int, bool) {
    if q.front == nil {
        return 0, false
    }
    val := q.front.value
    q.front = q.front.next
    if q.front == nil {
        q.rear = nil
    }
    return val, true
}

func (q *Queue) Print() {
    current := q.front
    for current != nil {
        fmt.Print(current.value)
        if current.next != nil {
            fmt.Print(" -> ")
        }
        current = current.next
    }
    fmt.Println(" -> null")
}

func main() {
    q := &Queue{}
    q.Enqueue(10)
    q.Enqueue(20)
    q.Dequeue()
    q.Enqueue(30)
    q.Dequeue()
    q.Print()
}

A 30 -> null

B 20 -> 30 -> null

C 10 -> 30 -> null

D null

💡 Hint

Trace each operation step-by-step and update the queue state.

Initially, enqueue 10 and 20: queue is 10 -> 20 -> null. Dequeue removes 10: queue is 20 -> null. Enqueue 30: queue is 20 -> 30 -> null. Dequeue removes 20: queue is 30 -> null. The final print shows 30 -> null.

🧠 Conceptual

intermediate

Understanding Queue Front and Rear Pointers

In a linked list implementation of a queue, which statement about the front and rear pointers is true after multiple enqueue and dequeue operations?

A The front pointer always points to the last inserted node.

B The front pointer points to the node to be dequeued next, and the rear pointer points to the last inserted node.

C Both front and rear pointers always point to the same node.

D The rear pointer always points to the first inserted node.

💡 Hint

Think about which end of the queue removes elements and which end adds elements.

In a queue, elements are removed from the front and added at the rear. So, the front pointer points to the node to be dequeued next, and the rear pointer points to the last inserted node.

🔧 Debug

advanced

Identify the Error in Dequeue Method

What error will occur when running the following Dequeue method in a linked list queue implementation if the queue is empty?

DSA Go

func (q *Queue) Dequeue() int {
    val := q.front.value
    q.front = q.front.next
    if q.front == nil {
        q.rear = nil
    }
    return val
}

A Runtime panic: nil pointer dereference

B Compilation error: missing return statement

C No error, returns zero value

D Runtime panic: index out of range

💡 Hint

Consider what happens if q.front is nil before accessing q.front.value.

If the queue is empty, q.front is nil. Accessing q.front.value causes a runtime panic due to nil pointer dereference.

❓ Predict Output

advanced

Output After Multiple Enqueue and Dequeue

What is the printed state of the queue after these operations?

Enqueue(5), Enqueue(15), Enqueue(25), Dequeue(), Dequeue(), Enqueue(35), Enqueue(45), Dequeue()

DSA Go

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

type Queue struct {
    front *Node
    rear  *Node
}

func (q *Queue) Enqueue(val int) {
    newNode := &Node{value: val}
    if q.rear == nil {
        q.front = newNode
        q.rear = newNode
        return
    }
    q.rear.next = newNode
    q.rear = newNode
}

func (q *Queue) Dequeue() (int, bool) {
    if q.front == nil {
        return 0, false
    }
    val := q.front.value
    q.front = q.front.next
    if q.front == nil {
        q.rear = nil
    }
    return val, true
}

func (q *Queue) Print() {
    current := q.front
    for current != nil {
        fmt.Print(current.value)
        if current.next != nil {
            fmt.Print(" -> ")
        }
        current = current.next
    }
    fmt.Println(" -> null")
}

func main() {
    q := &Queue{}
    q.Enqueue(5)
    q.Enqueue(15)
    q.Enqueue(25)
    q.Dequeue()
    q.Dequeue()
    q.Enqueue(35)
    q.Enqueue(45)
    q.Dequeue()
    q.Print()
}

A 25 -> 35 -> 45 -> null

B 45 -> null

C 15 -> 25 -> 35 -> 45 -> null

D 35 -> 45 -> null

💡 Hint

Track the queue after each operation carefully.

Start: enqueue 5,15,25 → 5->15->25->null. Dequeue removes 5 → 15->25->null. Dequeue removes 15 → 25->null. Enqueue 35,45 → 25->35->45->null. Dequeue removes 25 → 35->45->null. Final print is 35 -> 45 -> null.

🚀 Application

expert

Calculate Queue Size After Operations

Given a linked list queue with these operations:

Enqueue(1), Enqueue(2), Enqueue(3), Dequeue(), Enqueue(4), Dequeue(), Dequeue(), Enqueue(5)

What is the number of elements in the queue after these operations?

DSA Go

package main

type Node struct {
    value int
    next  *Node
}

type Queue struct {
    front *Node
    rear  *Node
}

func (q *Queue) Enqueue(val int) {
    newNode := &Node{value: val}
    if q.rear == nil {
        q.front = newNode
        q.rear = newNode
        return
    }
    q.rear.next = newNode
    q.rear = newNode
}

func (q *Queue) Dequeue() (int, bool) {
    if q.front == nil {
        return 0, false
    }
    val := q.front.value
    q.front = q.front.next
    if q.front == nil {
        q.rear = nil
    }
    return val, true
}

func (q *Queue) Size() int {
    count := 0
    current := q.front
    for current != nil {
        count++
        current = current.next
    }
    return count
}

func main() {
    q := &Queue{}
    q.Enqueue(1)
    q.Enqueue(2)
    q.Enqueue(3)
    q.Dequeue()
    q.Enqueue(4)
    q.Dequeue()
    q.Dequeue()
    q.Enqueue(5)
    size := q.Size()
    println(size)
}

A 4

B 3

C 2

D 1

💡 Hint

Count elements after each operation carefully.

Operations stepwise: Enqueue 1,2,3 → size 3. Dequeue removes 1 → size 2. Enqueue 4 → size 3. Dequeue removes 2 → size 2. Dequeue removes 3 → size 1. Enqueue 5 → size 2. Final size is 2.

Practice

1. What is the main advantage of implementing a queue using a linked list instead of an array?

easy

A. Uses less memory for small queues

B. Dynamic size allows unlimited enqueue without resizing

C. Faster access to middle elements

D. Simpler to implement than arrays

Solution

1. Step 1: Understand queue size limitations in arrays

   Arrays have fixed size, so queues implemented with arrays need resizing or have limited capacity.

2. Step 2: Linked list dynamic size advantage

   Linked lists grow dynamically by adding nodes, so queues can grow without size limits.

3. Final Answer:

   Dynamic size allows unlimited enqueue without resizing -> Option B

4. Quick Check:

   Linked list queues grow dynamically [OK]

Hint: Linked list queues grow dynamically, arrays don't [OK]

Common Mistakes:

• Thinking linked list queues have faster random access
• Assuming linked lists use less memory always
• Confusing simplicity of implementation

2. Which of the following is the correct way to declare a node struct for a linked list queue in Go?

easy

A. type Node struct { data int; next *Node }

B. type Node struct { data int; next Node }

C. type Node struct { data *int; next *Node }

D. type Node struct { data int; next interface{} }

Solution

1. Step 1: Understand pointer usage in linked list nodes

   Each node's next field must be a pointer to another node to link nodes dynamically.

2. Step 2: Check each option's next field type

   type Node struct { data int; next *Node } uses *Node pointer correctly; B uses Node (value) causing infinite size; C uses *int for data unnecessarily; D uses interface{} which is not type-safe.

3. Final Answer:

   type Node struct { data int; next *Node } -> Option A

4. Quick Check:

   Node next must be *Node pointer [OK]

Hint: Node next must be pointer to Node type [OK]

Common Mistakes:

• Using value type instead of pointer for next
• Using interface{} instead of *Node
• Making data a pointer unnecessarily

3. What will be the output after executing the following Go code that enqueues 10, 20, then dequeues one element from a linked list queue?

package main
import "fmt"

type Node struct {
  data int
  next *Node
}

type Queue struct {
  front *Node
  rear  *Node
}

func (q *Queue) Enqueue(val int) {
  newNode := &Node{data: val}
  if q.rear == nil {
    q.front = newNode
    q.rear = newNode
  } else {
    q.rear.next = newNode
    q.rear = newNode
  }
}

func (q *Queue) Dequeue() int {
  if q.front == nil {
    return -1
  }
  val := q.front.data
  q.front = q.front.next
  if q.front == nil {
    q.rear = nil
  }
  return val
}

func main() {
  q := &Queue{}
  q.Enqueue(10)
  q.Enqueue(20)
  fmt.Println(q.Dequeue())
  fmt.Println(q.front.data)
}

medium

A. 10
20

B. 20
10

C. 10
10

D. 20
20

Solution

1. Step 1: Trace enqueue operations

   Enqueue 10: front and rear point to node with 10. Enqueue 20: rear.next points to node with 20, rear updated to 20.

2. Step 2: Trace dequeue and print operations

   Dequeue removes front node (10), returns 10. Now front points to node with 20. Printing q.front.data prints 20.

3. Final Answer:

   10 20 -> Option A

4. Quick Check:

   Dequeue returns 10, front data is 20 [OK]

Hint: Dequeue returns front, front moves to next [OK]

Common Mistakes:

• Confusing front and rear after dequeue
• Printing dequeued value twice
• Assuming rear changes on dequeue

4. Identify the bug in this Dequeue method of a linked list queue in Go:

func (q *Queue) Dequeue() int {
  if q.front == nil {
    return -1
  }
  val := q.front.data
  q.front = q.front.next
  return val
}

medium

A. Does not check if queue is empty before dequeue

B. Returns wrong value from front node

C. Does not update rear when queue becomes empty

D. Incorrectly assigns front to rear

Solution

1. Step 1: Analyze queue empty condition after dequeue

   If after removing front node, front becomes nil, rear must also be set to nil to avoid dangling pointer.

2. Step 2: Check code for rear update

   Code does not update rear when front is nil, causing rear to point to old node incorrectly.

3. Final Answer:

   Does not update rear when queue becomes empty -> Option C

4. Quick Check:

   Rear must be nil if front is nil after dequeue [OK]

Hint: Set rear to nil when front becomes nil [OK]

Common Mistakes:

• Forgetting to update rear on empty queue
• Returning wrong value from front
• Not checking for empty queue before dequeue

5. You want to implement a function to print all elements of a linked list queue from front to rear. Which approach is correct in Go?

func (q *Queue) PrintQueue() {
  current := q.front
  for current != nil {
    fmt.Print(current.data, " -> ")
    current = current.next
  }
  fmt.Println("null")
}

What will be the output after enqueueing 5, 15, 25 and calling PrintQueue()?

medium

A. 25 -> 15 -> 5 -> null

B. 5 -> 15 -> null

C. null

D. 5 -> 15 -> 25 -> null

Solution

1. Step 1: Understand enqueue order in linked list queue

   Enqueue adds nodes at rear, so order is 5 (front), then 15, then 25 (rear).

2. Step 2: Trace PrintQueue traversal

   PrintQueue starts at front and prints each node's data until nil, so prints 5 -> 15 -> 25 -> null.

3. Final Answer:

   5 -> 15 -> 25 -> null -> Option D

4. Quick Check:

   Print from front to rear = 5 -> 15 -> 25 -> null [OK]

Hint: Traverse from front to rear printing data [OK]

Common Mistakes:

• Printing in reverse order
• Stopping before last node
• Not printing null at end