Queue Concept and FIFO Principle in DSA Go

Mental Model

A queue is a line where the first person to get in is the first to get out. It works like waiting in line for a bus.

Analogy: Imagine a line at a coffee shop. The first person to join the line is the first to get served and leave. New people join at the end of the line.

front -> [1] -> [2] -> [3] -> rear
null ← null ← null ← null

Dry Run Walkthrough

Input: Start with an empty queue, enqueue 1, enqueue 2, enqueue 3, then dequeue once

Goal: Show how elements enter at the rear and leave from the front following FIFO

Step 1: enqueue 1 into empty queue

front -> [1] -> rear

Why: First element becomes both front and rear

Step 2: enqueue 2 at rear

front -> [1] -> [2] -> rear

Why: New element added at the end of the queue

Step 3: enqueue 3 at rear

front -> [1] -> [2] -> [3] -> rear

Why: Keep adding elements at the rear

Step 4: dequeue from front

front -> [2] -> [3] -> rear

Why: Remove the first element that entered (1) following FIFO

Result:

front -> [2] -> [3] -> rear

Annotated Code

DSA Go

package main

import "fmt"

type Queue struct {
	items []int
}

func (q *Queue) Enqueue(val int) {
	q.items = append(q.items, val) // add at rear
}

func (q *Queue) Dequeue() (int, bool) {
	if len(q.items) == 0 {
		return 0, false // empty queue
	}
	val := q.items[0]           // front element
	q.items = q.items[1:]       // remove front
	return val, true
}

func (q *Queue) String() string {
	if len(q.items) == 0 {
		return "empty queue"
	}
	res := "front -> "
	for i, v := range q.items {
		res += fmt.Sprintf("[%d]", v)
		if i != len(q.items)-1 {
			res += " -> "
		}
	}
	res += " -> rear"
	return res
}

func main() {
	q := &Queue{}
	q.Enqueue(1)
	q.Enqueue(2)
	q.Enqueue(3)
	fmt.Println(q.String())
	q.Dequeue()
	fmt.Println(q.String())
}

q.items = append(q.items, val) // add at rear

add new element at the end of the queue

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

check if queue is empty before dequeue

val := q.items[0] // front element

store front element to return

q.items = q.items[1:] // remove front

remove front element to simulate dequeue

Output

front -> [1] -> [2] -> [3] -> rear

front -> [2] -> [3] -> rear

Complexity Analysis

Time: O(1) for enqueue and dequeue because append and slicing front are constant time in Go slices for this use case

Space: O(n) because queue stores n elements in a slice

vs Alternative: Compared to linked list queue, slice-based queue is simpler but slicing front can cause copying in some languages; linked list avoids copying but uses more memory

Edge Cases

dequeue from empty queue

returns false and zero value without error

DSA Go

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

enqueue into empty queue

queue correctly sets first element as front and rear

DSA Go

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

When to Use This Pattern

When you see a problem requiring processing items in the order they arrive, use a queue with FIFO principle to maintain correct order.

Common Mistakes

Mistake: Removing elements from the rear instead of the front
Fix: Always remove elements from the front to maintain FIFO order

Mistake: Adding elements at the front instead of the rear
Fix: Always add new elements at the rear to keep the order

Summary

A queue stores items so the first added is the first removed (FIFO).

Use a queue when order of processing must follow arrival order.

The key is adding at the rear and removing from the front to keep order.

Practice

1. What does the FIFO principle mean in the context of a queue?

easy

A. First In, First Out - the last element added is the first removed

B. First In, First Out - the first element added is the first removed

C. Last In, First Out - the first element added is the last removed

D. Last In, First Out - the last element added is the last removed

Solution

1. Step 1: Understand FIFO meaning

   FIFO means the first element that enters the queue is the first to leave.

2. Step 2: Match FIFO to queue behavior

   Queues follow FIFO, so the first added element is removed first.

3. Final Answer:

   First In, First Out - the first element added is the first removed -> Option B

