Circular Queue

Introduction

Circular queue: specialized linear data structure. Concept: last position connects back to first. Purpose: efficient memory reuse, avoids "false overflow". Widely used in buffer management, scheduling algorithms, data streaming.

"Queues are fundamental in computer science for managing ordered data; circular queues optimize queue utilization by eliminating wasted space." -- Donald Knuth

Definition and Concept

What is a Circular Queue?

Queue variant where rear and front wrap back to start on reaching end. Implements FIFO principle, supports enqueue and dequeue. Unlike linear queue, circular queue uses modulo arithmetic to cycle indices.

Core Idea

Memory segments arranged circularly. After last index, next element stored at zero index. Prevents queue overflow when space is available at front but rear is at end.

Terminology

Front: index of element to dequeue. Rear: index of last enqueued element. Size: fixed array length. Empty condition: front = -1. Full condition: (rear + 1) mod size = front.

Data Structure Layout

Underlying Storage

Fixed-size array or buffer. Circular indexing used to map logical queue order onto physical array.

Index Management

Increment indices with modulo operator: (index + 1) % size. Ensures wrap around.

State Variables

Front pointer: tracks dequeue position. Rear pointer: tracks enqueue position. Both initialized at -1 or 0 depending on implementation.

Basic Operations

Enqueue

Add element at rear index. Update rear: (rear + 1) mod size. If queue full, reject insertion.

Dequeue

Remove element at front index. Update front: (front + 1) mod size. If queue empty, reject removal.

Peek / Front

Access element at front without removing. Used to inspect next dequeue candidate.

IsEmpty

Condition: front == -1 or front == rear + 1 (depending on implementation). Indicates no elements.

IsFull

Condition: (rear + 1) % size == front. Indicates queue reached full capacity.

ENQUEUE(element): if (rear + 1) % size == front: error "Queue Full" else if front == -1: front = 0 rear = 0 else: rear = (rear + 1) % size array[rear] = elementDEQUEUE(): if front == -1: error "Queue Empty" element = array[front] if front == rear: front = -1 rear = -1 else: front = (front + 1) % size return element

Implementation Details

Array-Based Implementation

Array allocation of fixed size. Front and rear pointers managed with modulo arithmetic. Memory efficient, direct indexing.

Linked List-Based Implementation

Nodes connected circularly. Rear points to front node. Dynamic size but increased pointer overhead.

Initialization

Set front and rear to -1 or 0. Array elements undefined initially. Careful handling of empty and full states essential.

Edge Cases Handling

Single element queue: front == rear. Full vs empty condition distinction critical to avoid ambiguity.

Advantages over Linear Queue

Memory Utilization

Reuses vacant slots after dequeue. No wasted space at front.

Performance

Constant time enqueue and dequeue. No shifting of elements required.

Predictable Capacity

Fixed size ensures controlled memory usage.

Simple Indexing

Modulo arithmetic enables elegant circular wrap-around logic.

Limitations and Drawbacks

Fixed Size

Array-based queue has static capacity, prone to overflow if not sized correctly.

Complexity in Full/Empty Conditions

Ambiguity between full and empty states requires careful handling.

Limited Flexibility

Not suitable for dynamically growing queues without resizing logic.

Potential Wasted Space

One slot often sacrificed to distinguish full vs empty, reducing capacity by one.

Applications

Buffer Management

Used in circular buffers for streaming data, real-time audio/video buffering.

CPU Scheduling

Round-robin algorithms utilize circular queues to cycle through processes.

Resource Scheduling

Network packet scheduling, printer spooling, and task management.

Data Streaming

Handling continuous data streams where fixed-size buffers are required.

Time and Space Complexity

Time Complexity

Enqueue: O(1), Dequeue: O(1), Peek: O(1). Constant time due to direct indexing.

Space Complexity

O(n) for array-based implementation, where n is fixed queue size.

Auxiliary Space

Minimal additional variables (front, rear pointers).

Comparison with Other Queues

Linear Queue

Linear queue wastes space after dequeue; circular queue reuses space. Circular queue preferred for fixed capacity buffers.

Deque (Double Ended Queue)

Deque allows insertion/removal at both ends; circular queue only supports FIFO at front and rear.

Priority Queue

Priority queue orders elements by priority; circular queue maintains strict FIFO order.

Linked List Queue

Linked list dynamic size, no fixed capacity; circular queue fixed size, more cache friendly.

Code Example

Array-Based Circular Queue in C

#include <stdio.h>#define SIZE 5int queue[SIZE];int front = -1, rear = -1;int isFull() { return ((rear + 1) % SIZE == front);}int isEmpty() { return (front == -1);}void enqueue(int element) { if (isFull()) { printf("Queue is full\n"); return; } if (isEmpty()) { front = 0; } rear = (rear + 1) % SIZE; queue[rear] = element; printf("Enqueued %d\n", element);}int dequeue() { if (isEmpty()) { printf("Queue is empty\n"); return -1; } int element = queue[front]; if (front == rear) { front = -1; rear = -1; } else { front = (front + 1) % SIZE; } return element;}int main() { enqueue(10); enqueue(20); enqueue(30); enqueue(40); enqueue(50); // should show full printf("Dequeued: %d\n", dequeue()); enqueue(50); // now enqueue should succeed return 0;}

Visualization and Diagrams

Circular Indexing Illustration

Queue represented as circular buffer with indices 0 to n-1. Rear and front pointers move clockwise. Wrap-around occurs at boundary.

State Transitions

Empty → First enqueue sets front and rear to 0. Enqueue increments rear modulo size. Dequeue increments front modulo size. Empty when front = -1.

Example Diagram

Initial State:[ _ , _ , _ , _ , _ ] front = -1, rear = -1After enqueue(1):[ 1 , _ , _ , _ , _ ] front = 0, rear = 0After enqueue(2):[ 1 , 2 , _ , _ , _ ] front = 0, rear = 1After dequeue():[ 1 , 2 , _ , _ , _ ] front = 1, rear = 1After enqueue(3), enqueue(4), enqueue(5):[ 1 , 2 , 3 , 4 , 5 ] front = 1, rear = 0 (wrapped)Queue Full: (rear + 1) % size == front

References

• Knuth, D. E., "The Art of Computer Programming, Volume 1: Fundamental Algorithms," Addison-Wesley, 3rd Edition, 1997, pp. 237-240.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., "Introduction to Algorithms," MIT Press, 3rd Edition, 2009, pp. 170-175.
• Sedgewick, R., Wayne, K., "Algorithms," Addison-Wesley, 4th Edition, 2011, pp. 169-174.
• Goodrich, M. T., Tamassia, R., Goldwasser, M. H., "Data Structures and Algorithms in C++," Wiley, 2nd Edition, 2011, pp. 120-125.
• Aho, A. V., Hopcroft, J. E., Ullman, J. D., "Data Structures and Algorithms," Addison-Wesley, 1983, pp. 88-92.