cf.completefrontend
STACKS & QUEUES · CORE

Ring buffer

A fixed-size queue stored in an array whose end wraps around to the start, so no item ever has to move.

Time O(1) per operationSpace O(capacity)4 practice problemsStep-through picture

The idea

A ring buffer, also called a circular buffer, is a queue that lives in an array of fixed size. Instead of moving items when the front one leaves, it moves an index: head points at the oldest item, and new items go into the slot after the newest one.

When an index runs off the end of the array, it wraps around to slot 0, using % capacity. The array behaves like a circle with no first or last slot. As long as the buffer isn't full, there is always a free slot after the newest item.

Because the memory is set aside once and nothing ever moves, every push and remove is O(1) with no garbage to collect. That is why ring buffers are used for logs, audio, and network data that flow continuously.

An everyday example

A sushi conveyor belt

A sushi bar has a round conveyor belt with a fixed number of plate spots. The chef puts new plates in the next free spot, and customers take the oldest plate as it reaches them. The belt never gets longer and nothing is shuffled along it; it just keeps going round. When every spot holds a plate, the chef has to wait.

How the example maps to the code
In the exampleIn the code
The plate spots on the beltthis.items, a fixed-size array
The oldest platethis.items[this.head]
The next free spot(this.head + this.size) % this.capacity
Going past the last spot back to the first% this.capacity
Every spot is fullthis.size === this.capacity

From the slow way to ring buffer

  1. Start with the obvious queue: an array with push and shift. shift moves every remaining item, so each dequeue is O(n). The usual fix keeps a head index and moves it instead, which makes dequeue O(1), but the served slots before head are never reused, so the array grows forever on a stream that never stops.
  2. Those served slots are free space. If the queue never holds more than capacity items at once, an array of exactly capacity slots is enough, as long as new items can go into slots that earlier items left. When the back of the queue reaches the last slot, the next item should go into slot 0 again.
  3. Wrapping is one operation: x % capacity is the remainder after dividing by capacity, so it always lands between 0 and capacity - 1. Keep head, the slot of the oldest item, and size, how many items are stored. The free slot after the newest item is (head + size) % capacity, and after a removal head moves to (head + 1) % capacity.
  4. Tracking size also settles the one hard question: is the buffer empty or full? If size === 0 there's nothing to remove, and if size === capacity there's no room. The array is created once and nothing in it ever moves. That array with wrapping indexes is a ring buffer.

How it works

  1. Create items with capacity empty slots, and set head = 0 and size = 0.
  2. To push, return false if size === capacity. Otherwise compute the free slot tail = (head + size) % capacity.
  3. Store the value at items[tail] and add one to size.
  4. To remove the oldest item, return null if size is 0. Otherwise read items[head] and clear the slot.
  5. Move head forward with wrap-around: head = (head + 1) % capacity, and subtract one from size.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class RingBuffer {
  2. constructor(capacity) {
  3. this.items = new Array(capacity).fill(null);
  4. this.capacity = capacity;
  5. this.head = 0;
  6. this.size = 0;
  7. }
  9. push(value) {
  10. if (this.size === this.capacity) return false;
  11. const tail = (this.head + this.size) % this.capacity;
  12. this.items[tail] = value;
  13. this.size++;
  14. return true;
  15. }
  17. shift() {
  18. if (this.size === 0) return null;
  19. const value = this.items[this.head];
  20. this.items[this.head] = null;
  21. this.head = (this.head + 1) % this.capacity;
  22. this.size--;
  23. return value;
  24. }
  25. }

How fast it is

TimeO(1) per operation
Extra memoryO(capacity)

Each operation does a fixed amount of arithmetic and one array access. The array never grows, so memory depends only on capacity.

  • Best caseO(1)

    A push into a buffer with room, or a shift from a buffer with items: a little arithmetic and one array write.

  • Average caseO(1)

    Any mix of calls, including ones where head or the free slot wraps from the last slot to slot 0.

  • Worst caseO(1)

    Even a push into a full buffer is one comparison that returns false. No call ever loops or moves items.

Common mistakes

  • Keeping separate head and tail indexes without a size: when they are equal you can't tell an empty buffer from a full one. Track size, or always leave one slot empty.
  • Forgetting % capacity in one place, so an index runs past the end of the array.
  • Using array.shift() or splice on the buffer, which moves items and loses the whole point.
  • Reading the items in array order from 0 instead of from head, which mixes the newest and oldest items after a wrap.

When to use it

Look for these clues in a problem:

  • The task gives a fixed capacity, such as "keep the last 100 log lines" or "a buffer of size k".
  • Data flows continuously and only the newest k items matter.
  • You need a queue with O(1) operations and no memory growth.
  • The words circular, wrap around, or moving average over the last k values appear.

Check yourself

Answer each one in your head first, then open it.

Why track size instead of only head and tail indexes?

When the buffer is empty and when it is full, head and tail point to the same slot. size tells the two apart without wasting a slot.

With capacity = 5, head = 3, and size = 4, which slot does the next push write?

Slot 2, since (3 + 4) % 5 = 2. The items sit in slots 3, 4, 0, and 1.

Why is reading the array from index 0 the wrong way to list the items?

After a wrap, the oldest item may be in the middle of the array and newer items at slot 0. The order starts at head, as the trace showed when 44 sat in slot 0 but came out last.

How much memory does the buffer use after a million pushes and shifts?

The same as at the start: capacity slots. The array is never resized, so only the values in it change.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The class keeps one rule after every call: size is between 0 and capacity, the stored items, oldest first, sit in slots head, head + 1, and so on for size slots, each taken % capacity, and every other slot is null. At the start size is 0 and every slot is null, so the rule holds.

