✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-061

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.

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

Capacity

5

Initial Array

  • 10

  • 20

  • 30

Initial Front

0

Initial Rear

2

Operation

DEQUEUE() followed by ENQUEUE(40)

After Dequeue

Logical Queue

  • 20

  • 30

Front

1

Rear

2

After Enqueue

Logical Queue

  • 20

  • 30

  • 40

Front

1

Rear

3

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

Size Based

Empty

size == 0

Full

size == capacity

One Empty Slot Convention

Empty

front == -1

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.

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.

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

QuestionAnswer

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