Queue Implementation Using Array in DSA Go

Mental Model

A queue is like a line where the first person in is the first person out. We use an array to hold the items and keep track of where the front and back of the line are.

Analogy: Imagine a line at a ticket counter. People join at the end and leave from the front. The array is the floor with spots, and two markers show where the line starts and ends.

front -> [ ] [ ] [ ] [ ] [ ] ← rear
indexes  0   1   2   3   4

Dry Run Walkthrough

Input: Start with empty queue of size 5, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements enter at rear and leave from front using array indexes

Step 1: enqueue 10 at rear index 0

front=0, rear=0, array=[10, _, _, _, _]

Why: Add first element at start of array

Step 2: enqueue 20 at rear index 1

front=0, rear=1, array=[10, 20, _, _, _]

Why: Add next element at next free spot

Step 3: dequeue element at front index 0

front=1, rear=1, array=[10, 20, _, _, _]

Why: Remove element from front by moving front pointer forward

Step 4: enqueue 30 at rear index 2

front=1, rear=2, array=[10, 20, 30, _, _]

Why: Add new element at next rear position

Result:

front=1, rear=2, array=[10, 20, 30, _, _] with queue elements 20 -> 30 -> null

Annotated Code

DSA Go

package main

import (
	"errors"
	"fmt"
)

type Queue struct {
	items []int
	front int
	rear  int
	size  int
	count int
}

func NewQueue(size int) *Queue {
	return &Queue{
		items: make([]int, size),
		front: 0,
		rear:  -1,
		size:  size,
		count: 0,
	}
}

func (q *Queue) Enqueue(val int) error {
	if q.count == q.size {
		return errors.New("Queue is full")
	}
	q.rear = (q.rear + 1) % q.size // move rear forward circularly
	q.items[q.rear] = val         // place new val at rear
	q.count++                    // increase count
	return nil
}

func (q *Queue) Dequeue() (int, error) {
	if q.count == 0 {
		return 0, errors.New("Queue is empty")
	}
	val := q.items[q.front]       // get front value
	q.front = (q.front + 1) % q.size // move front forward circularly
	q.count--                    // decrease count
	return val, nil
}

func (q *Queue) String() string {
	if q.count == 0 {
		return "empty queue"
	}
	result := ""
	for i := 0; i < q.count; i++ {
		index := (q.front + i) % q.size
		result += fmt.Sprintf("%d", q.items[index])
		if i != q.count-1 {
			result += " -> "
		}
	}
	result += " -> null"
	return result
}

func main() {
	q := NewQueue(5)
	_ = q.Enqueue(10) // enqueue 10
	_ = q.Enqueue(20) // enqueue 20
	val, _ := q.Dequeue() // dequeue front
	_ = q.Enqueue(30) // enqueue 30
	fmt.Println(q.String())
	fmt.Println("Dequeued value:", val)
}

q.rear = (q.rear + 1) % q.size // move rear forward circularly

advance rear pointer to next position, wrap around if needed

q.items[q.rear] = val // place new val at rear

insert new element at rear index

q.count++ // increase count

track number of elements in queue

val := q.items[q.front] // get front value

retrieve element at front for dequeue

q.front = (q.front + 1) % q.size // move front forward circularly

advance front pointer to next position, wrap around if needed

q.count-- // decrease count

reduce element count after dequeue

Output

20 -> 30 -> null

Dequeued value: 10

Complexity Analysis

Time: O(1) because enqueue and dequeue only move pointers and assign values once

Space: O(n) because the array holds n elements where n is the queue size

vs Alternative: Compared to linked list queue, array queue uses fixed space but simpler pointer math; linked list uses dynamic space but more memory per node

Edge Cases

enqueue when queue is full

returns error "Queue is full" and does not add element

DSA Go

if q.count == q.size {
	return errors.New("Queue is full")
}

dequeue when queue is empty

returns error "Queue is empty" and no element is removed

DSA Go

if q.count == 0 {
	return 0, errors.New("Queue is empty")
}

enqueue and dequeue wrap around array end

front and rear pointers wrap to start using modulo to reuse array space

DSA Go

q.rear = (q.rear + 1) % q.size
q.front = (q.front + 1) % q.size

When to Use This Pattern

When you see a problem needing first-in-first-out order with fixed size, reach for queue using array with front and rear pointers to manage positions efficiently.

Common Mistakes

Mistake: Not wrapping front or rear pointers when they reach array end causing index out of range
Fix: Use modulo operation to wrap pointers: (pointer + 1) % size

Mistake: Confusing when queue is full vs empty by only checking front and rear equality
Fix: Track count of elements to distinguish full and empty states

Summary

Implements a queue using a fixed-size array with front and rear pointers.

Use when you need a simple, fast queue with known maximum size.

The key is moving front and rear pointers circularly to reuse array space.

Practice

1. What is the main characteristic of a queue implemented using an array?

easy

A. It allows random access to elements

B. It follows Last-In-First-Out (LIFO) order

C. It follows First-In-First-Out (FIFO) order

D. It stores elements in sorted order

Solution

1. Step 1: Understand queue behavior

   A queue adds elements at the rear and removes from the front, so the first element added is the first removed.

2. Step 2: Match behavior with options

   This behavior is called First-In-First-Out (FIFO), which matches It follows First-In-First-Out (FIFO) order.

