Lesson 33 of 62Intermediate16 min

HashSet, Queue and Stack

By the end of this lesson

Pick the structure that matches your access pattern.

A List can do almost anything, which is why it gets used for everything. Three other collections each answer one question particularly well, and choosing one tells the next reader what you intended.

The three questions are: have I already seen this? Who is next in line? What did I do most recently? Those map to HashSet, Queue and Stack.

What each one is for:

HashSet: Holds each item at most once and answers "is this in here?" in roughly constant time, using the same hashing idea as a Dictionary. It has no order and no positions.
Queue: First in, first out. You add at the back and take from the front, which is the order a fair waiting line works in.
Stack: Last in, first out. You add and take from the same end, so the most recent item comes back first. Undo histories work this way.

HashSet — uniqueness and fast membership checks

HashSet<string> skusSeen = new HashSet<string>();

Console.WriteLine(skusSeen.Add("DL-1001"));   // True  — it was new
Console.WriteLine(skusSeen.Add("NB-2002"));   // True
Console.WriteLine(skusSeen.Add("DL-1001"));   // False — already present, nothing added

Console.WriteLine(skusSeen.Count);            // 2
Console.WriteLine(skusSeen.Contains("NB-2002")); // True

// Which SKUs does the Pune warehouse stock that Nagpur does not?
HashSet<string> pune = new HashSet<string> { "DL-1001", "NB-2002", "PN-3003" };
HashSet<string> nagpur = new HashSet<string> { "NB-2002", "PN-3003", "CT-4004" };

HashSet<string> onlyInPune = new HashSet<string>(pune);
onlyInPune.ExceptWith(nagpur);                // { DL-1001 }

HashSet<string> inBoth = new HashSet<string>(pune);
inBoth.IntersectWith(nagpur);                 // { NB-2002, PN-3003 }

Add returns a bool rather than throwing on a duplicate. That return value is often the whole reason to use a HashSet: it tells you whether this is the first time you have seen something.
Contains is a hash lookup, so it does not slow down as the set grows. The same check on a List compares items one by one.
ExceptWith and IntersectWith modify the set they are called on, which is why each example copies first with new HashSet<string>(pune).
There is no indexing and no reliable order. If you need either, a HashSet is the wrong choice.

Queue — first in, first out

Queue<string> approvalQueue = new Queue<string>();

approvalQueue.Enqueue("INV-2201");
approvalQueue.Enqueue("INV-2202");
approvalQueue.Enqueue("INV-2203");

Console.WriteLine(approvalQueue.Peek());    // INV-2201 — look without removing
Console.WriteLine(approvalQueue.Count);     // 3

string next = approvalQueue.Dequeue();      // INV-2201, and it leaves the queue
Console.WriteLine(next);
Console.WriteLine(approvalQueue.Count);     // 2

// Drain it safely, without checking Count separately.
while (approvalQueue.TryDequeue(out string? reference))
{
    Console.WriteLine($"Approving {reference}");
}

Enqueue adds at the back. Dequeue removes and returns the item at the front. Peek returns the front item and leaves it there.
Dequeue and Peek throw InvalidOperationException on an empty queue. TryDequeue and TryPeek return false instead, which makes the draining loop above read cleanly.
The order is fixed by the structure. Nobody can index into the middle or reorder it by accident, and that constraint is the reason to choose it over a List.

Stack — last in, first out

Stack<string> editHistory = new Stack<string>();

editHistory.Push("Added line DL-1001");
editHistory.Push("Changed quantity to 3");
editHistory.Push("Applied 10% discount");

Console.WriteLine(editHistory.Peek());      // Applied 10% discount — the most recent

string undone = editHistory.Pop();          // removes and returns the discount change
Console.WriteLine($"Undid: {undone}");

while (editHistory.TryPop(out string? step))
{
    Console.WriteLine($"Undid: {step}");
}
// Undid: Changed quantity to 3
// Undid: Added line DL-1001

Push adds to the top. Pop removes and returns the top item. Peek looks at it without removing.
The undo order falls out of the structure: the last change made is the first one reversed, which is what a user expects.
Like a queue, Pop and Peek throw when empty, and TryPop and TryPeek are the non-throwing versions.

Queue against Stack, since the two are easy to mix up:

	Queue — FIFO	Stack — LIFO
