Cutting In, and Keeping Only the Last 100: Deques and Ring Buffers

A paid mobile order jumps to the front of the line, a customer at the back gives up and leaves, and a log must keep only its last 100 lines out of a million. Find the line that's cheap at both ends, and the fixed circle of slots that never moves or grows.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Use a deque to add and remove at both ends in O(1)
  • Trace a ring buffer as its front and back indexes wrap around a fixed array
  • Choose a stack, a queue, a deque or a ring buffer for a job, and say why

Key takeaways

  • A deque (double-ended queue) adds and removes at both ends in O(1): it can act as a stack, a queue, or both.
  • A ring buffer keeps a queue in a fixed number of slots arranged in a circle: the back is (front + count) % capacity, and both indexes wrap around.
  • A ring buffer never moves items and never grows, so it suits a fixed-size buffer such as the last 100 log lines or audio waiting to play.
  • A full ring buffer either refuses new items, like a keyboard buffer, or overwrites the oldest, like a log of the last 100 lines.
  • Trimming a list from the front moves every line on every add, and never trimming keeps everything; the circle does neither.

Before this: First Come, First Served at Rush Hour: Queues. A queue joins at the back and serves from the front, and does nothing else.

Two new jobs arrive at the coffee shop, and the queue can't do either. The first is about the line bending its rules: a mobile order that's already paid for goes to the front, and a customer at the back who gives up leaves the line. The second is about room: the order screen keeps a log for when something goes wrong, support only ever reads the last 100 lines, and a busy day writes a million. This lesson takes them one at a time.

Cutting in, and leaving from the back

What would you try? The queue from the last lesson only adds at the back, so it can't put the paid order first. A list can, with an insert at index 0, but that moves the whole line: O(n) for each cut-in. Or keep a second queue just for paid orders and always serve it first: that works for exactly two levels, and still lets nobody leave from the back.

The question that leads to it: which places does the line touch now? Both ends, both ways: join at the back or the front, leave from the front or the back. What would need to be cheap at all four? A linked list with a head, a tail and prev references already is: Reaching the Last Song, and Going Back One: Doubly Linked Lists made every one of those one step.

That line has a name: a deque (said "deck"; short for double-ended queue). It adds and removes at both ends, all in O(1). Use only one end and it's a stack; add at one end and remove at the other and it's a queue. That's why Java's documentation recommends ArrayDeque for both jobs, and why Python's collections.deque is its queue.

LinkedList<string> line = new LinkedList<string>();
line.AddLast("cold brew");
line.AddLast("chai tea");
line.AddLast("mocha");
Console.WriteLine("Line: " + string.Join(", ", line));

line.AddFirst("espresso");
Console.WriteLine("Mobile order to the front: " + string.Join(", ", line));

string left = line.Last!.Value;
line.RemoveLast();
Console.WriteLine("Customer at the back leaves: " + left);

string served = line.First!.Value;
line.RemoveFirst();
Console.WriteLine("Served from the front: " + served);
Console.WriteLine("Line: " + string.Join(", ", line));
Line: cold brew, chai tea, mocha
Mobile order to the front: espresso, cold brew, chai tea, mocha
Customer at the back leaves: mocha
Served from the front: espresso
Line: cold brew, chai tea
void main() {
    ArrayDeque<String> line = new ArrayDeque<>();
    line.addLast("cold brew");
    line.addLast("chai tea");
    line.addLast("mocha");
    IO.println("Line: " + String.join(", ", line));

    line.addFirst("espresso");
    IO.println("Mobile order to the front: " + String.join(", ", line));

    IO.println("Customer at the back leaves: " + line.removeLast());
    IO.println("Served from the front: " + line.removeFirst());
    IO.println("Line: " + String.join(", ", line));
}
Line: cold brew, chai tea, mocha
Mobile order to the front: espresso, cold brew, chai tea, mocha
Customer at the back leaves: mocha
Served from the front: espresso
Line: cold brew, chai tea
from collections import deque

line = deque()
line.append("cold brew")
line.append("chai tea")
line.append("mocha")
print("Line: " + ", ".join(line))

line.appendleft("espresso")
print("Mobile order to the front: " + ", ".join(line))

print("Customer at the back leaves: " + line.pop())
print("Served from the front: " + line.popleft())
print("Line: " + ", ".join(line))
Line: cold brew, chai tea, mocha
Mobile order to the front: espresso, cold brew, chai tea, mocha
Customer at the back leaves: mocha
Served from the front: espresso
Line: cold brew, chai tea
const line = [];
line.push("cold brew");
line.push("chai tea");
line.push("mocha");
console.log(`Line: ${line.join(", ")}`);

line.unshift("espresso");
console.log(`Mobile order to the front: ${line.join(", ")}`);

console.log(`Customer at the back leaves: ${line.pop()}`);
console.log(`Served from the front: ${line.shift()}`);
console.log(`Line: ${line.join(", ")}`);
Line: cold brew, chai tea, mocha
Mobile order to the front: espresso, cold brew, chai tea, mocha
Customer at the back leaves: mocha
Served from the front: espresso
Line: cold brew, chai tea
const line: string[] = [];
line.push("cold brew");
line.push("chai tea");
line.push("mocha");
console.log(`Line: ${line.join(", ")}`);

line.unshift("espresso");
console.log(`Mobile order to the front: ${line.join(", ")}`);

console.log(`Customer at the back leaves: ${line.pop()}`);
console.log(`Served from the front: ${line.shift()}`);
console.log(`Line: ${line.join(", ")}`);
Line: cold brew, chai tea, mocha
Mobile order to the front: espresso, cold brew, chai tea, mocha
Customer at the back leaves: mocha
Served from the front: espresso
Line: cold brew, chai tea

Each language reaches for something different here. C# has no class named deque; its LinkedList<T> is a doubly linked list with O(1) at both ends, and First! and Last! say "this node is there" (the line isn't empty). Java's ArrayDeque and Python's deque are true deques. JavaScript and TypeScript have none built in: unshift and shift work at the front of an array, but they move every item, O(n), so for a long line you'd write your own deque, as a doubly linked list or a ring buffer.

Keeping only the last 100

Now the log. Every event the order screen handles adds a line: "09:02 order 17 placed". Support only ever needs the last 100.

Trim the oldest, then append. Once the log holds 100 lines, remove the first one before adding each new line at the end. That's the pop(0) from Why Does This Loop Take Seconds? Your Language's List: every new line moves the 99 lines behind the oldest one. A million lines cost about 99 million moves.

Never trim. Adding is O(1), and the last 100 are always at the end. But the log holds a million lines to show 100, and tomorrow it holds two million.

A front index, as in the queue lesson. Add at the end, and move a "first line to show" number forward instead of removing anything. No moves at all. But the dead slots before the front pile up forever: the same memory as never trimming.

What we tried Add a line Memory for a million lines Where it breaks
Trim with pop(0), then append O(n): 99 lines move 100 lines 99 million moves
Never trim O(1) a million lines memory
A front index O(1) a million slots, most of them dead memory

The questions that lead to it: the front-index try was almost right. It never moves anything; it only wastes the slots before the front. Those slots are free. What if the back could reuse them? Keep exactly 100 slots, and when the back reaches slot 99, carry on at slot 0, writing over the oldest line, which nobody needs any more. How do you say "after slot 99 comes slot 0" in code? With the remainder after dividing by the number of slots, written % and read "modulo" (or "mod"): 100 % 100 is 0, so slot 99 + 1 wraps to slot 0.

How it got its name

This idea was so useful that it got a name: a ring buffer (also called a circular buffer). It's a queue kept in a plain array of fixed size, with two numbers:

  • front: the slot of the oldest item;
  • count: how many items are in it.

The back, where the next item goes, is (front + count) % capacity. Nothing ever scoots over, the slots are reused, and the memory never grows.

You know the everyday version: a small round counter with 4 numbered stools at a busy coffee bar. Customers sit in order around the circle and leave in the order they sat down. When stool 3 is taken and stool 0 is free again, the next customer sits at stool 0: the line wraps around.

A small round coffee counter seen from above, with four stools around it numbered 0, 1, 2 and 3 clockwise. Customers sit on all four stools. The customer on stool 2, who sat down first, is getting up to leave, and a new customer waits beside stool 2 to take it. A curved arrow runs around the counter from stool 3 to stool 0, labeled "after 3 comes 0"

This LastLines keeps the last 4 lines of a log (4, so you can follow every slot; a real one would keep 100). When it's full, a new line overwrites the oldest one, and the front moves on.

LastLines log = new LastLines(4);
string[] lines = { "09:00 app started", "09:01 user signed in", "09:02 order 17 placed", "09:03 order 17 paid", "09:04 order 18 placed", "09:05 user signed out" };
foreach (string line in lines)
{
    log.Add(line);
}
Console.WriteLine("Last 4: " + string.Join(" | ", log.Lines()));

class LastLines
{
    private string[] slots;
    private int front = 0;
    private int count = 0;

    public LastLines(int capacity)
    {
        slots = new string[capacity];
    }

    public void Add(string line)
    {
        int back = (front + count) % slots.Length;
        slots[back] = line;
        if (count < slots.Length)
        {
            count++;
        }
        else
        {
            front = (front + 1) % slots.Length;
        }
        Console.WriteLine(line + " -> slot " + back);
    }

    public List<string> Lines()
    {
        List<string> oldestFirst = new List<string>();
        for (int i = 0; i < count; i++)
        {
            oldestFirst.Add(slots[(front + i) % slots.Length]);
        }
        return oldestFirst;
    }
}
09:00 app started -> slot 0
09:01 user signed in -> slot 1
09:02 order 17 placed -> slot 2
09:03 order 17 paid -> slot 3
09:04 order 18 placed -> slot 0
09:05 user signed out -> slot 1
Last 4: 09:02 order 17 placed | 09:03 order 17 paid | 09:04 order 18 placed | 09:05 user signed out
class LastLines {
    private String[] slots;
    private int front = 0;
    private int count = 0;

    LastLines(int capacity) {
        slots = new String[capacity];
    }

    void add(String line) {
        int back = (front + count) % slots.length;
        slots[back] = line;
        if (count < slots.length) {
            count++;
        } else {
            front = (front + 1) % slots.length;
        }
        IO.println(line + " -> slot " + back);
    }

    List<String> lines() {
        List<String> oldestFirst = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            oldestFirst.add(slots[(front + i) % slots.length]);
        }
        return oldestFirst;
    }
}

void main() {
    LastLines log = new LastLines(4);
    String[] lines = {"09:00 app started", "09:01 user signed in", "09:02 order 17 placed", "09:03 order 17 paid", "09:04 order 18 placed", "09:05 user signed out"};
    for (String line : lines) {
        log.add(line);
    }
    IO.println("Last 4: " + String.join(" | ", log.lines()));
}
09:00 app started -> slot 0
09:01 user signed in -> slot 1
09:02 order 17 placed -> slot 2
09:03 order 17 paid -> slot 3
09:04 order 18 placed -> slot 0
09:05 user signed out -> slot 1
Last 4: 09:02 order 17 placed | 09:03 order 17 paid | 09:04 order 18 placed | 09:05 user signed out
class LastLines:
    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.front = 0
        self.count = 0

    def add(self, line):
        back = (self.front + self.count) % len(self.slots)
        self.slots[back] = line
        if self.count < len(self.slots):
            self.count += 1
        else:
            self.front = (self.front + 1) % len(self.slots)
        print(f"{line} -> slot {back}")

    def lines(self):
        return [self.slots[(self.front + i) % len(self.slots)] for i in range(self.count)]


log = LastLines(4)
for line in ["09:00 app started", "09:01 user signed in", "09:02 order 17 placed", "09:03 order 17 paid", "09:04 order 18 placed", "09:05 user signed out"]:
    log.add(line)
print("Last 4: " + " | ".join(log.lines()))
09:00 app started -> slot 0
09:01 user signed in -> slot 1
09:02 order 17 placed -> slot 2
09:03 order 17 paid -> slot 3
09:04 order 18 placed -> slot 0
09:05 user signed out -> slot 1
Last 4: 09:02 order 17 placed | 09:03 order 17 paid | 09:04 order 18 placed | 09:05 user signed out
class LastLines {
  constructor(capacity) {
    this.slots = new Array(capacity);
    this.front = 0;
    this.count = 0;
  }

  add(line) {
    const back = (this.front + this.count) % this.slots.length;
    this.slots[back] = line;
    if (this.count < this.slots.length) {
      this.count++;
    } else {
      this.front = (this.front + 1) % this.slots.length;
    }
    console.log(`${line} -> slot ${back}`);
  }

  lines() {
    const oldestFirst = [];
    for (let i = 0; i < this.count; i++) {
      oldestFirst.push(this.slots[(this.front + i) % this.slots.length]);
    }
    return oldestFirst;
  }
}

const log = new LastLines(4);
for (const line of ["09:00 app started", "09:01 user signed in", "09:02 order 17 placed", "09:03 order 17 paid", "09:04 order 18 placed", "09:05 user signed out"]) {
  log.add(line);
}
console.log(`Last 4: ${log.lines().join(" | ")}`);
09:00 app started -> slot 0
09:01 user signed in -> slot 1
09:02 order 17 placed -> slot 2
09:03 order 17 paid -> slot 3
09:04 order 18 placed -> slot 0
09:05 user signed out -> slot 1
Last 4: 09:02 order 17 placed | 09:03 order 17 paid | 09:04 order 18 placed | 09:05 user signed out
class LastLines {
  private slots: string[];
  private front = 0;
  private count = 0;

  constructor(capacity: number) {
    this.slots = new Array<string>(capacity);
  }

  add(line: string): void {
    const back = (this.front + this.count) % this.slots.length;
    this.slots[back] = line;
    if (this.count < this.slots.length) {
      this.count++;
    } else {
      this.front = (this.front + 1) % this.slots.length;
    }
    console.log(`${line} -> slot ${back}`);
  }

  lines(): string[] {
    const oldestFirst: string[] = [];
    for (let i = 0; i < this.count; i++) {
      oldestFirst.push(this.slots[(this.front + i) % this.slots.length]);
    }
    return oldestFirst;
  }
}

const log = new LastLines(4);
for (const line of ["09:00 app started", "09:01 user signed in", "09:02 order 17 placed", "09:03 order 17 paid", "09:04 order 18 placed", "09:05 user signed out"]) {
  log.add(line);
}
console.log(`Last 4: ${log.lines().join(" | ")}`);
09:00 app started -> slot 0
09:01 user signed in -> slot 1
09:02 order 17 placed -> slot 2
09:03 order 17 paid -> slot 3
09:04 order 18 placed -> slot 0
09:05 user signed out -> slot 1
Last 4: 09:02 order 17 placed | 09:03 order 17 paid | 09:04 order 18 placed | 09:05 user signed out

Follow the slots: the first four lines fill slots 0 to 3. The fifth line finds all 4 slots full, so it goes to (0 + 4) % 4 = slot 0, over the oldest line, and the front moves to slot 1. The sixth goes to (1 + 4) % 4 = slot 1, and the front moves to slot 2. Reading from the front, slot 2, 3, 0 and then 1, gives the last four lines, oldest first. A million lines would cost a million writes and no moves, in 100 slots.

A real ring buffer decides what "full" means for its job: a log overwrites the oldest line, as this one does, while a keyboard buffer refuses new keys until the program catches up. Python's deque(maxlen=100) is a ring buffer of the last 100 already, and Java's ArrayDeque is a ring buffer inside; in C# and JavaScript you write the few lines above.

Try it. Add two more lines, "09:06 app stopped" and "09:07 app started", and predict which slots they go to and which four lines are left before you run it.

The cost cards

Operation Deque Ring buffer
Add at the back O(1) O(1), refusing or overwriting when full
Remove from the front O(1) O(1)
Add at the front, remove from the back O(1) not used: it's a queue
Memory grows as needed fixed, set when it's made

Check yourself

2 questions to try on the lesson page.

So what

A deque is the all-purpose line: stack, queue, or a bit of both. A ring buffer is the line that never grows and never moves anything, which is why it sits inside keyboards, network cards, audio players and every "last 100 lines" log. Knowing both lets you pick the line that fits the job.

Key terms

Cheat sheets