IndexedQueue<T> - A Custom Queue in C#

• Download source code - 7.5 KB

Introduction

Microsoft provides a Queue<T> class but despite being ordered, it does not provide indexed access to its elements. Since I needed one that allowed efficient access by index, I reimplemented a queue over a growable circular buffer backed by an array. This is similar to how Microsoft's implementation does it. The main difference is mine exposes just a little bit more functionality. This class is highly specialized, but when you need it, you really need it, so I'm providing it here. I use it in my backtracking parsers to back the lookahead buffer.

Note: I originally called this Queue<T> because that's the best name for it, but I changed it to avoid collision with Microsoft's queue. The project name and folder names reflect the old name, but the class and source files have been updated with the new name.

Using the Code

Using the code is exactly like using the code in Microsoft's Queue<T> with the addition of an indexer property. The reason I didn't implement IList<T> is because to implement Insert() is non-trivial and at that point, the container essentially becomes a double-ended queue in functionality, which is a whole different data structure. Eventually, I may post one.

The demo code is pretty self explanatory:

var q = new IndexedQueue<int>(1);
Console.WriteLine("Enqueuing 1..20");
for (var i = 0; i < 20; ++i)
    q.Enqueue(i + 1);

Console.WriteLine("Dequeuing 1..10");
for (var i = 0; i < 10; ++i)
    Console.Write("{0} ",q.Dequeue());
Console.WriteLine();

Console.WriteLine("Enqueuing 21..40 (force array wrap)");
for (var i = 0; i < 20; ++i)
    q.Enqueue(i + 21);

Console.WriteLine("Enumerating");
foreach (var i in q)
    Console.Write("{0} ", i);
Console.WriteLine();

Console.WriteLine("Removing 34 (middle of array)");
(q as System.Collections.Generic.ICollection<int>).Remove(34);

Console.WriteLine("Enumerating");
foreach (var i in q)
    Console.Write("{0} ", i);
Console.WriteLine();

Console.WriteLine("Removing 32 (end of array)");
(q as System.Collections.Generic.ICollection<int>).Remove(32);

Console.WriteLine("Enumerating");
foreach (var i in q)
    Console.Write("{0} ", i);
Console.WriteLine();

Implementing it was fairly straightforward, but removes from the middle (for ICollection<T>) got a little tricky.

Anyway, if you need it, here it is. Most people probably never will, but there you go.

History

• 12^th December, 2019 - Initial submission