Circular Queue Implementation Using Array in DSA Go - Build from Scratch

Circular Queue Implementation Using Array

📖 Scenario: Imagine you are managing a small parking lot with a fixed number of parking spots arranged in a circle. Cars enter and leave in order, and you want to keep track of which spots are occupied using a circular queue.

🎯 Goal: You will build a circular queue using an array in Go. This queue will help manage the parking spots by adding cars when they arrive and removing cars when they leave, wrapping around the array when needed.

📋 What You'll Learn

Create an array to hold the queue elements

Use variables to track the front and rear positions

Implement enqueue operation to add elements

Implement dequeue operation to remove elements

Print the queue state after operations

💡 Why This Matters

🌍 Real World

Circular queues are used in real-world systems like traffic lights, CPU scheduling, and buffering data streams where fixed-size buffers wrap around.

💼 Career

Understanding circular queues helps in roles involving system programming, embedded systems, and performance-critical applications.

1

Create the Circular Queue Array and Pointers

Create an integer array called queue with size 5. Also create two integer variables called front and rear, both initialized to -1.

DSA Go

var queue [5]int
var front int = -1
var rear int = -1
// Your code here

Hint

Use var to declare the array and variables. Initialize front and rear to -1 to indicate the queue is empty.

2

Add a Function to Enqueue Elements

Add a function called enqueue that takes an integer value and pointers to front, rear, and the queue array. Inside, check if the queue is full by comparing (rear + 1) % 5 with front. If not full, update rear and add value to queue[rear]. If front is -1, set it to 0.

DSA Go

package main

import "fmt"

func enqueue(value int, front *int, rear *int, queue *[5]int) {
    // Your code here
}

func main() {
    var queue [5]int
    var front int = -1
    var rear int = -1
}

Hint

Use pointers to modify front and rear inside the function. Use modulo % to wrap around the array.

3

Add a Function to Dequeue Elements

Add a function called dequeue that takes pointers to front, rear, and the queue array. If front is -1, print "Queue is empty" and return -1. Otherwise, store the value at queue[front], then if front equals rear, reset both to -1. Else, update front to (front + 1) % 5. Return the stored value.

DSA Go

package main

import "fmt"

func enqueue(value int, front *int, rear *int, queue *[5]int) {
    if (*rear+1)%5 == *front {
        fmt.Println("Queue is full")
        return
    }
    if *front == -1 {
        *front = 0
    }
    *rear = (*rear + 1) % 5
    queue[*rear] = value
}

func dequeue(front *int, rear *int, queue *[5]int) int {
    // Your code here
}

func main() {
    var queue [5]int
    var front int = -1
    var rear int = -1
}

Hint

Check if the queue is empty first. Use modulo to move front forward. Reset pointers when queue becomes empty.

4

Test the Circular Queue by Enqueueing and Dequeueing

In main, enqueue the values 10, 20, 30, 40, and 50 in order. Then dequeue two values and print them. Then enqueue 60 and 70. Finally, print all elements currently in the queue from front to rear in order, separated by spaces.

DSA Go

Hint

Remember to pass pointers to enqueue and dequeue. Use a loop with modulo to print from front to rear.

Practice

1. What is the main advantage of using a circular queue over a simple linear queue when implemented using an array?

easy

A. It allows storing different data types in the same queue.

B. It efficiently uses the available space by reusing freed slots.

C. It automatically sorts the elements in the queue.

D. It increases the maximum size of the queue beyond the array length.

Solution

1. Step 1: Understand linear queue limitation

   In a linear queue using an array, once the rear reaches the end, no more elements can be added even if there are empty slots at the front.

2. Step 2: Circular queue advantage

   A circular queue connects the end of the array back to the front, allowing reuse of empty slots freed by dequeued elements.

3. Final Answer:

   It efficiently uses the available space by reusing freed slots. -> Option B

4. Quick Check:

   Space reuse = Advantage [OK]

Hint: Circular queue reuses space freed by dequeues [OK]

Common Mistakes:

• Thinking circular queue increases array size
• Believing it sorts elements automatically
• Confusing data type flexibility with queue type

2. Which of the following is the correct way to check if a circular queue is full when using an array of size n with front and rear indices?

easy

A. if front == -1

B. if rear == front

C. if rear == n - 1

D. if (rear + 1) % n == front

Solution

