concept · INFO-CS-ADS-061Circular Queues
A circular queue is a queue implementation in which the final array position connects logically back to the first position. It reuses empty positions created by dequeue operations and maintains FIFO ordering.
Explanation
Overview
A circular queue is a FIFO data structure that treats its storage positions as a circular sequence. When the rear reaches the last array index, it can wrap around to the beginning if space is available.
Purpose
Circular queues solve the space-reuse limitation of simple linear array queues. They are useful for fixed-size buffers and applications that repeatedly insert and remove elements.
Time complexity
enqueue: O(1); dequeue: O(1); front: O(1); rear: O(1); search: O(n); traversal: O(n)
Space complexity
O(C) for an array with capacity C, regardless of how many positions are currently occupied.
Example
capacity: 5; initialArray: 10; 20; initialFront: 0; initialRear: 2; operation: DEQUEUE() followed by ENQUEUE(40); afterDequeue: logicalQueue: 20; 30; front: 1
Advantages
Reuses empty array positions.; Avoids shifting all remaining elements after dequeue.; Provides constant-time enqueue and dequeue in a typical implementation.; Uses a fixed array efficiently for repeated insertions and removals.; Suitable for continuous data buffering.
Limitations
Capacity is fixed unless resizing is added.; Circular index calculations require careful implementation.; Full and empty states must be distinguished consistently.; Incorrect front or rear updates can overwrite existing elements or lose queue data.
Example or application
Operation
DEQUEUE() followed by ENQUEUE(40)
Explanation
The queue advances its front after removal and inserts the new value at the next rear position.
Definition
A circular queue is a FIFO data structure that treats its storage positions as a circular sequence. When the rear reaches the last array index, it can wrap around to the beginning if space is available.
Purpose
Circular queues solve the space-reuse limitation of simple linear array queues. They are useful for fixed-size buffers and applications that repeatedly insert and remove elements.
Core Principle
The front and rear positions move through the array using circular indexing. The next position after the final array index is the first index.
Main Components
Array: Stores the queue elements.
Front: Identifies the first element to be removed.
Rear: Identifies the final element or the position used for insertion.
Capacity: Total number of available array positions.
Size: Number of currently occupied positions, when maintained.
Circular Indexing
General Expression
(index + 1) % capacity
Explanation
The modulo operation wraps the index to zero when advancing beyond the final valid array position.
Enqueue Procedure
Check whether the circular queue is full.
Calculate the next rear position using circular indexing.
Insert the new element at the calculated position.
Update the rear reference or index.
Update the size counter if maintained.
Initialize front appropriately when inserting the first element.
Dequeue Procedure
Check whether the circular queue is empty.
Save the element at the front position.
Advance front using circular indexing.
Decrease the size counter if maintained.
Reset the empty-state metadata when the final element is removed.
Return the removed value.
Full And Empty Conditions
One Empty Slot Convention
Full
(rear + 1) % capacity == front
Note
This convention leaves one array position unused to distinguish full from empty without a separate size counter.
Explanation
Different implementations use different state conventions. The full and empty checks must match the chosen convention.
Linear Vs Circular Queue
Linear Queue
A simple linear array queue may reach the final rear index while earlier positions are empty and cannot be reused without shifting elements.
Circular Queue
A circular queue wraps indices to the beginning, allowing previously freed positions to be reused.
Shared Behavior
Both preserve FIFO ordering.
Advantages
Reuses empty array positions.
Avoids shifting all remaining elements after dequeue.
Provides constant-time enqueue and dequeue in a typical implementation.
Uses a fixed array efficiently for repeated insertions and removals.
Suitable for continuous data buffering.
Limitations
Capacity is fixed unless resizing is added.
Circular index calculations require careful implementation.
Full and empty states must be distinguished consistently.
Incorrect front or rear updates can overwrite existing elements or lose queue data.
Space Complexity
O(C) for an array with capacity C, regardless of how many positions are currently occupied.
Implementation Considerations
Choose one consistent method for tracking full and empty states.
Use modulo arithmetic for circular index movement.
Handle insertion into an empty queue correctly.
Handle removal of the final element correctly.
Prevent overwriting an occupied position.
Test wraparound behavior at the beginning and end of the array.
Common Applications
Keyboard and input buffers
Audio and video streaming buffers
Network packet buffers
Producer-consumer systems
Round-robin scheduling
Embedded systems with fixed memory
Real-time data processing
Learning Objectives
Explain the purpose of circular queues.
Understand circular indexing and wraparound.
Describe enqueue and dequeue operations.
Distinguish full and empty conditions.
Compare linear and circular array queues.
Key Takeaways
A circular queue treats array storage as a continuous loop.
Modulo arithmetic supports index wraparound.
Previously freed positions can be reused.
Enqueue and dequeue generally take O(1) time.
A consistent full and empty convention is essential.
Related Topics
Introduction to Queues
Queue Operations — Enqueue and Dequeue
Queue Implementation Using Arrays and Linked Lists
Double-Ended Queues (Deque)
Priority Queues
Round-Robin Scheduling
Practice Questions
| Question | Answer |
|---|
What is the main purpose of circular queues? | A circular queue is a queue implementation in which the final array position connects logically back to the first position. It reuses empty positions created by dequeue operations and maintains FIFO ordering. |
What should be checked before applying circular queues? | For circular queues, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of circular queues be validated? | Trace a representative circular queues case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Scienexy Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures