# Circular Array

# 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:

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

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

Remove from the front:

```id="y2k9hf"
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

```id="k91d2m"
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
```

```id="z4v7q8"
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
}
```