push runs only when size < capacity, so at least one slot is free, and the first one after the newest item is (head + size) % capacity. Writing there and adding one to size extends the run by one at its end. shift runs only when size > 0; it reads and clears slot head, moves head one slot forward with wrap-around, and subtracts one from size, which drops the run's first item and keeps the rest in order.

So the oldest item is always at head and the next free slot is always right after the newest, wherever the run wraps. Every index passes through % capacity, so no index ever leaves the array, and each method does a fixed amount of work: O(1).

Going deeper

3 more ideas

Why the modulo makes a circle

x % capacity is the remainder after dividing by capacity, so it is always between 0 and capacity - 1. Index capacity becomes 0, capacity + 1 becomes 1, and so on. The items sit in slots head, head + 1, ... up to size slots, each taken % capacity, so they may wrap past the end and continue at the start.

Cost

Push and remove do a few arithmetic steps and one array write, so both are O(1). The array is created once with capacity slots, so memory is O(capacity) no matter how many items pass through.

Overwriting instead of refusing

Logs and metrics usually prefer to keep the newest data. In that version, a push to a full buffer writes into slot head (the oldest item) and moves head forward by one, so the oldest item is dropped and size stays at capacity.

Work it by hand

Every step in a table, with why

Use a buffer of 3 slots: fill it, wrap round to slot 0, get refused when full, then empty it.

capacity = 3; push(11), push(22), shift(), push(33), push(44), push(55), shift(), shift(), shift(), shift()

StepCallReturnsitemsheadsizeWhy
1push(11)true[11, null, null]01tail = (0 + 0) % 3 = 0, so 11 goes into slot 0.
2push(22)true[11, 22, null]02tail = (0 + 1) % 3 = 1.
3shift()11[null, 22, null]11The oldest item is at head = 0. Its slot is cleared and head moves to 1.
4push(33)true[null, 22, 33]12tail = (1 + 1) % 3 = 2, the last slot.
5push(44)true[44, 22, 33]13tail = (1 + 2) % 3 = 0: the index wraps round and 44 reuses the slot 11 left.
6push(55)false[44, 22, 33]13size === capacity, so the push is refused and nothing changes.
7shift()22[44, null, 33]22The oldest item is in slot 1, not slot 0. Order comes from head, not from array position.
8shift()33[44, null, null]01head = (2 + 1) % 3 = 0: head wraps round too.
9shift()44[null, null, null]10The newest item, stored in slot 0, comes out last, as a queue should.
10shift()null[null, null, null]10size === 0, so there's nothing to remove.

The items came out as 11, 22, 33, 44, the order they went in, while the array never grew past 3 slots. 55 was refused because the buffer was full at that moment.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Ring bufferO(1)O(capacity)You know the most items that can wait at once, or only the newest capacity items matter, and memory must not grow.
Array with shiftO(n)O(n)Tiny queues where the clearest code matters most. Each dequeue moves all remaining items.
Array with a head indexO(1)O(n)The queue has no size limit and runs for a short time, so the served slots never get large.
Linked-list queueO(1)O(n)The queue has no size limit and must free served items, at the cost of one node object per item.

Extra memory: O(capacity): the array is created once with capacity slots, however many items pass through it over time.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Ring buffer and the other approaches, on a scale where each line up is 10 times more steps.
  • Ring buffer, Array with a head index, Linked-list queue O(1)
  • Array with shift O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Ring buffer111
Array with shift101,0001 million
Array with a head index111
Linked-list queue111

Inputs that need care

5 tricky inputs
push into a full buffer
It returns false and changes nothing, as push(55) did in the trace. The caller must decide to drop the value, wait, or use the overwriting version.
shift from an empty buffer
It returns null without touching head.
Pushing null as a real value
shift would return null, which looks the same as "empty". Check size instead of the return value, or return an undefined marker that can't be stored.
capacity = 1
(head + size) % 1 is always 0, so the single slot is reused for every item. It works as a one-item queue.
capacity = 0
size === capacity is true at once, so every push returns false and every shift returns null. The % 0 line is never reached, so it never produces NaN.

Variations and follow-ups

Twists interviewers add

Overwrite the oldest when full

Logs and metrics want the newest data. When size === capacity, write the new value into slot head and move head one slot forward. The oldest item is dropped and size stays at capacity.

Two indexes and one empty slot

Some versions keep head and tail and no size. Then head === tail must mean empty, so the buffer is called full when (tail + 1) % capacity === head, leaving one slot unused.

Power-of-two capacity

If capacity is a power of two, such as 1,024, x % capacity equals x & (capacity - 1), a single bit operation. Audio and network code often picks such sizes for that reason.

Shared between threads

With one writer and one reader, such as an AudioWorklet and the main thread, the slots can live in a SharedArrayBuffer, and each side moves only its own index with Atomics. Neither side ever allocates memory while data flows.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "fixed size", "circular", "keep the last k", "moving average of the last k values", or "design a circular queue".
  • Explain the state in one sentence: "head is the oldest item's slot, size is how many items there are, and the free slot is (head + size) % capacity". Then say why you track size: with only two indexes, empty and full look the same.
  • Test by hand on a buffer of 3: fill it, remove one, then push twice so the index wraps to slot 0. Check the refused push and the order items come out.
  • Expect the follow-up "what if it should keep the newest data when full?". Overwrite slot head and move head forward, leaving size at capacity.

Where frontend code uses it

The same idea in real UI code
  • Error-reporting tools keep only the last few dozen user actions (breadcrumbs) before a crash; a ring buffer stores exactly the newest k without growing.
  • Audio code that passes samples between an AudioWorklet and the main thread commonly uses a ring buffer over a SharedArrayBuffer, so neither side allocates memory while sound plays.
  • FPS meters and performance overlays keep the last 60 or 120 frame times in a ring buffer to draw a rolling graph.

Related algorithms