3. Final Answer:

   It follows First-In-First-Out (FIFO) order -> Option C

4. Quick Check:

   Queue = FIFO [OK]

Hint: Queue means first in, first out order [OK]

Common Mistakes:

• Confusing queue with stack (LIFO)
• Thinking queue allows random access
• Assuming queue sorts elements automatically

2. Which of the following is the correct way to declare a fixed-size queue array of size 5 in Go?

easy

A. var queue [5]int

B. queue := []int{5}

C. queue := [5]int

D. queue := make([]int, 5)

Solution

1. Step 1: Understand array declaration in Go

   Fixed-size arrays in Go are declared with var name [size]type, e.g., var queue [5]int.

2. Step 2: Check options for fixed-size array

   var queue [5]int uses var queue [5]int which is correct fixed-size array syntax.

3. Final Answer:

   var queue [5]int -> Option A

4. Quick Check:

   Fixed array = var name [size]type [OK]

Hint: Fixed array uses var name [size]type in Go [OK]

Common Mistakes:

• Using make for fixed-size array (make is for slices)
• Using slice literal with size inside braces
• Confusing slice and array syntax

3. Consider this Go code snippet implementing a queue using an array and two indices front and rear:

var queue [5]int
front, rear := -1, -1

// Enqueue 10
rear++
queue[rear] = 10

// Enqueue 20
rear++
queue[rear] = 20

// Dequeue
front++

// Enqueue 30
rear++
queue[rear] = 30

// Current queue elements from front+1 to rear are printed

What will be the printed queue elements?

medium

A. [20, 30]

B. [10, 20, 30]

C. [10, 30]

D. [30]

Solution

1. Step 1: Trace enqueue and dequeue operations

   Initially front = -1, rear = -1. Enqueue 10: rear=0, queue[0]=10 Enqueue 20: rear=1, queue[1]=20 Dequeue: front=0 (removes queue[0]=10) Enqueue 30: rear=2, queue[2]=30

2. Step 2: Identify current queue elements

   Queue elements are from front+1=1 to rear=2, so queue[1]=20 and queue[2]=30. Printed elements: [20, 30]

3. Final Answer:

   [20, 30] -> Option A

4. Quick Check:

   After dequeue, front=0; elements = queue[1..2] = [20,30] [OK]

Hint: Queue elements lie between front+1 and rear indices [OK]

Common Mistakes:

• Printing elements from 0 to rear ignoring front
• Not updating front after dequeue
• Confusing front and rear indices

4. Given this Go code snippet for dequeue operation in a queue implemented with array:

func dequeue() int {
    if front == rear {
        fmt.Println("Queue is empty")
        return -1
    }
    front++
    return queue[front]
}

What is the main bug in this code?

medium

A. It does not check if queue is full before dequeue

B. It should decrement rear instead of front

C. It increments front before returning element, causing off-by-one error

D. It returns queue[front] after increment, which is correct

Solution

1. Step 1: Understand dequeue logic

   Dequeue removes element at front+1 index. Incrementing front before returning queue[front] is correct to get the next element.

2. Step 2: Analyze options for bug

   It does not check if queue is full before dequeue is unrelated to dequeue. It increments front before returning element, causing off-by-one error says increment causes off-by-one error but this is standard for queue. It should decrement rear instead of front is wrong because rear is for enqueue. It returns queue[front] after increment, which is correct correctly states the code is correct.

3. Final Answer:

   It returns queue[front] after increment, which is correct -> Option D

4. Quick Check:

   Increment front then return element = correct dequeue [OK]

Hint: Dequeue increments front then returns element [OK]

Common Mistakes:

• Thinking front should not be incremented before return
• Confusing enqueue and dequeue pointers
• Checking full condition in dequeue

5. You have a fixed-size queue implemented using an array of size 5 with front and rear indices initialized to -1. After performing these operations:

Enqueue 5
Enqueue 10
Enqueue 15
Dequeue
Dequeue
Enqueue 20
Enqueue 25
Enqueue 30
Enqueue 35

What will happen when you try to enqueue 35, and what is the correct way to handle this situation?

hard

A. Queue underflow occurs; reset front and rear to -1

B. Queue overflow occurs; use circular queue logic to reuse space

C. Queue accepts 35 without issue; no special handling needed

D. Queue overflow occurs; increase array size dynamically

Solution

1. Step 1: Trace queue operations and indices

   Initial front = -1, rear = -1 Enqueue 5: rear=0 Enqueue 10: rear=1 Enqueue 15: rear=2 Dequeue: front=0 (removes 5) Dequeue: front=1 (removes 10) Enqueue 20: rear=3 Enqueue 25: rear=4 Enqueue 30: rear=5 (array size 5, index 5 invalid - overflow) Trying to enqueue 35 causes overflow

2. Step 2: Explain correct handling

   Since front has moved forward, space at start is free but rear reached end. Using circular queue logic allows rear to wrap to start and reuse space. Without circular logic, overflow occurs prematurely.

3. Final Answer:

   Queue overflow occurs; use circular queue logic to reuse space -> Option B

4. Quick Check:

   Overflow at end; circular queue fixes space reuse [OK]

Hint: Use circular queue to avoid overflow when space is free [OK]

Common Mistakes:

• Ignoring free space at start after dequeues
• Assuming array can grow dynamically
• Resetting front and rear incorrectly