Add with	Enqueue, at the back	Push, on the top
Remove with	Dequeue, from the front	Pop, from the top
Which item comes out	The one waiting longest	The one added most recently
Everyday analogy	A queue at a counter	A pile of plates
Typical use	Jobs to process in arrival order, fair scheduling	Undo history, retracing steps, evaluating nested structures

Common mistake

Common mistakes

Putting custom objects in a HashSet without overriding Equals and GetHashCode. Two Product objects with identical values count as different items, so the set happily holds both and your deduplication does nothing. A record gives you the right comparison behaviour without writing it yourself.

Calling Dequeue or Pop without checking whether anything is there. On an empty collection both throw. Use TryDequeue and TryPop, which also make loops shorter.

Expecting a HashSet to keep insertion order. It does not, and the order you observe can change as the set grows. If you need uniqueness and order, keep a List for order and a HashSet alongside it for the membership check.

Mutating an object after adding it to a HashSet. The same trap as a dictionary key: the hash was taken from the old state, so the item can no longer be found.

Assuming Queue is a message queue. It is an in-memory structure with no durability, no delivery guarantees and no thread safety. If items must survive a restart or cross a process boundary, you need an actual message broker. ConcurrentQueue handles the multi-threaded case within one process.

When to use this

When a plain List is still the better answer

You need positions, ordering, or to look at an item without removing it from the middle. None of these three structures offers that.

Duplicates are meaningful. Three separate orders for the same SKU are three facts, and a HashSet would discard two of them.

The collection is small and short-lived. Scanning fifteen items for a duplicate is not worth a second collection, and a List is easier to inspect while debugging.

You need to enumerate repeatedly. Iterating a Queue or Stack without removing items is possible but reads oddly, and the intent of the type is being ignored at that point.

The honest summary: reach for these when the access pattern is the point and you want the type to enforce it. Reach for List when you want general-purpose storage.

Summary

HashSet holds each item once and checks membership by hashing, with no order and no indexing
Queue is first in, first out: Enqueue at the back, Dequeue from the front
Stack is last in, first out: Push and Pop at the same end
Dequeue, Pop and Peek throw when empty; the Try versions return false instead
Custom types need Equals and GetHashCode before a HashSet can recognise duplicates

Practice

Attempt each one before opening the solution. Getting it wrong first is how the idea sticks.

Try it yourself

You are given a List of order references that may contain duplicates. Produce a list of the unique references in their original first-seen order.

Do it in one pass, using a HashSet for the checking and a List for the order.

Show solution

Neither structure can do this alone. A HashSet gives you the cheap duplicate check and loses the order; a List keeps the order and makes every check a scan. Using both is the standard answer, and Add returning false is what keeps it to one pass.

For a handful of items a List with Contains is perfectly acceptable and shorter. The two-structure version matters once the input is large enough that repeated scanning shows up, because the cost of the List-only version grows with the square of the input size.

List<string> incoming = new List<string>
{
    "INV-2201", "INV-2202", "INV-2201", "INV-2203", "INV-2202"
};

HashSet<string> seen = new HashSet<string>();
List<string> uniqueInOrder = new List<string>();

foreach (string reference in incoming)
{
    if (seen.Add(reference))        // true only the first time
    {
        uniqueInOrder.Add(reference);
    }
}

foreach (string reference in uniqueInOrder)
{
    Console.WriteLine(reference);
}
// INV-2201, INV-2202, INV-2203

Think about it

Support tickets should be worked oldest first, except that escalated tickets jump ahead of everything not yet escalated.

Does a Queue handle this? If not, what would you use, and what does that tell you about picking a structure from a description of the rules?

Show solution

A Queue does not handle it. A queue has exactly one ordering rule — arrival — and no way to insert ahead of waiting items. Forcing it would mean rebuilding the queue on every escalation.

There are two reasonable answers. PriorityQueue, available in .NET 6 and later, stores each item with a priority and always hands back the most urgent; that matches the requirement directly. Or keep two queues, one escalated and one normal, and always take from the escalated one first — simpler to reason about, and it naturally preserves arrival order within each band.

The general lesson is that the structure follows from the access pattern, and the access pattern is stated in the requirement. "Oldest first" is a queue. "Most recent first" is a stack. "Most urgent first" is a priority queue. When the requirement names two rules at once, expect to need either a structure that understands priority or more than one collection.

Saved in this browser only.