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
}