Stacks, Queues and Ring Buffers in C#: Your Own Implementations and Real Uses
What makes a queue O(1) on an array is the circular buffer: instead of shifting elements, the head and tail indexes advance and wrap around; a queue built with List.RemoveAt(0) is 497 times slower than Queue<T> with 100,000 orders. We write an array-based stack, a circular queue that unwraps the ring as it grows, a bounded ring buffer with an overflow policy, bracket validation, undo/redo and a monotonic stack, all with xUnit tests.
Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.
Guess First
Bookstore's order processing service puts incoming orders in line and processes them starting from the oldest. A developer built that line with a List<Order>: a new order is appended with Add, the next one is read with list[0] and removed with RemoveAt(0). The code works; the tests are green.
On campaign day 100,000 orders pile up in the line. How much does doing the same job with a Queue<Order> change: a few percent, 10 times, 500 times? Second question: Queue<T> also uses an array inside. How does it make removing from the front O(1) without shifting the array?
Stack: Last In, First Out
A stack is an ADT (Abstract Data Type) with a LIFO (Last In, First Out) contract: Push puts on top, Pop takes the top, Peek looks without taking. Implementing it on an array is natural: "the top" is the end of the array, and appending and removing at the end are already cheap. It is almost the same as the dynamic array from the series' second post:
namespace Algorithms.Linear;
public sealed class ArrayStack<T>
{
private T[] _items = new T[4];
public int Count { get; private set; }
public void Push(T item)
{
if (Count == _items.Length) Array.Resize(ref _items, _items.Length * 2);
_items[Count++] = item;
}
public T Pop()
{
if (Count == 0) throw new InvalidOperationException("Stack is empty.");
T item = _items[--Count];
_items[Count] = default!; // do not keep a reference to a popped item
return item;
}
public T Peek() => Count == 0 ? throw new InvalidOperationException("Stack is empty.") : _items[Count - 1];
public bool TryPop(out T item)
{
if (Count == 0) { item = default!; return false; }
item = Pop();
return true;
}
public void Clear()
{
Array.Clear(_items, 0, Count);
Count = 0;
}
}Push is amortized O(1), Pop and Peek are O(1). The default assignment in Pop is the same lesson as the removed slot in the series' second post: leave the popped element in the array and the GC (Garbage Collector) cannot collect it. The BCL (Base Class Library) Stack<T> is array-based in the same way and does the same cleanup.
Queue and the Circular Buffer
A queue has a FIFO (First In, First Out) contract: Enqueue appends at the end, Dequeue takes from the front. Here is the problem with the List solution from the opening: taking from the front means shifting everything else in the array one slot to the left. The fix is to advance an index that marks where the front is, instead of shifting elements. When the front and the end reach the end of the array they wrap around to the start; the array is logically used as a ring. This is called a circular buffer.
namespace Algorithms.Linear;
public sealed class CircularQueue<T>
{
private T[] _items = new T[4];
private int _head; // next item to dequeue
private int _tail; // next free slot
private int _count; // head == tail means empty OR full; the count tells which
public int Count => _count;
public int Capacity => _items.Length;
public void Enqueue(T item)
{
if (_count == _items.Length) Grow();
_items[_tail] = item;
_tail = (_tail + 1) % _items.Length;
_count++;
}
public T Dequeue()
{
if (_count == 0) throw new InvalidOperationException("Queue is empty.");
T item = _items[_head];
_items[_head] = default!;
_head = (_head + 1) % _items.Length;
_count--;
return item;
}
private void Grow()
{
T[] bigger = new T[_items.Length * 2];
// unwrap: copy [head..end) then [0..tail) so the new array starts at index 0
int firstPart = Math.Min(_count, _items.Length - _head);
Array.Copy(_items, _head, bigger, 0, firstPart);
Array.Copy(_items, 0, bigger, firstPart, _count - firstPart);
_items = bigger;
_head = 0;
_tail = _count;
}
internal (int Head, int Tail) Positions => (_head, _tail);
}
The classic trap of a circular buffer is telling empty from full. In both, _head == _tail: in an empty queue both point to the same free slot, in a full queue _tail has wrapped around and caught up with _head. There are three common fixes: keep a separate _count (what we do here), always leave one slot empty and make the "full" condition (tail + 1) % length == head, or increase the indexes forever without modulo and look at their difference. The two Array.Copy calls in Grow are the second critical point: copy a wrapped ring into the bigger array as it is and the order breaks. You have to flatten the ring by copying from _head to the end first, then from the start to _tail.
The test brings exactly these two situations together: the queue fills up, two elements leave from the front, two new ones wrap around to the start of the array, and a growth is triggered in exactly that state:
[Fact]
public void CircularQueue_WrapsThenGrows_KeepsFifoOrder()
{
CircularQueue<int> queue = new();
for (int i = 1; i <= 4; i++) queue.Enqueue(i); // full: capacity 4
queue.Dequeue();
queue.Dequeue();
queue.Enqueue(5);
queue.Enqueue(6); // tail wrapped to the start
Assert.Equal((2, 2), queue.Positions);
queue.Enqueue(7); // full and wrapped: grow must unwrap
List<int> drained = [];
while (queue.Count > 0) drained.Add(queue.Dequeue());
Assert.Equal([3, 4, 5, 6, 7], drained);
Assert.Equal(8, queue.Capacity);
}The BCL's Queue<T> has the same structure: Queue.cs in dotnet/runtime has the fields _array, _head, _tail and _size. There are two differences: growth is ×2 but adds at least 4 slots, and advancing the index uses a "reset to zero at the end" check instead of %. According to the comment in the source, the remainder operator is noticeably slower for this. Using the API (Application Programming Interface) is covered in the C# Collections series post "C# Queue, Stack, LinkedList and PriorityQueue".
Use the same ring from both ends and you get a deque (double-ended queue): stepping _head back by one makes adding at the front O(1) too. The BCL has no ready-made Deque<T>; when one is needed, people either use LinkedList<T> or add AddFirst and RemoveLast to a circular buffer like this one.
Bounded Ring Buffer: the Last N Log Lines
Sometimes you do not want the queue to grow. When Bookstore's payment service fails, you want to attach the last 200 log lines to the error report, but you cannot keep the whole log in memory. A fixed-capacity ring buffer is made for this: a ring that knows in advance what to do when it fills up.
namespace Algorithms.Linear;
public enum OverflowPolicy
{
OverwriteOldest,
Reject,
}
// fixed capacity, never grows: memory use is decided up front
public sealed class RingBuffer<T>(int capacity, OverflowPolicy policy)
{
private readonly T[] _items = new T[capacity];
private int _head;
private int _count;
public int Count => _count;
public long Dropped { get; private set; }
public bool TryWrite(T item)
{
if (_count == _items.Length)
{
if (policy == OverflowPolicy.Reject)
{
Dropped++;
return false;
}
// overwrite: the oldest item is lost, head moves forward
_items[_head] = item;
_head = (_head + 1) % _items.Length;
Dropped++;
return true;
}
_items[(_head + _count) % _items.Length] = item;
_count++;
return true;
}
// oldest first
public T[] Snapshot()
{
T[] result = new T[_count];
for (int i = 0; i < _count; i++) result[i] = _items[(_head + i) % _items.Length];
return result;
}
}[Fact]
public void RingBuffer_Overwrite_KeepsLastN()
{
RingBuffer<string> lastLines = new(3, OverflowPolicy.OverwriteOldest);
foreach (string line in new[] { "l1", "l2", "l3", "l4", "l5" }) lastLines.TryWrite(line);
Assert.Equal(["l3", "l4", "l5"], lastLines.Snapshot());
Assert.Equal(2, lastLines.Dropped);
}
[Fact]
public void RingBuffer_Reject_KeepsFirstN()
{
RingBuffer<string> buffer = new(3, OverflowPolicy.Reject);
bool[] accepted = [.. new[] { "l1", "l2", "l3", "l4" }.Select(buffer.TryWrite)];
Assert.Equal([true, true, true, false], accepted);
Assert.Equal(["l1", "l2", "l3"], buffer.Snapshot());
}The two policies answer two different questions. Overwrite is for "what happened most recently?": logs, metric samples, the last N requests. Reject is for "nothing may disappear silently; the excess is turned away": orders that must be processed, work the caller must retry. The Dropped counter matters in both; if you do not expose the number of lost or rejected elements as a metric, nobody notices that the buffer overflows all the time.
Jobs a Stack Solves: Brackets and Undo/Redo
A stack is the natural tool for every problem shaped like "close the most recently opened first". Bookstore's campaign rule editor checks bracket balance before saving the expression the user typed:
public static class BracketValidator
{
// returns the index of the first error, or -1 if the text is balanced
public static int FindError(string text)
{
Stack<(char Bracket, int Index)> open = new();
for (int i = 0; i < text.Length; i++)
{
char c = text[i];
if (c is '(' or '[' or '{')
{
open.Push((c, i));
}
else if (c is ')' or ']' or '}')
{
char expected = c switch { ')' => '(', ']' => '[', _ => '{' };
if (!open.TryPop(out (char Bracket, int Index) top) || top.Bracket != expected)
return i;
}
}
return open.TryPeek(out (char Bracket, int Index) unclosed) ? unclosed.Index : -1;
}
}[Theory]
[InlineData("order.Items[0].Price * (1 - discount)", -1)]
[InlineData("{ \"title\": [\"Dune\" }", 19)]
[InlineData("f(a, g(b)", 1)]
[InlineData(")(", 0)]
public void BracketValidator_FindsFirstError(string text, int expected)
{
Assert.Equal(expected, BracketValidator.FindError(text));
}The second test is a broken piece of JSON (JavaScript Object Notation): a [ is opened but a } comes first, and the error is at index 19. In the third, the first unclosed bracket is at index 1. Because the stack can also tell where the error is, you can show the user a message such as "unexpected } at character 19". A check with a single counter only works for a single bracket type; it cannot catch crossed text such as ([)].
Undo/redo is two stacks: one holds the states that can be undone, the other the ones that can be redone.
public sealed class EditorHistory(string initial)
{
private readonly Stack<string> _undo = new();
private readonly Stack<string> _redo = new();
public string Text { get; private set; } = initial;
public void Apply(string newText)
{
_undo.Push(Text);
_redo.Clear(); // a new edit invalidates the redo branch
Text = newText;
}
public bool Undo()
{
if (!_undo.TryPop(out string? previous)) return false;
_redo.Push(Text);
Text = previous;
return true;
}
public bool Redo()
{
if (!_redo.TryPop(out string? next)) return false;
_undo.Push(Text);
Text = next;
return true;
}
}Forget the _redo.Clear() line in Apply, and after the user undoes and types something new, "redo" brings back a future they never wrote. In a real editor each step should hold only the change (a command), not the whole text; otherwise a 10,000-step history means 10,000 copies of the text. The Command pattern is covered in the Design Patterns series; the two-stack structure here stays exactly the same.
Monotonic Stack: Next Greater and Stock Span
The stack has a less known but powerful use: a stack that keeps its elements in a fixed order (always decreasing or always increasing). Bookstore's price history screen asks for every day, "on which day was the price higher for the first time after this one?" A nested loop that looks ahead from each day is O(n²); with a monotonic stack it is O(n):
public static class MonotonicStack
{
// for each day, the next day with a higher price; -1 if none. O(n): each index is pushed and popped once
public static int[] NextGreater(int[] prices)
{
int[] result = new int[prices.Length];
Array.Fill(result, -1);
Stack<int> waiting = new(); // indexes whose prices decrease from bottom to top
for (int i = 0; i < prices.Length; i++)
{
while (waiting.Count > 0 && prices[waiting.Peek()] < prices[i])
result[waiting.Pop()] = i;
waiting.Push(i);
}
return result;
}
// span: how many consecutive days up to today had price <= today's price
public static int[] StockSpan(int[] prices)
{
int[] span = new int[prices.Length];
Stack<int> higher = new();
for (int i = 0; i < prices.Length; i++)
{
while (higher.Count > 0 && prices[higher.Peek()] <= prices[i])
higher.Pop();
span[i] = higher.Count == 0 ? i + 1 : i - higher.Peek();
higher.Push(i);
}
return span;
}
}[Fact]
public void NextGreater_ReturnsIndexOfNextHigherPrice()
{
int[] prices = [73, 74, 75, 71, 69, 72, 76, 73];
Assert.Equal([1, 2, 6, 5, 5, 6, -1, -1], MonotonicStack.NextGreater(prices));
}
[Fact]
public void StockSpan_ReturnsConsecutiveLowerOrEqualDays()
{
int[] prices = [100, 80, 60, 70, 60, 75, 85];
Assert.Equal([1, 1, 1, 2, 1, 4, 6], MonotonicStack.StockSpan(prices));
}The idea: the stack holds the days that have not found their answer yet, and their prices decrease from bottom to top. When a new day arrives, it is the answer for every waiting day cheaper than it; those leave the stack. Because of the nested while the code looks O(n²), but each index enters the stack once and leaves at most once. The total number of iterations of all the while loops never exceeds n. Counting "total cost" this way is exactly the aggregate method from the Big-O and Complexity series post "Amortized Analysis".
$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.StackQueueTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (567ms)
Test run summary: Passed!
total: 11
failed: 0
succeeded: 11Measuring: List.RemoveAt(0) versus a Queue
Back to the opening question. The benchmark enqueues N elements and dequeues them all in order; three implementations do the same job:
[Benchmark]
public long ListRemoveAtZero()
{
List<int> queue = [];
for (int i = 0; i < N; i++) queue.Add(i);
long sum = 0;
while (queue.Count > 0)
{
sum += queue[0];
queue.RemoveAt(0); // shifts every remaining item: O(n) per dequeue
}
return sum;
}BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
[Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a
| Method | N | Mean | Ratio | Allocated |
|----------------- |------- |---------------:|-------:|-----------:|
| BclQueue | 1000 | 4.298 us | 1.00 | 8.23 KB |
| OwnCircularQueue | 1000 | 5.876 us | 1.37 | 8.2 KB |
| ListRemoveAtZero | 1000 | 24.514 us | 5.71 | 8.23 KB |
| | | | | |
| BclQueue | 100000 | 582.184 us | 1.00 | 1024.59 KB |
| OwnCircularQueue | 100000 | 620.533 us | 1.07 | 1024.55 KB |
| ListRemoveAtZero | 100000 | 289,619.803 us | 497.52 | 1024.39 KB |With 1,000 orders the gap is 5.7 times and 24 µs; nobody notices. At 100,000 the List takes 290 ms and Queue<T> 0.58 ms: 497 times. The List version shifts every remaining element on each RemoveAt(0); the total shifting is around n²/2, about 5 billion element copies for 100,000. All three allocate the same (the array's growth); the difference comes entirely from shifting. Our own circular queue is 7–37 percent slower than the BCL; most of that is the % at every step and micro-optimizations the BCL does and we do not. The measurement ran while other work was running on the machine; look at the ratios.
In Production
None of the structures in this post is thread-safe, and neither are the BCL's Stack<T> and Queue<T>. If several threads write to and read from the same queue, use ConcurrentQueue<T> or, better, System.Threading.Channels. A bounded channel gives you the production version of the overflow policy we wrote here: with BoundedChannelFullMode you choose to wait, or to drop the oldest or the newest, when it is full. Details are in the C# Async series posts "C# Synchronization: lock, Interlocked, SemaphoreSlim and Concurrent Collections" and "Producer/Consumer with C# Channels".
An unbounded queue means unbounded memory. If the consumer is slower than the producer, Queue<T> grows forever and the process crashes when it hits its memory limit. Every queue in production should have an upper bound and a written decision about what happens at that bound; that decision is the system's backpressure behaviour.
Watch out for order expectations coming from a stack. Enumerating a Stack<T> with foreach or calling ToArray() returns elements with the top first, which is the reverse of insertion order. Code that turns a stack into JSON and loads it back ends up with the order reversed.
Common Pitfalls
Not deciding the ring buffer's overflow policy. The answer to "what happens when it is full?" should not be given silently in a branch of an if; it should be chosen explicitly with an enum, and the number of dropped elements should be reported as a metric.
Mixing up empty and full. In a circular buffer without a separate count, head == tail means two things; code that mistakes "full" for "empty" loses every element in the queue at once.
Not unwrapping the ring while growing. Copying a wrapped buffer in one piece with Array.Copy(_items, bigger, _count) breaks the order; the test was written to catch exactly this.
Using a List instead of a queue. RemoveAt(0) looks innocent on small data; the measurement showed a 497 times gap at 100,000 elements. Use Queue<T> for any structure you remove from at the front.
A Small Experiment
★☆☆ Replace the % operators in CircularQueue<T> with a "reset to zero at the end" check and run the benchmark again. How much of the gap with the BCL closes?
★★☆ Turn CircularQueue<T> into a CircularDeque<T>: AddFirst, AddLast, RemoveFirst, RemoveLast. How do you wrap a negative index when stepping _head back? Write a test that performs the same operations on a LinkedList<T>.
★★★ Use the monotonic stack idea for "the lowest price of the last 30 days": write a method that returns, for each day, the minimum of the 30-day window up to that day in O(n). Hint: you need to remove from both ends, so a deque.
In this post we kept the stack ourselves. In the next post we look at the stack the runtime keeps for us: the call stack. The anatomy of recursion, the StackOverflowException that cannot be caught, and the technique of turning a recursive algorithm into an iterative one with an explicit Stack<T>, just like the ones we wrote here.