Circular queue in Data Structures Theory - Mini Project: Build & Apply

Understanding Circular Queue

📖 Scenario: Imagine you are managing a small parking lot with a fixed number of parking spaces arranged in a circle. Cars enter and leave the lot in order, and when the lot is full, new cars must wait until a space is free. This setup works like a circular queue.

🎯 Goal: Build a simple circular queue model using a list and pointers to track the front and rear positions. You will create the data structure, set up control variables, implement the logic to add and remove cars, and finalize the queue management.

📋 What You'll Learn

Create a list called parking_lot with 5 empty slots represented by None

Create two variables called front and rear both set to -1

Write a function called enqueue(car) that adds a car to the circular queue if space is available

Write a function called dequeue() that removes a car from the circular queue if it is not empty

💡 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 software development roles involving system design, embedded systems, and performance optimization.

1

Create the parking lot list

Create a list called parking_lot with exactly 5 slots, each initialized to None to represent empty parking spaces.

Data Structures Theory

# Create the parking_lot list with 5 None values
# Your code here

Hint

Use square brackets to create a list with 5 None elements.

2

Set up front and rear pointers

Create two variables called front and rear and set both to -1 to indicate the queue is initially empty.

Data Structures Theory

parking_lot = [None, None, None, None, None]
# Initialize front and rear pointers
# Your code here

Hint

Set both front and rear to -1 to show the queue is empty.

3

Write the enqueue function

Write a function called enqueue(car) that adds a car to the parking_lot circular queue. It should update rear and handle wrapping around. If the queue is full, do nothing.

Data Structures Theory

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

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

Hint

Use modulo % to wrap rear around the list length.

4

Write the dequeue function

Write a function called dequeue() that removes a car from the parking_lot circular queue. It should update front and handle wrapping around. If the queue is empty, do nothing.

Data Structures Theory

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

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

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

Hint

Reset front and rear to -1 when queue becomes empty.

Practice

1. What is the main advantage of a circular queue compared to a regular linear queue?

easy

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

B. It efficiently reuses empty space by connecting the end to the start.

C. It automatically sorts elements while enqueuing.

D. It requires shifting elements after every dequeue operation.

Solution

1. Step 1: Understand the structure of a circular queue

   A circular queue connects the last position back to the first, forming a circle.

2. Step 2: Identify the advantage over a linear queue

   This connection allows the queue to reuse spaces freed by dequeued elements without shifting.

3. Final Answer:

   It efficiently reuses empty space by connecting the end to the start. -> Option B

4. Quick Check:

   Circular queue = space reuse [OK]

Hint: Circular queue wraps around to reuse space [OK]

Common Mistakes:

• Thinking it sorts elements automatically
• Believing it stores multiple data types
• Assuming it shifts elements after dequeue

2. Which of the following is the correct way to update the rear pointer in a circular queue after an enqueue operation?

easy

A. rear = (rear + 1) % size

B. rear = rear + 1

C. rear = rear - 1

D. rear = size - rear

Solution

1. Step 1: Recall how circular queue pointers move

   In a circular queue, pointers wrap around using modulo arithmetic to stay within bounds.

2. Step 2: Apply modulo to update rear pointer

   After enqueue, rear moves to (rear + 1) modulo the queue size to wrap if needed.

3. Final Answer:

   rear = (rear + 1) % size -> Option A

4. Quick Check:

   Rear update uses modulo [OK]

Hint: Use modulo (%) to wrap rear pointer [OK]

Common Mistakes:

• Incrementing rear without modulo
• Decrementing rear after enqueue
• Using subtraction instead of modulo

3. Consider a circular queue of size 5 with front = 3 and rear = 1. Which of the following statements is true about the queue state?

medium

A. The queue is empty.

B. The queue is full.

C. The queue has 3 elements.

D. The queue has 4 elements.

Solution

1. Step 1: Understand front and rear positions in circular queue

   Front at 3 and rear at 1 means rear has wrapped around past front.

2. Step 2: Calculate number of elements using formula

   Number of elements = (rear - front + size) % size = (1 - 3 + 5) % 5 = 3 % 5 = 3.

3. Final Answer:

   The queue has 3 elements. -> Option C

4. Quick Check:

   Elements count = 3 [OK]

Hint: Use (rear - front + size) % size to count elements [OK]

Common Mistakes:

• Confusing full and empty conditions
• Ignoring modulo in calculation
• Assuming rear < front means empty

4. Given this code snippet for dequeue in a circular queue, what is the error?

if front == -1:
    print("Queue is empty")
else:
    data = queue[front]
    if front == rear:
        front = rear = -1
    else:
        front = (front + 1) % size

medium

A. The code does not return or use the dequeued data.

B. The front pointer update should use rear instead of front.

C. The condition to check empty queue is incorrect.

D. The rear pointer should be incremented after dequeue.

Solution

1. Step 1: Analyze the dequeue operation steps

   The code checks if queue is empty, retrieves data, updates pointers correctly.

2. Step 2: Identify missing usage of dequeued data

   Though data is assigned, it is neither returned nor used, so the operation loses the dequeued value.

3. Final Answer:

   The code does not return or use the dequeued data. -> Option A

4. Quick Check:

   Dequeue must return data [OK]

Hint: Always return dequeued element [OK]

Common Mistakes:

• Not returning dequeued value
• Incorrect pointer updates
• Incrementing rear on dequeue

5. You have a circular queue of size 6. Initially, front = 0 and rear = 4. You perform two dequeue operations followed by three enqueue operations. What will be the final positions of front and rear?

hard

A. front = 1, rear = 2

B. front = 2, rear = 0

C. front = 0, rear = 5

D. front = 2, rear = 1

Solution

1. Step 1: Update front after two dequeues

   Each dequeue moves front by 1 modulo size: front = (0 + 2) % 6 = 2.

2. Step 2: Update rear after three enqueues

   Each enqueue moves rear by 1 modulo size: rear = (4 + 3) % 6 = 7 % 6 = 1.

3. Final Answer:

   front = 2, rear = 1 -> Option D

4. Quick Check:

   Front and rear updated with modulo [OK]

Hint: Add operations to pointers using modulo size [OK]

Common Mistakes:

• Not using modulo for pointer wrap-around
• Mixing front and rear updates
• Forgetting to update pointers after each operation