Circular Queue

# CHAPTER 13

Circular Queue #

1. Introduction #

2. Learning Objectives #

• Understand the mechanics of the "False Overflow" bug.

• Utilize Modulo Arithmetic (%) to manipulate array indexes.

• Implement a Circular Queue utilizing a static array.

• Differentiate between a "Full" state and an "Empty" state in circular logic.

3. The Core Concept: Wrap-Around Mathematics #

If the Array size (MAX) is 5, the indexes are 0, 1, 2, 3, 4. When rear = 4, where does it go next? Instead of executing rear = rear + 1 (which equals 5, crashing the program), we execute: rear = (rear + 1) % MAX (4 + 1) % 5 equals 0! The pointer seamlessly teleports back to the beginning of the array, filling the empty spaces abandoned by the dequeue operation.

4. Tracking the Pointers #

1. 1. Empty State: front = -1 and rear = -1.

1. 2. Single Element: front == rear.

1. 3. Full State: (rear + 1) % MAX == front. (This means the rear pointer has wrapped around the track and is literally one step behind the front pointer, mathematically proving there are zero empty slots left).

5. Implementation: The Ring Buffer #

// C Example: Circular Queue Implementation
#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1;
int rear = -1;

void enqueue(int data) {
    // 1. Check for True Overflow (Queue is absolutely full)
    if ((rear + 1) % MAX == front) {
        printf("Queue is Full! (True Overflow)\n");
        return;
    }
    
    // 2. If it's the very first element being inserted
    if (front == -1 && rear == -1) {
        front = 0;
        rear = 0;
    } 
    // 3. Normal Insertion with Modulo Wrap-Around!
    else {
        rear = (rear + 1) % MAX;
    }
    
    queue[rear] = data; // Insert data
    printf("Inserted: %d\n", data);
}

int dequeue() {
    // 1. Check for Underflow
    if (front == -1) {
        printf("Queue is Empty!\n");
        return -1;
    }
    
    int data = queue[front]; // Extract the data
    
    // 2. If we just removed the very last element in the queue
    if (front == rear) {
        front = -1; // Reset to absolute zero
        rear = -1;
    } 
    // 3. Normal Removal with Modulo Wrap-Around!
    else {
        front = (front + 1) % MAX;
    }
    
    return data;
}

6. Complexity Analysis #

7. Real-World Applications #

1. 1. Hardware Buffers: When you type on a keyboard, the keystrokes are sent to a tiny, fixed-size Circular Queue hardware chip. The CPU reads (dequeues) the keys. If you type faster than the CPU can process, the buffer wraps around and eventually hits the "Full" state, causing the computer to beep at you!

1. 2. Audio/Video Streaming: Netflix streams data into a fixed-size Ring Buffer. The video player reads data from the front, while the network connection writes data to the rear. When the pointers get too close, the video pauses to "Buffer".

1. 3. Traffic Lights: Managing the sequential looping of Red -> Green -> Yellow.

8. Common Mistakes #

• Confusing Full and Empty Conditions: Because the pointers wrap around each other endlessly, front == rear does NOT mean the queue is full. It actually means the queue contains exactly 1 element! The only mathematical way to prove the queue is completely full is the modulo equation (rear + 1) % MAX == front.

9. Best Practices #

• Use Modulo for EVERYTHING: Do not write complex, heavily nested if (rear == MAX - 1) statements. Trust the (rear + 1) % MAX formula. It elegantly handles the mathematical wrap-around in a single line of perfectly optimized CPU instruction code.

10. Exercises #

1. 1. Trace the mathematical values of front and rear for a Circular Queue of MAX=4 after: enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), enqueue(50).

1. 2. Why does the front == -1 condition exist? What specific software state does it prevent?

11. MCQs with Answers #

12. Interview Preparation #

• *Whiteboard Math:* "Write the exact line of C++ or Java code required to move the front pointer backward (counter-clockwise) by 1 step in a Circular Queue while preventing negative index out-of-bounds errors." *(Hint: front = (front - 1 + MAX) % MAX; Adding MAX prevents negative numbers during modulo division!).*

Common Pitfalls:

• In whiteboard interviews, candidates easily remember (rear + 1) % MAX for enqueueing, but catastrophically forget to apply the exact same modulo logic to the front pointer during dequeue()! If front doesn't wrap around, the algorithm shatters.

13. FAQs #

14. Summary #

15. Next Chapter Recommendation #