Queues, circular buffers and deques

A queue is the fair version of a stack: items leave in the order they arrived. You enqueue at the back and dequeue from the front: FIFO, first in, first out. Print jobs, customer support tickets, messages between services, and the steps of breadth-first search all use queues.

The slow way: a List

The obvious idea is list.Add(x) to enqueue and list.RemoveAt(0) to dequeue. But removing index 0 shifts every other item one slot left, so each dequeue is O(n), and processing n items costs O(n²).

The fast way: a circular buffer

Instead of moving the items, move the front marker. Keep two indexes: head (where the next item will be taken) and tail (where the next item will be written). Both only move forward, and when they reach the end of the array they wrap around to index 0 using % capacity. The array behaves like a ring.

1public class RingQueue<T>2{3    private T[] _items;4    private int _head;      // index of the front item5    private int _tail;      // index where the next item goes6    private int _count;7 8    public RingQueue(int capacity = 4) => _items = new T[capacity];9    public int Count => _count;10 11    public void Enqueue(T item)12    {13        if (_count == _items.Length) Grow();14        _items[_tail] = item;15        _tail = (_tail + 1) % _items.Length;     // wrap around16        _count++;17    }18 19    public T Dequeue()20    {21        if (_count == 0) throw new InvalidOperationException("Queue is empty");22        T item = _items[_head];23        _items[_head] = default!;24        _head = (_head + 1) % _items.Length;     // wrap around25        _count--;26        return item;27    }28 29    private void Grow()30    {31        var bigger = new T[_items.Length * 2];32        for (int i = 0; i < _count; i++)         // copy in queue order, front first33            bigger[i] = _items[(_head + i) % _items.Length];34        _items = bigger;35        _head = 0;36        _tail = _count;37    }38}

Queue<T> in .NET

.NET’s Queue<T> is a growable circular buffer, just like the one above.

1var jobs = new Queue<string>();2jobs.Enqueue("Export IFC");3jobs.Enqueue("Generate drawings");4jobs.Enqueue("Send report");5 6Console.WriteLine($"Next up: {jobs.Peek()}");7 8while (jobs.TryDequeue(out var job))9    Console.WriteLine($"Running {job} ({jobs.Count} left)");

Next up: Export IFC
Running Export IFC (2 left)
Running Generate drawings (1 left)
Running Send report (0 left)

Deque: a double-ended queue

A deque (say “deck”) allows adding and removing at both ends in O(1). It can act as a stack, a queue, or both at once, and it is the key structure of the “sliding window maximum” technique you will meet later. A circular buffer supports it naturally: moving head backwards is (head - 1 + capacity) % capacity.

.NET has no class called Deque<T>. Use LinkedList<T> (AddFirst, AddLast, RemoveFirst, RemoveLast are all O(1)), or write a circular-buffer deque when performance matters.

Other queues you will meet

1var counter = new RecentCounter();2foreach (int t in new[] { 1, 100, 3001, 3002 })3    Console.Write(counter.Ping(t) + " ");4 5public class RecentCounter6{7    private readonly Queue<int> _times = new();8 9    public int Ping(int t)10    {11        _times.Enqueue(t);12        while (_times.Peek() < t - 3000)13            _times.Dequeue();           // too old, never needed again14        return _times.Count;15    }16}

1 2 3 3