1. Introduction

A Circular Buffer is a fixed-size data structure that uses a single, continuous block of memory. It appears to be “circular” because when it’s full and a subsequent write is performed, then it starts overwriting the oldest data. This structure is particularly useful in scenarios where we want a rolling window of last N items. In this post, we will walk through the implementation of a circular buffer in Java.

2. Program Steps

1. Initialize a generic array to store the buffer’s elements.

2. Define two pointers, start and end, to manage buffer’s bounds.

3. Implement the following operations:

– add(E item): Add an item to the buffer.

– get(): Get and remove the oldest item from the buffer.

– peek(): View the oldest item without removing it.

– isEmpty(): Check if the buffer is empty.

– isFull(): Check if the buffer is full.

3. Code Program

class CircularBuffer<E> {

    private final E[] buffer;
    private int start;
    private int end;
    private int size;
    private final int capacity;

    @SuppressWarnings("unchecked")
    public CircularBuffer(int capacity) {
        this.buffer = (E[]) new Object[capacity];
        this.capacity = capacity;
        this.size = 0;
        this.start = 0;
        this.end = 0;
    }

    public void add(E item) {
        if (isFull()) {
            start = (start + 1) % capacity;
        }
        buffer[end] = item;
        end = (end + 1) % capacity;
        if (size < capacity) {
            size++;
        }
    }

    public E get() {
        if (isEmpty()) {
            throw new IllegalStateException("Buffer is empty");
        }
        E item = buffer[start];
        start = (start + 1) % capacity;
        size--;
        return item;
    }

    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Buffer is empty");
        }
        return buffer[start];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public static void main(String[] args) {
        CircularBuffer<Integer> buffer = new CircularBuffer<>(3);
        buffer.add(1);
        buffer.add(2);
        buffer.add(3);
        System.out.println("Peek: " + buffer.peek());
        buffer.add(4);
        System.out.println("Removed: " + buffer.get());
        System.out.println("Peek after remove: " + buffer.peek());
    }
}

Output:

Peek: 1
Removed: 2
Peek after remove: 3

4. Step By Step Explanation

1. We initialize the buffer array to store elements. We also have two pointers, start and end, that keep track of the oldest and newest elements respectively.

2. The add method adds an element at the end and then moves the end pointer. If the buffer is full, the start pointer also moves to the next position, effectively removing the oldest element.

3. The get method retrieves the oldest element from the buffer and then moves the start pointer.

4. The peek method returns the oldest element without removing it.

5. isEmpty checks if the buffer has no elements and isFull checks if the buffer is at its capacity.

6. In the main function, we create a buffer of capacity 3. We add three numbers, then peek the buffer. We add another number, which removes the oldest one, and then retrieve and peek again. This demonstrates the circular nature of the buffer.