Circular Queue Implementation Using Array in DSA Python - 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 when the last spot is reached, the next car goes back to the first spot if it is free. This is like a circular queue.

🎯 Goal: You will build a simple circular queue using an array to manage the parking spots. You will add cars, remove cars, and show the current state of the parking lot.

📋 What You'll Learn

Create an array to hold the queue elements with a fixed size

Use two pointers: front and rear to track the queue

Implement enqueue operation to add a car if space is available

Implement dequeue operation to remove a car if the queue is not empty

Print the current queue elements in order

💡 Why This Matters

🌍 Real World

Circular queues are used in real-world systems like traffic lights, CPU scheduling, and buffering data streams where resources are reused in a cycle.

💼 Career

Understanding circular queues helps in roles involving system design, embedded systems, and performance optimization where fixed-size buffers are common.

1

Create the Circular Queue Array and Pointers

Create a list called queue with 5 None elements to represent empty spots. Also create two variables front and rear and set both to -1 to indicate the queue is empty.

DSA Python

# Create queue list and initialize front and rear pointers
# Your code here

Hint

Use a list with 5 None values. Set front and rear to -1 to show the queue is empty.

2

Add a Car to the Circular Queue (Enqueue)

Create a function called enqueue(car) that adds car to the queue. Update rear to the next position in a circular way using modulo. If the queue is empty, set front to 0. Do not add if the queue is full (when next rear equals front).

DSA Python

queue = [None, None, None, None, None]
front = -1
rear = -1

# Define enqueue function to add a car
# Your code here

Hint

Check if queue is full by comparing next rear position with front. Use modulo to wrap around. Update front if queue was empty.

3

Remove a Car from the Circular Queue (Dequeue)

Create a function called dequeue() that removes and returns the car at front. If the queue becomes empty after removal, reset front and rear to -1. Otherwise, move front to the next position circularly.

DSA Python

queue = [None, None, None, None, None]
front = -1
rear = -1

def enqueue(car):
    global front, rear
    if (rear + 1) % len(queue) == front:
        return  # Queue is full, do nothing
    if front == -1:
        front = 0
    rear = (rear + 1) % len(queue)
    queue[rear] = car

# Define dequeue function to remove a car
# Your code here

Hint

Check if queue is empty first. Remove the car at front. If only one car was there, reset pointers. Otherwise, move front forward using modulo.

4

Print the Current Circular Queue

Write code to print the current elements in the queue from front to rear in order, separated by ' -> '. If the queue is empty, print 'Queue is empty'.

DSA Python

queue = [None, None, None, None, None]
front = -1
rear = -1

def enqueue(car):
    global front, rear
    if (rear + 1) % len(queue) == front:
        return  # Queue is full, do nothing
    if front == -1:
        front = 0
    rear = (rear + 1) % len(queue)
    queue[rear] = car

def dequeue():
    global front, rear
    if front == -1:
        return None  # Queue is empty
    car = queue[front]
    queue[front] = None
    if front == rear:
        front = -1
        rear = -1
    else:
        front = (front + 1) % len(queue)
    return car

# Print the queue elements from front to rear
# Your code here

Hint

Start from front and keep moving forward using modulo until you reach rear. Collect elements and join them with ' -> '.

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 efficiently uses the available space by reusing freed slots.

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

C. It automatically sorts the elements in the queue.

D. It eliminates the need for front and rear pointers.

Solution

1. Step 1: Understand linear queue limitation

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

2. Step 2: Circular queue reuses space

   Circular queue connects the end of the array back to the front, allowing reuse of freed slots and efficient space usage.

3. Final Answer:

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

4. Quick Check:

   Space reuse = Advantage [OK]

Hint: Circular queue reuses space unlike linear queue [OK]

Common Mistakes:

• Thinking circular queue sorts elements
• Believing circular queue removes need for pointers
• Assuming it stores multiple data types automatically

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

easy

A. if rear == max_size - 1

B. if rear == front

C. if front == -1

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

Solution

1. Step 1: Understand full condition in circular queue

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

2. Step 2: Use modulo for circular increment

   Using modulo operator, (rear + 1) % max_size gives the next position circularly.

