Circular queue

Why it matters

Many real systems have a buffer of fixed size: the memory where a network card stores incoming packets, the place where a sound card holds the samples it is about to play, the log that keeps the last few hundred events of a server. Each of these needs a queue that never grows and never wastes space. The circular queue, also called a ring buffer, solves that problem with one simple idea: after the last slot, go back to the first. The idea is short, but it is the source of several classic bugs. This lesson builds the ring carefully, traces it step by step, and shows the mistakes that interviewers look for.

The problem with a plain array queue

Suppose you store a queue in an array of five slots. You keep two numbers: front, the index of the oldest item, and rear, the index of the next free slot. Pushing writes at rear and moves rear forward. Popping reads at front and moves front forward.

Now run a short sequence: push 1, 2, 3, then pop twice. The pops freed slots 0 and 1. Push 4 uses slot 3, and push 5 uses slot 4. A sixth push would need slot 5, which does not exist. The queue reports "full" even though two slots at the start of the array are empty. The space is there, but the plain queue cannot reach it, because rear only moves forward.

There are two standard fixes for a plain array, and both are poor. The first is to shift every remaining item one step left after each pop. That makes each pop cost O(n), which is slow for a busy buffer. The second is to copy the queue into a bigger array when it is full, which breaks the goal of a fixed size. A circular queue avoids both costs by making the array behave as if its last slot is connected to its first.

The idea: a ring

Think of a revolving sushi belt with five plate positions. A plate goes onto a position as it passes, and when it reaches the end of the visible area, it simply continues to position 0. The belt has no real end. The same five positions are used over and over.

In code, the wrap is done with the modulo operator %, which gives the remainder after division. For a ring of capacity cap, the next index after i is (i + 1) % cap. With cap equal to 5, the index after 4 is (4 + 1) % 5 = 0. The index after 2 is (2 + 1) % 5 = 3, which is the ordinary next slot.

The rear slot, where a new item goes, is found from the front and the count of items: (front + count) % cap. The count is the number of items in the queue. If the front is at slot 3 and there are 4 items, the items occupy slots 3, 4, 0 and 1, and the new item goes to (3 + 4) % 5 = 2. Every push and pop changes only one index, so each operation is O(1), and no item is ever moved.

Step through the animation below. Watch the front index chase the rear index around the ring, and watch the newest item land in a slot that an earlier pop has freed.

The diagram below shows the same idea as a fixed row of slots, with the front and the rear marked.

A ring of five slots holding three items, with the front marker on the oldest item and the rear marker on the next free slot, and a note that the rear wraps back to slot 0

The full and empty problem

The ring has one subtle flaw. If you track only front and rear, the two cases look the same. When the queue is empty, front equals rear. When it is full after wrapping, front also equals rear. The indexes cannot tell you which case you are in.

There are two standard ways to fix this, and both are common in interviews and in real code. The table compares them.

The first method is simpler to read, and it is the one the first program uses. The second method uses only two indexes and never needs a count, which can be useful when the storage is shared between threads or devices. It costs one slot. A buffer of capacity 4 holds only 3 items, and the second program shows that effect.

A ring with a count

The first program implements the ring with a count. It keeps the oldest index in front and the number of items in count. The rear slot is computed as (front + count) % cap, which means the program never stores rear at all. The class also owns its memory with new[], so the destructor frees it with delete[].

Output:

1110
1
1
2
5

Here is the trace. The capacity is 3, so the array has slots 0, 1 and 2. Each row shows the slots after the step, with F marking the front item and . for a free slot.

Step 10 is the payoff. After step 7 the items in order are 2 (slot 1), 3 (slot 2) and 5 (slot 0), because the write wrapped to the start of the array. The two pops in step 9 remove 2 and 3, moving the front from slot 1 to slot 2 and then to slot 0. The one item left is 5 in slot 0, so peek prints 5.

The trace shows the most important point of the ring. Step 7 writes into slot 0, which is the first slot in the array, because the item lands after the last item in the ring. The wrap happened without any copying.

Every operation here is O(1). The space is fixed at O(k) for capacity k, and nothing is shifted.

Copying warning: raw arrays need care

The class above owns a block of memory from new[]. That creates a trap. If someone copies the object, both copies point to the same block. When each copy is destroyed, each destructor calls delete[] on the same address. The second call frees memory that is already free, which is a serious error.

Here is a tiny program that shows the trap. It has only a constructor and a destructor, and it makes a copy. Its real output, shortened, is a crash with exit code 134:

free(): double free detected in tcache 2

