Circular Array

A circular array treats a fixed-size array as if it wraps around. Indices advance modulo the capacity, so the structure forms a logical ring.

You use it when you need constant-time insertions and removals at both ends within a bounded buffer.

Problem

Maintain a sequence $A$ of capacity $n$ that supports:

• insert at front and back
• remove from front and back
• wrap indices without shifting elements

Structure

A circular array maintains:

• an array of size $n$
• a head index
• a tail index

Positions wrap using modulo arithmetic:

$$ index = (base + offset) \bmod n $$

Algorithm

Insert at the back:

push_back(A, x):
    if size == capacity:
        error "full"

    A[tail] = x
    tail = (tail + 1) mod capacity
    size += 1

Remove from the front:

pop_front(A):
    if size == 0:
        error "empty"

    value = A[head]
    head = (head + 1) mod capacity
    size -= 1
    return value

Example

Let capacity be $5$.

step	operation	array	head	tail
1	push 8	[8, -, -, -, -]	0	1
2	push 3	[8, 3, -, -, -]	0	2
3	pop	[8, 3, -, -, -]	1	2
4	push 5	[8, 3, 5, -, -]	1	3
5	push 1	[8, 3, 5, 1, -]	1	4
6	push 9	[8, 3, 5, 1, 9]	1	0

The tail wraps from index $4$ back to $0$.

Correctness

At all times:

• elements occupy positions from head to tail in cyclic order
• modulo arithmetic ensures indices remain within bounds
• size tracks the number of valid elements

Thus operations maintain correct ordering without shifting elements.

Complexity

operation	time
push_back	$O(1)$
push_front	$O(1)$
pop_front	$O(1)$
pop_back	$O(1)$

Space usage:

$$ O(n) $$

When to Use

Circular arrays are appropriate when:

• a fixed-size buffer is sufficient
• constant-time queue or deque operations are required
• memory allocation must remain stable

They are less suitable when:

• capacity must grow dynamically
• random insertions in the middle are required

Implementation

class CircularArray:
    def __init__(self, capacity):
        self.a = [None] * capacity
        self.capacity = capacity
        self.head = 0
        self.tail = 0
        self.size = 0

    def push_back(self, x):
        if self.size == self.capacity:
            raise Exception("full")
        self.a[self.tail] = x
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1

    def pop_front(self):
        if self.size == 0:
            raise Exception("empty")
        value = self.a[self.head]
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return value

type CircularArray[T any] struct {
    data     []T
    head     int
    tail     int
    size     int
    capacity int
}

func NewCircularArray[T any](capacity int) *CircularArray[T] {
    return &CircularArray[T]{
        data:     make([]T, capacity),
        capacity: capacity,
    }
}

func (c *CircularArray[T]) PushBack(x T) bool {
    if c.size == c.capacity {
        return false
    }
    c.data[c.tail] = x
    c.tail = (c.tail + 1) % c.capacity
    c.size++
    return true
}

func (c *CircularArray[T]) PopFront() (T, bool) {
    var zero T
    if c.size == 0 {
        return zero, false
    }
    v := c.data[c.head]
    c.head = (c.head + 1) % c.capacity
    c.size--
    return v, true
}