4. Quick Check:

   FIFO = First In, First Out [OK]

Hint: Remember queue = line; first come, first served [OK]

Common Mistakes:

• Confusing FIFO with LIFO
• Thinking last added is removed first
• Mixing stack behavior with queue

2. Which of the following is the correct way to declare a queue using a slice in Go?

easy

A. queue := []int{}

B. var queue []int

C. queue := make(map[int]int)

D. var queue int

Solution

1. Step 1: Identify slice declaration for queue

   In Go, a queue can be represented as a slice, initialized as empty with []int{}.

2. Step 2: Check options for correct slice syntax

   queue := []int{} uses slice literal syntax to create an empty int slice, suitable for queue.

3. Final Answer:

   queue := []int{} -> Option A

4. Quick Check:

   Slice queue declaration = queue := []int{} [OK]

Hint: Use slice literal []int{} for empty queue [OK]

Common Mistakes:

• Using map instead of slice
• Declaring queue as single int variable
• Using var without initialization for slice

3. What will be the output of the following Go code snippet?

package main
import "fmt"
func main() {
  queue := []int{10, 20, 30}
  // Dequeue operation
  first := queue[0]
  queue = queue[1:]
  fmt.Println(first)
  fmt.Println(queue)
}

medium

A. 10
[10 20 30]

B. 20
[10 30]

C. 10
[20 30]

D. 30
[10 20]

Solution

1. Step 1: Identify dequeue operation

   The first element 10 is stored in 'first', then queue is sliced from index 1 onward.

2. Step 2: Determine output values

   Printing 'first' outputs 10; printing 'queue' outputs remaining slice [20 30].

3. Final Answer:

   10 [20 30] -> Option C

4. Quick Check:

   Dequeue removes first element = 10, queue left = [20 30] [OK]

Hint: Dequeue removes first element, slice queue from index 1 [OK]

Common Mistakes:

• Printing old queue without slicing
• Confusing index positions
• Assuming queue unchanged after dequeue

4. Identify the error in the following Go code that tries to enqueue an element to a queue represented by a slice:

package main
func main() {
  queue := []int{1, 2, 3}
  queue[3] = 4
}

medium

A. Compile error because queue is not declared

B. Syntax error due to missing import statement

C. No error; element 4 is added correctly

D. Index out of range error because slice index 3 does not exist

Solution

1. Step 1: Analyze slice indexing

   Slice 'queue' has length 3 with indices 0,1,2; index 3 is out of range.

2. Step 2: Understand how to add elements

   To add elements, use append(queue, 4) instead of direct index assignment.

3. Final Answer:

   Index out of range error because slice index 3 does not exist -> Option D

4. Quick Check:

   Accessing queue[3] invalid for length 3 slice [OK]

Hint: Use append to add elements, not direct index assignment [OK]

Common Mistakes:

• Trying to assign beyond slice length
• Forgetting to use append for enqueue
• Assuming slice auto-expands on index assignment

5. Given a queue implemented as a slice in Go, how would you write a function to enqueue multiple elements at once while preserving FIFO order? Choose the correct code snippet.

func enqueueMultiple(queue []int, elements []int) []int {
  // Fill in
}

hard

A. return append(queue, elements...)

B. return append(elements, queue...)

C. for _, e := range elements { queue = append([]int{e}, queue...) } return queue

D. queue = elements; return queue

Solution

1. Step 1: Understand enqueue multiple elements

   To add multiple elements preserving order, append all new elements at the end of queue.

2. Step 2: Check code options for correct append usage

   return append(queue, elements...) uses append(queue, elements...) which adds all elements at the end in order.

3. Final Answer:

   return append(queue, elements...) -> Option A

4. Quick Check:

   Appending elements at end preserves FIFO enqueue order [OK]

Hint: Use append(queue, elements...) to add multiple items [OK]

Common Mistakes:

• Appending new elements before queue (wrong order)
• Replacing queue instead of appending
• Appending elements one by one at front