The message says the library found the same block freed twice. It is a sign of a copy bug, not a bug in the array logic itself. You have three ways to avoid it. You can delete the copy operations, so the compiler refuses to copy the object. You can write a copy constructor that allocates a new block. Or you can avoid manual memory and use std::vector<int> for the storage, which copies itself correctly. The next program uses the vector approach.

Leaving one slot unused

The second program uses the other method. It stores front and rear, and it never keeps a count. The queue is full when advancing rear would make it equal to front. That means one slot always stays empty, so a ring of 4 slots holds 3 items.

Output:

ok
ok
ok
full
1
2
3

The trace is short. Both indexes start at 0, which means empty. Push 1 writes slot 0 and moves tail to 1. Push 2 writes slot 1 and moves tail to 2. Push 3 writes slot 2 and moves tail to 3. Push 4 checks (3 + 1) % 4 = 0, which equals head, so the queue is full and the push is refused. Then the three pops return 1, 2 and 3 in order, and head reaches tail, so the loop stops.

The code uses vector<int> and the % a.size() expression. The size() function returns an unsigned type, but here the value is always positive, so the modulo works. Be careful with negative numbers: in C++, % of a negative number is negative, so a formula such as (rear - 1) % cap can produce a negative index when rear is 0. The safe form adds cap before taking the remainder. The third program and the rear function below use that trick.

A moving average over the last k values

Ring buffers are used for streams, where the newest values replace the oldest ones. Here the buffer does not reject new values. It overwrites the oldest slot instead. The program below keeps the average of the last k values as numbers arrive.

The idea is to keep a running sum of the values in the ring. When the ring is full, the value about to be overwritten leaves the sum before the new one enters. This gives each update in O(1) time, with no loop over the window.

Input box:

3 5
10 20 30 40 50

Output:

10.00
15.00
20.00
30.00
40.00

Check the fourth line, which is the first time the ring is full. Before the fourth value, the ring holds 10, 20, 30 and sum is 60. The next slot to overwrite is slot 0, which holds 10. The code subtracts 10, making sum 50, then writes 40 into slot 0 and adds it, making sum 90. The window is now 20, 30, 40, and the average is 90 divided by 3, which is 30.00. The fifth line follows the same pattern. The next slot to overwrite is slot 1, which holds 20, so 20 leaves the window and 50 enters. The window is now 30, 40, 50, and the average is 40.00.

The static_cast<double> converts the integer sum to a decimal before dividing. Without it, sum / filled would divide two integers and throw away the fraction. The setprecision(2) call from the iomanip header prints two decimal places.

Reading the rear

A queue often needs to read its newest item as well as its oldest. In a ring, the newest item sits just before the rear slot, at index (front + count - 1 + cap) % cap. The + cap keeps the value positive when front + count - 1 is zero. The next program adds a rear function and prints the state after a short sequence of operations.

Output:

20 2
40 3
0

The first line is simple. Two items are in the ring, and the newest is 20. The pop removes 10, so front moves to slot 1. Pushing 30 writes slot 2, and pushing 40 writes (1 + 2) % 3 = 0, which is slot 0. The rear is now (1 + 3 - 1 + 3) % 3 = 0, which holds 40. The ring is full, so the last push(50) returns false, and the program prints 0.

The cout << q.push(50) line prints 0 because a bool prints as 1 or 0 unless you set boolalpha. That is a small detail, but it explains a common surprise when people print true and false results.

Debugging walkthrough: the ring that refuses its first item

The most common bug in a ring is the one this lesson warned about: using front == rear for both empty and full. Here is a small class that does exactly that. Predict the output before you run it.

Output:

rejected
empty

The ring is brand new and holds nothing, yet the first push is refused. The reason is that full() returns true when front == rear, and a new ring has both at 0. So the full() test is true for an empty ring. The fix is one of the two methods from this lesson: keep a count, so full() checks count == cap, or leave one slot unused, so full() checks (rear + 1) % cap == front. Notice that the debug output shows the state directly. When a check looks wrong, print the two indexes and compare them with what you expected.

Tracing the leave-one-slot ring step by step

The leave-one-slot method is harder to picture than the count method, because the items and the empty slot move together. Trace the second program on the same operations, with four slots. Slots are written as 1 2 3 ., where a dot is an empty slot. head is the oldest item, and tail is the next free slot.

