Skip to content
Algorithm Atlas
Data StructuresAll categories
CoreSource checked

Circular Buffer

Stores a fixed-size queue by wrapping read and write positions around an array.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Beginner
Family
Queue Buffer
Tier
Core
Status
Verified
Review
Source Checked
Sources
2
Formulas
1
Relationships
2
Code example
Ready
Visualization
Ready

Overview

A Circular Buffer reuses array slots as items are consumed, making it useful for streams and producer-consumer queues.

Core Concepts

fixed capacityhead indextail indexmodulo wrap

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(1)

Worst

O(1)

Space

O(capacity)

When to Use

  • Use when a bounded FIFO or rolling history should avoid reallocations.
  • Use when audio buffers is a central requirement.

When Not to Use

  • Avoid when the queue must grow without a fixed upper bound.
  • Avoid when a simpler array, map, or list already meets the access pattern.

What It Does

  • Maintains head and tail indices
  • Wraps indices at capacity
  • Reuses fixed storage

Use Cases

  • Audio buffers
  • Streaming queues
  • Recent event history

Inputs

  • Fixed-capacity array
  • Push and pop operations

Outputs

  • FIFO sequence with bounded capacity

Key Formulas (1)

Wrapped index

nextindex = (index + 1) mod capacity
next_index = (index + 1) mod capacity

Moves a pointer forward while wrapping back to the start.

Pseudocode

  1. 1.Keep head and tail indices
  2. 2.Write new items at tail
  3. 3.Advance tail modulo capacity
  4. 4.Read items from head
  5. 5.Advance head modulo capacity

Canonical Example

Input
capacity = 3, push A B C, pop A, push D
Output
buffer order = B C D
Explanation
The write position wraps around to reuse the freed slot.

Implementation Notes

  • Track a count or reserve one empty slot to distinguish states.
  • Keep update operations small and test invariants after insertions and deletions.
  • Keep a tiny example with known output beside the implementation.
  • Test updates and queries as sequences, not only one operation at a time.

Common Pitfalls

  • Confusing full and empty when head equals tail causes data loss or stalls.
  • The advertised performance depends on maintaining the structure's invariants.
  • Not defining boundary, empty, or degenerate inputs before implementation.
  • Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show head and tail pointers wrapping around a fixed array.

Circular Buffer mechanism walkthrough step 1 of 5suvwxt
Step 1 of 5: Keep head and tail indices
data-structure

Notes

Full and empty states need a clear convention, such as storing count separately.

Sources (2)

What each reference supports for this entry.

Handbook of Data Structures and Applications

Book

Data-structures reference for fixed-capacity ring buffers, head/tail indexing, queue semantics, and wraparound behavior.

Boost.Circular Buffer Documentation

Documentation

Official documentation for circular-buffer fixed-capacity storage, overwrite behavior, and wraparound container operations.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Used byRound Robin Scheduling

Scheduling · Foundation

Round-robin schedulers can use circular queues to rotate runnable tasks.

Compare with this
Conceptual neighborsDeque

Data Structures · Foundation

Circular buffers are a common way to implement deque-like storage.

Compare with this

Relationships

View full relationship page
Used byRound Robin Scheduling

Round-robin schedulers can use circular queues to rotate runnable tasks.

Related Algorithms

Round Robin SchedulingHash Table

Tags

Data StructureQueueBuffer