1. Step 1: Understand full condition in circular queue

   The queue is full when the next position of rear (circularly) equals front.

2. Step 2: Apply modulo for circular increment

   Using modulo n ensures wrap-around, so (rear + 1) % n == front means full.

3. Final Answer:

   if (rear + 1) % n == front -> Option D

4. Quick Check:

   Full condition uses modulo wrap [OK]

Hint: Full when next rear equals front modulo array size [OK]

Common Mistakes:

• Checking rear == front means empty, not full
• Using rear == n - 1 ignores circular wrap
• Confusing front == -1 as full condition

3. Consider a circular queue of size 5 (indices 0 to 4). Initially, front = -1 and rear = -1. The following operations are performed:
enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), enqueue(50), enqueue(60)
What will be the values of front and rear after these operations?

medium

A. front = 1, rear = 0

B. front = 0, rear = 4

C. front = 1, rear = 3

D. front = 2, rear = 1

Solution

1. Step 1: Trace enqueue and dequeue operations

   Start: front = -1, rear = -1
   enqueue(10): front=0, rear=0
   enqueue(20): rear=1
   enqueue(30): rear=2
   dequeue(): front=1 (removes 10)
   enqueue(40): rear=3
   enqueue(50): rear=4
   enqueue(60): rear=(4+1)%5=0 (wraps around)

2. Step 2: Final front and rear values

   front = 1, rear = 0 after last enqueue.

3. Final Answer:

   front = 1, rear = 0 -> Option A

4. Quick Check:

   Wrap-around rear = 0, front moved after dequeue [OK]

Hint: Track front/rear changes step-by-step with modulo [OK]

Common Mistakes:

• Not wrapping rear index after reaching end
• Forgetting to update front after dequeue
• Assuming front stays at -1 after first enqueue

4. Given the following Go code snippet for a circular queue, what is the bug that causes incorrect enqueue operation?

func enqueue(q []int, front *int, rear *int, n int, value int) {
    if (*rear+1)%n == *front {
        fmt.Println("Queue is full")
        return
    }
    if *front == -1 {
        *front = 0
    }
    *rear = (*rear + 1) % n
    q[*rear] = value
}

medium

A. The check for full queue is incorrect; it should be rear == front.

B. The queue slice q is passed by value, so changes to q are not saved.

C. The front pointer is not updated when queue is empty.

D. The rear index is incremented before checking if queue is full.

Solution

1. Step 1: Check handling of empty queue

   The code updates front to 0 only if front == -1, handling the initial empty state correctly.

2. Step 2: Issue after full dequeues

   After dequeuing all elements, dequeue updates front = (front + 1) % n, making (*rear + 1) % n == *front true, falsely detecting full. Enqueue fails to update/reset front for subsequent empty states.

3. Final Answer:

   The front pointer is not updated when queue is empty. -> Option C

4. Quick Check:

   Handle non-initial empty by resetting front [OK]

Hint: Reset front when queue empty after dequeues [OK]

Common Mistakes:

• Confusing full condition with rear == front
• Overlooking empty queue handling after dequeues
• Thinking slice passing causes the issue

5. You have a circular queue implemented using an array of size 6. Initially, front = 4 and rear = 2. Which of the following sequences of operations will cause the queue to become full?

hard

A. dequeue, enqueue, enqueue, enqueue

B. enqueue, dequeue, enqueue, dequeue

C. dequeue, dequeue, enqueue, enqueue

D. dequeue, enqueue, dequeue

Solution

1. Step 1: Understand initial state and full condition

   Array size n=6, front=4, rear=2 (5 elements occupied, 1 free). Full: (rear + 1) % 6 == front.

2. Step 2: Simulate each option

   Only D causes final full state:
   dequeue: front=5, rear=2 (4 elem)
   enqueue: rear=3 (5 elem)
   enqueue: rear=4 (6 elem, now full since (4+1)%6=5==front)
   enqueue: full detected, no change. Final: front=5, rear=4 full.
   Others end not full.

3. Final Answer:

   dequeue, enqueue, enqueue, enqueue -> Option A

4. Quick Check:

   Simulate steps to check final full condition [OK]

Hint: Simulate front/rear moves to check full condition [OK]

Common Mistakes:

• Assuming enqueue always fills queue immediately
• Ignoring circular wrap in index calculations
• Not updating front on dequeue