3. Final Answer:

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

4. Quick Check:

   Full condition = (rear + 1) % max_size == front [OK]

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

Common Mistakes:

• Checking rear == front means full (actually empty)
• Using rear == max_size - 1 ignores circular wrap
• Checking front == -1 means empty, not full

3. Consider this circular queue code snippet with max_size = 5:

front = 0
rear = 3
queue = [10, 20, 30, 40, None]

# Enqueue operation
rear = (rear + 1) % 5
queue[rear] = 50

# Dequeue operation
front = (front + 1) % 5

print(queue)

What will be the printed output?

medium

A. [10, 20, 30, 40, 50] with front=1 and rear=4

B. [10, 20, 30, 40, None]

C. [10, 20, 30, 40, 50]

D. [10, 20, 30, 40, 50] with front=0 and rear=4

Solution

1. Step 1: Perform enqueue operation

   rear moves from 3 to (3+1)%5 = 4; queue[4] = 50; queue becomes [10, 20, 30, 40, 50]

2. Step 2: Perform dequeue operation

   front moves from 0 to (0+1)%5 = 1; front=1, rear=4

3. Final Answer:

   [10, 20, 30, 40, 50] with front=1 and rear=4 -> Option A

4. Quick Check:

   Enqueue rear=4, Dequeue front=1 [OK]

Hint: Track front and rear updates carefully after enqueue/dequeue [OK]

Common Mistakes:

• Ignoring front and rear pointer updates
• Assuming queue content changes on dequeue
• Confusing front and rear positions

4. The following code snippet for dequeue operation in a circular queue has a bug:

def dequeue(queue, front, rear, max_size):
    if front == -1:
        return None, front, rear  # Queue empty
    data = queue[front]
    if front == rear:
        front = rear = -1
    else:
        front = (front + 1) % max_size
    return data, front, rear

# Initial state
queue = [10, 20, 30, 40, 50]
front = 0
rear = 4

# Dequeue call
value, front, rear = dequeue(queue, front, rear, 5)
print(value, front, rear)

What is the bug in this code?

medium

A. The condition to check empty queue should be rear == -1, not front == -1.

B. The function does not update the queue after dequeue.

C. The function does not handle the case when queue is full.

D. The function incorrectly resets front and rear to -1 when queue becomes empty.

Solution

1. Step 1: Check queue update after dequeue

   The dequeue operation removes the element logically by moving front, but the queue array still holds the old value.

2. Step 2: Identify missing update

   To avoid stale data, the dequeued position should be cleared or updated (e.g., set to None) after dequeue.

3. Final Answer:

   The function does not update the queue after dequeue. -> Option B

4. Quick Check:

   Queue array update after dequeue [OK]

Hint: Dequeue should clear or update the dequeued slot [OK]

Common Mistakes:

• Checking only front for empty queue
• Not resetting pointers correctly after last dequeue
• Ignoring queue full condition in dequeue

5. You have a circular queue of size 6 (indices 0 to 5). Initially, front = 4 and rear = 2. The queue array is:
[70, 80, 90, None, 40, 50]

Which of the following sequences of operations will correctly enqueue 100 and dequeue two elements, updating front and rear properly?

hard

A. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6

B. Enqueue: rear = (rear + 2) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6

C. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6

D. Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 2) % 6

Solution

1. Step 1: Enqueue operation

   rear = (2 + 1) % 6 = 3; queue[3] = 100; queue becomes [70, 80, 90, 100, 40, 50]

2. Step 2: Dequeue two elements

   front moves twice: front = (4 + 1) % 6 = 5, then front = (5 + 1) % 6 = 0

3. Final Answer:

   Enqueue: rear = (rear + 1) % 6; queue[rear] = 100; Dequeue: front = (front + 1) % 6; front = (front + 1) % 6 -> Option C

4. Quick Check:

   One enqueue + two dequeues update pointers correctly [OK]

Hint: Increment pointers modulo size for each enqueue/dequeue [OK]

Common Mistakes:

• Incrementing rear or front by more than 1 at once
• Not using modulo for circular wrap
• Dequeueing fewer or more times than asked