ring_buffer.md

Ring Buffer

A dynamic-capacity circular buffer. Uses head and tail pointers with modular arithmetic to wrap around. Doubles capacity when full.

Time Complexity

Operation	Big O
Push	O(1) amortized
Pop	O(1)
Peek	O(1)

Space complexity: O(n)

Pseudocode

Grow

GROW(buffer):
    newCap = buffer.cap * 2
    newItems = NEW array of size newCap
    FOR i = 0 TO buffer.len - 1
        newItems[i] = buffer.items[(buffer.head + i) MOD buffer.cap]
    buffer.items = newItems
    buffer.head = 0
    buffer.tail = buffer.len
    buffer.cap = newCap

Push

PUSH(buffer, item):
    IF buffer.len == buffer.cap
        GROW(buffer)
    buffer.items[buffer.tail] = item
    buffer.tail = (buffer.tail + 1) MOD buffer.cap
    buffer.len++

Pop

POP(buffer):
    IF buffer.len == 0
        RETURN nil, false
    item = buffer.items[buffer.head]
    buffer.head = (buffer.head + 1) MOD buffer.cap
    buffer.len--
    RETURN item, true

Peek

PEEK(buffer):
    IF buffer.len == 0
        RETURN nil, false
    RETURN buffer.items[buffer.head], true