Two things are worth noticing. First, the full test at step 4 is (tail + 1) % cap == head, not tail == head. If the test used tail == head, step 1 would already look full, which is the bug from the debugging walkthrough. Second, the item values stay in their slots after a pop. Step 5 does not erase the 1. It only moves head past it. A pop never needs to clear the slot, because the indexes say which slots are live.

The table also explains the lost slot. Four slots hold three items, because at step 4 the tail is one slot behind the head and must stop there. If the queue were allowed to fill slot 3 and tail reached head, the empty test and the full test would again look the same. The lost slot is the price of using two indexes alone.

Choosing the capacity

A capacity is a design decision with real costs. A buffer that is too small drops data when the producer is faster than the consumer. A buffer that is too large wastes memory, and in some systems it also delays the moment when a problem becomes visible. For a logging ring, a capacity of a few thousand records may be right. For a network card, the size is set by the hardware.

For a single program, pick the capacity from the problem statement, and write it as a named constant, not as a number scattered through the code. Then test the boundary. Fill the ring exactly to its capacity, then try one more push, and check that the extra push fails. Many off-by-one bugs appear only at that boundary.

Some people choose a capacity that is a power of two, such as 8, 16 or 1024. The reason is speed. The remainder % cap is a division, which is slow compared with other operations. When the capacity is a power of two, the same wrap can be done with a bit mask. For a capacity of 8, the mask is 7, written in binary as 111, and index & 7 gives the same result as index % 8 for any non-negative index. When the index is unsigned and the divisor is a constant, many compilers already make this replacement for you. Treat it as an optimisation, not a requirement. A correct ring with any capacity is still correct.

Testing a ring

A ring has many small rules, so it needs a test plan. Write the tests as a list of operations and expected results, then run them in order. Here is a plan that covers the common failures.

• Push into an empty ring, then pop. The value must come back, and the ring must be empty again.
• Fill the ring to its capacity. The next push must fail, and nothing must be overwritten.
• Pop one item from a full ring, then push one. The new item must go into the freed slot.
• Pop from an empty ring. The function must refuse and must not move the front.
• Go around the ring several times. Run at least three full laps of pushes and pops, and check the values in order.
• For the moving average, run a window larger than the number of values. The divisor must be the count of real values.

The strongest test is a comparison with a simple reference. Write the same queue with std::deque, which is easy to trust, and run both on the same random sequence of pushes and pops. Print the first operation where the results differ. This is the same comparison method used for the brute-force checks in the previous lesson, and it finds the wrap-around bugs that hand-written tests miss.

Two threads and a ring

Rings are often used between two parts of a program that run at the same time. One thread writes new items at the rear, and another reads items from the front. This is a common and valuable design, because neither side has to wait for a lock on every operation.

It is also a place where the simple count method breaks. If both threads change count, they can overwrite each other's update. The two-index method is safer for one writer and one reader, because each thread changes only its own index. Even so, the two threads must agree on when a write is visible to the other side, and that requires memory-ordering rules that are beyond this module. For now, remember the rule: a shared counter needs locking, and a single writer with a single reader is the easiest safe case.

Watching the ring at the boundary

Many ring bugs appear only when the ring is exactly full or exactly empty, so test the operation that comes right after each of those states. Take the count version with capacity 3, holding 1, 2 and 3. The ring is full, with front at 0 and count at 3. A pop moves front to 1 and lowers the count to 2. The next push writes to (1 + 2) % 3, which is slot 0. That is the slot the pop just freed. A push after that finds count equal to 3 and returns false.

The same reasoning applies to the empty boundary. After the last pop, count is 0 and front points at a slot that may still hold an old value. A peek on an empty ring must not return that old value, which is why the programs in this lesson test empty() before reading. The old value is still in memory, and nothing clears it, so the count is the only safe signal.

When you test a boundary, write down the three numbers that define the state, front, count and cap, before and after the operation. Most mistakes are visible as a wrong number in that list. This habit is faster than reading the code again and again.

Questions about the moving average

Students often ask three questions about the moving average program. The first is why the first few averages are not divided by k. The answer is that the window is not full yet, so the average is taken over the values that exist. The variable filled counts those values, and the program divides by it. Dividing by k would make the early averages too small, as if the missing values were zeros.

The second question is whether filled can ever be zero when the program divides. It cannot. The division happens after the value is read and filled is increased, so filled is at least 1 on every line.

The third question is whether a window of size 1 works. It does. The ring has one slot, and each new value overwrites it. The sum is always the newest value, and the average is that value. This is a useful check, because it shows that the ring logic handles the smallest case without a special branch.

Common mistakes

