Sets, Queues and Stacks

Beyond lists and dictionaries, System.Collections.Generic has collections built for specific jobs: HashSet for unique values, Queue for first-in-first-out processing, Stack for last-in-first-out, and PriorityQueue for "most urgent first". Picking the right one makes code simpler and faster.

HashSet: unique values

A HashSet<T> holds each value at most once and can tell you very quickly whether it contains something. Add returns false if the value was already there:

var visited = new HashSet<string>();

foreach (string page in new[] { "home", "about", "home", "shop", "about", "cart" })
{
    if (visited.Add(page))
        Console.WriteLine($"first visit: {page}");
}

Console.WriteLine(visited.Count);
Console.WriteLine(visited.Contains("shop"));

Output

first visit: home
first visit: about
first visit: shop
first visit: cart
4
True

Removing duplicates from any collection is a one-liner: new HashSet<int>(numbers), or numbers.Distinct() with LINQ.

Set operations

Sets support the operations from maths: union, intersection and difference. These methods change the set they're called on:

HashSet<string> alice = ["python", "sql", "c#", "git"];
HashSet<string> bob = ["c#", "java", "git", "docker"];

var both = new HashSet<string>(alice);
both.IntersectWith(bob);
Console.WriteLine("Both know: " + string.Join(", ", both));

var either = new HashSet<string>(alice);
either.UnionWith(bob);
Console.WriteLine("Together: " + string.Join(", ", either));

var onlyAlice = new HashSet<string>(alice);
onlyAlice.ExceptWith(bob);
Console.WriteLine("Only Alice: " + string.Join(", ", onlyAlice));

Console.WriteLine(alice.Overlaps(bob));
Console.WriteLine(new HashSet<string> { "git" }.IsSubsetOf(alice));

Output

Both know: c#, git
Together: python, sql, c#, git, java, docker
Only Alice: python, sql
True
True

Like Dictionary, a HashSet has no guaranteed order. SortedSet<T> keeps its values sorted and also offers Min, Max and range views.

Queue: first in, first out

A Queue<T> is like a line at a shop: items join at the back with Enqueue and leave from the front with Dequeue. Peek looks at the front item without removing it:

var printJobs = new Queue<string>();
printJobs.Enqueue("invoice.pdf");
printJobs.Enqueue("photo.jpg");
printJobs.Enqueue("letter.docx");

Console.WriteLine($"Next up: {printJobs.Peek()}");

while (printJobs.Count > 0)
{
    string job = printJobs.Dequeue();
    Console.WriteLine($"Printing {job}");
}

Console.WriteLine(printJobs.TryDequeue(out string? extra));

Output

Next up: invoice.pdf
Printing invoice.pdf
Printing photo.jpg
Printing letter.docx
False

Dequeue on an empty queue throws; TryDequeue returns false instead. Queues are natural for tasks waiting to be processed, messages, and breadth-first searches.

Stack: last in, first out

A Stack<T> is like a pile of plates: you Push onto the top and Pop from the top, so the most recent item comes out first. It's perfect for undo history:

var history = new Stack<string>();
history.Push("type 'Hello'");
history.Push("make bold");
history.Push("insert image");

Console.WriteLine($"Last action: {history.Peek()}");
Console.WriteLine($"Undo: {history.Pop()}");
Console.WriteLine($"Undo: {history.Pop()}");
Console.WriteLine($"Remaining: {string.Join(", ", history)}");

Output

Last action: insert image
Undo: insert image
Undo: make bold
Remaining: type 'Hello'

Using a stack: balanced brackets

To check that brackets in an expression are balanced, push each opening bracket; for each closing bracket, the top of the stack must be its partner:

foreach (string s in new[] { "(a[b]{c})", "(]", "((x)", "{[()()]}" })
{
    Console.WriteLine($"{s,-10} {IsBalanced(s)}");
}

static bool IsBalanced(string text)
{
    var open = new Stack<char>();
    foreach (char c in text)
    {
        if (c is '(' or '[' or '{')
        {
            open.Push(c);
        }
        else if (c is ')' or ']' or '}')
        {
            char expected = c switch { ')' => '(', ']' => '[', _ => '{' };
            if (open.Count == 0 || open.Pop() != expected)
                return false;
        }
    }
    return open.Count == 0;
}

Output

(a[b]{c})  True
(]         False
((x)       False
{[()()]}   True

PriorityQueue: most urgent first

A PriorityQueue<TElement, TPriority> always hands out the element with the lowest priority value next, whatever order they were added in:

var triage = new PriorityQueue<string, int>();
triage.Enqueue("sprained ankle", 3);
triage.Enqueue("cardiac arrest", 1);
triage.Enqueue("broken arm", 2);
triage.Enqueue("cough", 5);

while (triage.TryDequeue(out string? patient, out int priority))
{
    Console.WriteLine($"[{priority}] {patient}");
}

Output

[1] cardiac arrest
[2] broken arm
[3] sprained ankle
[5] cough

LinkedList

LinkedList<T> stores each item in a separate node linked to its neighbours, so inserting or removing in the middle is cheap once you hold a node. In practice List<T> is faster for almost everything else, so linked lists are rarely needed.

Choosing a collection

You need…	Use
An ordered sequence you add to and index into	`List<T>`
A fixed-size sequence	`T[]` (array)
Lookup by key	`Dictionary<TKey, TValue>`
Unique values, fast "contains" checks	`HashSet<T>`
Keys or values kept sorted	`SortedDictionary`, `SortedSet`
Process in arrival order	`Queue<T>`
Most recent first (undo, backtracking)	`Stack<T>`
Most important first	`PriorityQueue<T, P>`

For data shared between threads, the System.Collections.Concurrent namespace has thread-safe versions such as ConcurrentDictionary and ConcurrentQueue (lesson 58).

Try it yourself

Use a queue to simulate a round-robin scheduler: each task runs for up to 2 units, then goes to the back of the queue if it isn't finished.

var tasks = new Queue<(string Name, int Remaining)>();
tasks.Enqueue(("A", 3));
tasks.Enqueue(("B", 1));
tasks.Enqueue(("C", 4));

int clock = 0;
while (tasks.TryDequeue(out var task))
{
    int run = Math.Min(2, task.Remaining);
    clock += run;
    int left = task.Remaining - run;
    if (left > 0)
    {
        tasks.Enqueue((task.Name, left));
        Console.WriteLine($"t={clock}: {task.Name} paused, {left} left");
    }
    else
    {
        Console.WriteLine($"t={clock}: {task.Name} finished");
    }
}

Edit the code, copy it into Program.cs and run it with dotnet run Program.cs (.NET 10 or later). How to set up .NET

Output

t=2: A paused, 1 left
t=3: B finished
t=5: C paused, 2 left
t=6: A finished
t=8: C finished

PreviousDictionaries NextIndices, Ranges & Spans