Overview#

A circular array is not a new physical storage structure, but rather a way of “connecting the ends of an ordinary array together.” It uses modulo arithmetic to make the index wrap back to the beginning at the array boundary, thereby simulating a ring.

This structure is especially suitable for scenarios with fixed capacity and continuous reads and writes, such as circular queues, log buffers, audio and video frame buffers, and the most recent N records.

An ordinary array stops once its tail reaches the capacity limit, whereas a circular array maps the next write back to a previously freed position.

Prerequisites

• Modulo arithmetic: indices wrap around via % capacity
• Queue semantics: head and tail pointers handle reads and writes respectively
• Capacity design: empty and full states need to be distinguished

Problem Definition#

Suppose we have an array with a fixed length of 5:

1
index: 0 1 2 3 4
2
value: _ _ _ _ _

We want it to support:

• Writing new elements from the tail;
• Reading old elements from the head;
• Not moving elements when space runs out;
• Automatically returning to 0 when the index goes past the tail.

This is the problem that a circular array solves: using a fixed array to implement logically circular space.

Core Principle: Step-by-Step Diagram#

A circular array usually maintains three states:

1
capacity: fixed capacity
2
head:     next read position
3
tail:     next write position
4
size:     current number of elements

1
tail = (tail + 1) % capacity

1
index: 0 1 2 3 4
2
value: C D _ A B
3
head:        ^
4
tail:     ^

1
head = (head + 1) % capacity

Detailed Algorithm Steps#

When implementing a circular queue, the key point is distinguishing “empty” from “full.” There are two common approaches:

This article adopts the size approach because it is better suited to teaching and TypeScript encapsulation.

Enqueue steps:

1. If the queue is full, reject the write;
2. Write the element to items[tail];
3. Move tail forward by one position and apply modulo;
4. Increment size by one.

Dequeue steps:

1. If the queue is empty, return undefined;
2. Read items[head];
3. Clear the current position;
4. Move head forward by one position and apply modulo;
5. Decrement size by one.

TypeScript Implementation#

1
class CircularQueue<T> {
2
  private readonly items: Array<T | undefined>;
3
  private head = 0;
4
  private tail = 0;
5
  private count = 0;
6

7
  constructor(private readonly capacity: number) {
8
    if (capacity <= 0) {
9
      throw new Error('capacity must be positive');
10
    }
11

12
    this.items = new Array<T | undefined>(capacity);
13
  }
14

15
  get size(): number {
16
    return this.count;
17
  }
18

19
  isEmpty(): boolean {
20
    return this.count === 0;
21
  }
22

23
  isFull(): boolean {
24
    return this.count === this.capacity;
25
  }
26

27
  enqueue(value: T): boolean {
28
    if (this.isFull()) return false;
29

30
    this.items[this.tail] = value;
31
    this.tail = (this.tail + 1) % this.capacity;
32
    this.count++;
33
    return true;
34
  }
35

36
  dequeue(): T | undefined {
37
    if (this.isEmpty()) return undefined;
38

39
    const value = this.items[this.head];
40
    this.items[this.head] = undefined;
41
    this.head = (this.head + 1) % this.capacity;
42
    this.count--;
43
    return value;
44
  }
45

46
  peek(): T | undefined {
47
    return this.items[this.head];
48
  }
49
}
50

51
const queue = new CircularQueue<number>(3);
52
queue.enqueue(1);
53
queue.enqueue(2);
54
queue.enqueue(3);
55
console.log(queue.enqueue(4)); // false
56
console.log(queue.dequeue()); // 1
57
queue.enqueue(4);

In this implementation, the array capacity never changes, and all positions can be reused.

Engineering Optimization: Ring Buffer#

In logging or monitoring scenarios, sometimes we do not want to reject writes after the queue is full, but instead overwrite the oldest data. This is a ring buffer.

1
class RingBuffer<T> {
2
  private readonly items: Array<T | undefined>;
3
  private next = 0;
4
  private count = 0;
5

6
  constructor(private readonly capacity: number) {
7
    this.items = new Array<T | undefined>(capacity);
8
  }
9

10
  push(value: T): void {
11
    this.items[this.next] = value;
12
    this.next = (this.next + 1) % this.capacity;
13
    this.count = Math.min(this.count + 1, this.capacity);
14
  }
15

16
  values(): T[] {
17
    const result: T[] = [];
18
    const start = this.count === this.capacity ? this.next : 0;
19

20
    for (let i = 0; i < this.count; i++) {
21
      const index = (start + i) % this.capacity;
22
      result.push(this.items[index] as T);
23
    }
24

25
    return result;
26
  }
27
}

A queue emphasizes “not losing data,” while a buffer emphasizes “keeping the latest data.” Both use a circular array, but their business semantics differ.

Applications and Limitations#

Summary#

• A circular array uses modulo to turn an ordinary array into a logical closed loop.
• head, tail, and size are the core states for implementing a circular queue.
• The difference between a queue and a buffer lies in the full-policy.
• It is suitable for scenarios with fixed capacity, high-frequency reads and writes, and avoidance of element shifting.