Sets, Queues and Stacks

HashSet for uniqueness, Queue for first-in-first-out, Stack for last-in-first-out, and the problem each one answers.

SyntaxHashSet<string> seen = new HashSet<string>();

These three collections each exist to answer one question quickly. Using the right one makes the code say what it means, and makes the wrong use impossible.

HashSet<T>: is this already in here?

A HashSet<T> holds each distinct value once. Add(item) returns true when the item was new, and the set now holds it; it returns false when the item was already there, and then the set is left unchanged. Contains(item) answers membership without searching every item, the way a list would have to. A set has no positions, so there is no indexer, and the order you get items back in is not guaranteed.

Queue<T>: first in, first out

A queue is a line at a counter. Enqueue(item) joins the back. Dequeue() removes and returns the item at the front. Peek() looks at the front without removing it. Use a queue for work that should be handled in the order it arrived.

Stack<T>: last in, first out

A stack is a pile of plates. Push(item) puts one on top. Pop() takes the top one off and returns it. Peek() reads the top without removing it. Use a stack when the most recent thing is the one you need next: undo history, a browser back button, matching brackets.

Where it goes wrong

Dequeue, Pop and Peek throw InvalidOperationException on an empty collection. The TryDequeue, TryPop and TryPeek methods return false instead, which makes a drain-it-all loop safe.

Example

Example · csharp
HashSet<string> seen = new HashSet<string>();
bool first = seen.Add("ana");    // true: it was not in the set
bool again = seen.Add("ana");    // false: already there, set unchanged

Queue<string> line = new Queue<string>();
line.Enqueue("ana");             // joins the back of the line
line.Enqueue("bo");
string served = line.Dequeue();  // leaves from the front: first in, first out

Stack<string> history = new Stack<string>();
history.Push("home");
history.Push("cart");
string back = history.Pop();     // the newest item comes off: last in, first out

Console.WriteLine($"added ana: {first}");
Console.WriteLine($"added ana again: {again}");
Console.WriteLine($"unique names: {seen.Count}");
Console.WriteLine($"served: {served}, still waiting: {line.Count}");
Console.WriteLine($"went back to: {back}, next back: {history.Peek()}");

// Output:
// added ana: True
// added ana again: False
// unique names: 1
// served: ana, still waiting: 1
// went back to: cart, next back: home

When to use it

  • Skipping records you have already processed, by keeping their ids in a HashSet.
  • Holding incoming jobs in a Queue so they run in the order they arrived.
  • Keeping an undo history in a Stack, where the last change is the first one reversed.
  • Answering whether a user's role is in an allowed set, without looping over the list each time.

More examples

Comparing two sets

IntersectWith, UnionWith and ExceptWith change the set they are called on, which is why each starts from a copy here. This is the short way to answer questions like which permissions two roles share.

Example · csharp
HashSet<string> monday = new HashSet<string> { "ana", "bo", "cy" };
HashSet<string> tuesday = new HashSet<string> { "bo", "dee" };

HashSet<string> both = new HashSet<string>(monday);
both.IntersectWith(tuesday);   // keep only what is in tuesday as well

HashSet<string> either = new HashSet<string>(monday);
either.UnionWith(tuesday);     // add everything tuesday has

// A set has no order of its own, so sort before printing.
List<string> names = new List<string>(either);
names.Sort();

Console.WriteLine($"came both days: {string.Join(", ", both)}");
Console.WriteLine($"came at all: {string.Join(", ", names)}");
Console.WriteLine($"count: {either.Count}");

// Output:
// came both days: bo
// came at all: ana, bo, cy, dee
// count: 4

Draining a queue safely

This is the shape of almost every work-queue loop. Note that Queue<T> is not safe to use from two threads at once; a later stage covers ConcurrentQueue<T> for that.

Example · csharp
Queue<string> jobs = new Queue<string>();
jobs.Enqueue("resize");
jobs.Enqueue("upload");
jobs.Enqueue("notify");

// TryDequeue takes the next item and returns false once the queue is empty,
// so the loop ends on its own instead of throwing.
while (jobs.TryDequeue(out string? job))
{
    Console.WriteLine($"running {job} ({jobs.Count} left)");
}

Console.WriteLine($"empty: {jobs.Count == 0}");

// Output:
// running resize (2 left)
// running upload (1 left)
// running notify (0 left)
// empty: True

A stack for matching brackets

Any nesting problem has this shape: parsing brackets or tags, tracking nested transactions, or an undo history where the newest change is undone first. Checking Count before Pop is what keeps the empty case from throwing.

Example · csharp
// "What was the last thing I opened?" is exactly what a stack answers.
Stack<char> open = new Stack<char>();
string text = "(a[b])";
bool balanced = true;

foreach (char c in text)
{
    if (c == '(' || c == '[')
    {
        open.Push(c);
    }
    else if (c == ')' || c == ']')
    {
        char expected = '(';

        if (c == ']')
        {
            expected = '[';
        }

        if (open.Count == 0 || open.Pop() != expected)
        {
            balanced = false;
        }
    }
}

Console.WriteLine($"balanced: {balanced && open.Count == 0}");
Console.WriteLine($"left open: {open.Count}");

// Output:
// balanced: True
// left open: 0

Related

dotnet dictionarydotnet listsdotnet object overridesdotnet collection interfacesdotnet concurrent collections

Discussion

  • Be the first to comment on this lesson.