Mistake 1: forgetting the modulo. Writing rear + 1 without % cap steps off the end of the array. The program may write into memory it does not own, which is undefined behaviour and can crash much later.

Mistake 2: using front == rear for both states. This is the bug above. Choose a method and apply it to both the empty test and the full test.

Mistake 3: computing the rear slot without the modulo. Writing a[front + count] instead of a[(front + count) % cap] gives an index past the end once the ring wraps.

Mistake 4: forgetting to decrement the count. If pop moves front but does not reduce count, the ring believes it is still full, and every later push fails.

Mistake 5: copying an object that owns a raw array. The double-free message shown earlier is the sign. Use vector, or delete the copy operations.

Mistake 6: negative modulo. For a negative value, % gives a negative result in C++, so (rear - 1) % cap can be negative. Add cap before taking the remainder.

Mistake 7: printing bools without thinking. cout << q.push(5) prints 1 or 0, not true or false. Set boolalpha if you want words.

Interview questions and what they test

Circular queues come up in interviews as a test of careful index arithmetic. Expect these questions:

• Design a circular queue with a fixed capacity. Name the two indexes, choose the full and empty method, and state the capacity you can use.
• Why does a circular queue not need to shift items? Because the front and rear indexes move, and the wrap makes the array act as a loop.
• What is the complexity? O(1) per operation, and O(k) space for capacity k.
• How do you tell full from empty? Explain the count method or the one-slot method, and say which costs a slot.
• What if the capacity is a power of two? Then % cap can be replaced by & (cap - 1), which is a faster bit operation. This is an optimisation, not a requirement, and you should state it as such.

When you answer, say the full and empty rule before you write code. Interviewers often mark down a solution that tests front == rear without a plan for the ambiguity.

Variations and edge cases

Test your ring with these cases:

• Capacity 1. A ring with one slot holds at most one item, so push then pop must alternate.
• Repeated push and pop, many times around the ring. Check that the indexes wrap correctly after several laps.
• Push until full, pop one, push again. The new item must go into the freed slot.
• Pop from an empty ring. The function must refuse and must not move the front.
• A moving average with k larger than the number of values. The divisor must be the count of real values, not k.

The last case is the one that most often goes wrong in the moving average. The program uses filled for the divisor, so the first two averages are computed over one and two values. Using k would give the wrong answer for the start of the stream.

Real-world uses

Audio systems keep a ring of samples so the sound card always has data to play, while the program fills the ring with new samples. Network drivers keep a ring of descriptors for incoming packets. Logging systems keep a ring of the most recent events, so the newest records are available without growing memory. In each case the buffer is fixed in size, and the wrap prevents any copying.

Practice

1. Easy. For a ring of capacity 5 with front = 3 and count = 4, which slot receives the next push? Explain the formula you used.

2. Easy. A ring of capacity 3 has pushed 1, 2 and 3, then popped once. What does peek return, and why?

3. Easy. Explain in one sentence why a plain array queue that only moves its indexes can report full while it still has free space.

4. Medium. Add a size() function to the first program that returns the count, and print it after each operation in the example. Hint: the function already exists in the state, so only return the value.

5. Medium. Rewrite the leave-one-slot-empty ring so that its capacity is the number of items it holds, not one less. Hint: allocate one extra slot in the vector and report the capacity as the size minus one.

6. Medium. Explain why cout << q.push(5) prints 1 and not true, and write the line that prints true or false instead.

7. Medium. Implement a ring that stores pairs of values, the name and the time, without any heap allocation. Hint: use a vector of a small struct, and keep the same index arithmetic.

8. Hard. Write a function that returns the largest value in a ring of the newest k numbers, updated after each new number. Hint: a moving maximum needs more than a running sum, so think about a deque of indexes from the previous lesson.

9. Hard. A ring has capacity 8. Explain how many items it can hold under each method, and why the leave-one-slot method is not a waste in some systems.

10. Hard. Find the bug in this pop, and explain what it does to a ring with capacity 3 holding 1, 2 and 3:

bool pop() {
    if (count == 0) return false;
    front = (front + 1) % cap;
    return true;
}

What you now know

• A circular queue reuses slots by wrapping indexes with %, so it never shifts items.
• The rear slot is (front + count) % cap when you track a count.
• Full and empty look the same if you track only two indexes, so use a count or leave one slot unused.
• A ring can compute running statistics, such as a moving average, in O(1) per update.
• A class that owns a raw array needs a copy rule, or it will crash with a double free. A vector avoids this.
• Negative modulo gives negative results in C++, so add cap before taking the remainder.