C# & .NET (C# 14, .NET 10 LTS) Module 5 – Arrays and collections

Queues, stacks and priority queues: how to choose

Serve work in arrival order with Queue<T>, undo with Stack<T> and urgency with PriorityQueue, then choose a .NET collection by how code reads and writes it.

Intermediate
25 minutes
Examples run with .NET 10.0.401
By MySmartCoPilot

Free: A queue serves items in the order they arrived · A stack gives back the most recent item first · A priority queue serves the most urgent item first. With a pass: 3 in-depth parts and 3 interview answers, about 16 minutes.

What you will learn

Use Queue<T> for first-in, first-out work and Stack<T> for undo and nesting
Order work by urgency with PriorityQueue<TElement,TPriority>
Compare collection operations by their complexity and their measured cost
Choose a collection from the way code finds, adds and removes items

Before you start

Dictionaries, sets and comparers

What you’ll learn · Before you start

What you will learn

Use Queue<T> for first-in, first-out work and Stack<T> for undo and nesting
Order work by urgency with PriorityQueue<TElement,TPriority>
Compare collection operations by their complexity and their measured cost
Choose a collection from the way code finds, adds and removes items

Before you start

Dictionaries, sets and comparers

On this page

Five requests wait at a station help desk, and one of them is for medical help. Served in the order they came, it waits behind an enquiry; served by urgency, it goes first. Which item comes out next is the whole difference between Queue<T>, Stack<T> and PriorityQueue<TElement,TPriority>.

You will use queues for arrival order, stacks for undo and nesting, and priority queues for urgency, then choose among all the collections of this module by how your code uses them.

A queue serves items in the order they arrived

A ticket counter serves people in the order they joined. Queue<T> keeps that order, FIFO: First in, first out: the order of a queue, which always gives back the item that has waited longest. A Queue<T> adds at the back with Enqueue and takes from the front with Dequeue.: Enqueue adds at the back, Dequeue removes and returns the front item, and Peek only reads it:

counter.cs: a ticket counter as a Queue<string> C# · counter/counter.cs

// A ticket counter: people join at the back of the line and are served from the front.
var line = new Queue<string>();
line.Enqueue("Asha");
line.Enqueue("Ravi");
line.Enqueue("Meera");
Console.WriteLine($"in line          {string.Join(", ", line)}; Count {line.Count}; Peek {line.Peek()}");
Console.WriteLine($"Dequeue twice    {line.Dequeue()}, then {line.Dequeue()}");
line.Enqueue("Kiran");
Console.WriteLine($"Kiran joins      {string.Join(", ", line)}");

while (line.TryDequeue(out string? next))
{
    Console.WriteLine($"served           {next}");
}
Console.WriteLine($"TryDequeue now   {line.TryDequeue(out _)}: the line is empty");
try
{
    line.Dequeue();
}
catch (InvalidOperationException e)
{
    Console.WriteLine($"Dequeue now      {e.GetType().Name}");
}

// The array inside a queue is used as a ring: the front and the back move round it, and nothing is shifted.
// 1,000 tokens pass through a counter where at most 3 people ever wait, and the queue never needs a bigger array.
var counter = new Queue<int>(4);
for (int token = 1; token <= 1_000; token++)
{
    counter.Enqueue(token);
    if (counter.Count == 3)
    {
        counter.Dequeue();
    }
}
Console.WriteLine($"1,000 tokens through a queue of 4: capacity {counter.EnsureCapacity(0)}, waiting {string.Join(", ", counter)}");

Output

in line          Asha, Ravi, Meera; Count 3; Peek Asha
Dequeue twice    Asha, then Ravi
Kiran joins      Meera, Kiran
served           Meera
served           Kiran
TryDequeue now   False: the line is empty
Dequeue now      InvalidOperationException
1,000 tokens through a queue of 4: capacity 4, waiting 999, 1000

Recorded with .NET SDK 10.0.401 (runtime 10.0.12) on macOS 26 arm64. To run it yourself: dotnet run counter.cs

Asha joined first and was served first. On the empty queue Dequeue threw InvalidOperationException while TryDequeue returned False, which is why loops that drain a queue use TryDequeue. The documentation says the class is a circular array: An array used as a ring: the front and back positions move forward and wrap round to the start, so a queue adds and removes items without shifting any. Queue<T> is implemented this way.: front and back move round one array and wrap to its start, so no item is ever shifted. That is how 1,000 tokens passed through a queue of capacity 4 that never grew. Step through the first six tokens and watch the back wrap to slot 0:

Interactive · step through it Tokens 1 to 6 through a ring of four slots front and rear move round a fixed set of slots and wrap from the last slot to slot 0.

being moved or written

Pseudo-code

enqueue(x): if count = capacity: error "full"
a[rear] ← x; rear ← (rear + 1) mod capacity; count ← count + 1
dequeue(): if count = 0: error "empty"
x ← a[front]; front ← (front + 1) mod capacity; count ← count − 1; return x

A circular queue with 4 slots. front is where the next item leaves, rear where the next one goes; both wrap around to slot 0 after slot 3.

When it finishes: 2 items queued.

Items 0

Operations 0

The figure refuses an item when all four slots are taken; a Queue<T> grows instead, copying its items into a larger array, the one case in which the documentation gives Enqueue as O(n).

Checkpoint

Check: Queues, first in first out

Question 1 of 2 What does this print?
Read the code, then choose one answer.
```
var q = new Queue<int>();
q.Enqueue(5);
q.Enqueue(8);
q.Enqueue(2);
q.Dequeue();
Console.WriteLine(q.Peek());
```
2 8 It throws InvalidOperationException 5
Show the answer: Question 1 of 2

Answer: 8

A queue gives items back in the order they went in: Enqueue adds at the back, Dequeue and Peek work at the front.
Question 2 of 2 In counter.cs, 1,000 tokens passed through a Queue<int> made with capacity 4, and its capacity was still 4 at the end. Why did it never grow?
Choose one answer.

The tokens are ints, which the queue stores outside its array At most 3 tokens waited at once, and the front and back wrap round the same 4 slots A Queue<T> never grows past the capacity it was made with Dequeue shifts the remaining items to the start of the array

Show the answer: Question 2 of 2

Answer: At most 3 tokens waited at once, and the front and back wrap round the same 4 slots

The capacity a queue needs is the most items that wait at the same time, not the number that pass through it.

A stack gives back the most recent item first

Undo takes back the latest seat pick first. Stack<T> keeps that order, LIFO: Last in, first out: the order of a stack, which always gives back the item added most recently. A Stack<T> adds with Push and takes with Pop, both at its top.: Push adds on top, Pop removes and returns the top item, and Peek reads it. Every pick below is pushed, and every undo pops:

undo.cs: an undo history and a bracket check with Stack<T> C# · undo/undo.cs

// A seat map where every pick can be undone, most recent first: the undo history is a stack.
var picked = new List<int>();
var history = new Stack<int>();

void Pick(int seat)
{
    picked.Add(seat);
    history.Push(seat);
}

void Undo()
{
    if (history.TryPop(out int seat))
    {
        picked.Remove(seat);
        Console.WriteLine($"undo             seat {seat}; picked {string.Join(", ", picked)}");
    }
    else
    {
        Console.WriteLine("undo             nothing to undo");
    }
}

Pick(14);
Pick(15);
Pick(22);
Console.WriteLine($"picked           {string.Join(", ", picked)}; Peek {history.Peek()}; a foreach reads {string.Join(", ", history)}");
Undo();
Pick(23);
Undo();
Undo();
Undo();
Undo();

// A stack also checks nesting: every closing bracket must match the most recent opening one.
Console.WriteLine($"brackets of \"Seats(B2[14,15])\" balanced: {Balanced("Seats(B2[14,15])")}; of \"Seats(B2[14,15)]\": {Balanced("Seats(B2[14,15)]")}");

static bool Balanced(string text)
{
    var open = new Stack<char>();
    foreach (char c in text)
    {
        if (c is '(' or '[')
        {
            open.Push(c);
        }
        else if (c is ')' or ']')
        {
            char expected = c == ')' ? '(' : '[';
            if (!open.TryPop(out char top) || top != expected)
            {
                return false;
            }
        }
    }
    return open.Count == 0;
}

Output

picked           14, 15, 22; Peek 22; a foreach reads 22, 15, 14
undo             seat 22; picked 14, 15
undo             seat 23; picked 14, 15
undo             seat 15; picked 14
undo             seat 14; picked 
undo             nothing to undo
brackets of "Seats(B2[14,15])" balanced: True; of "Seats(B2[14,15)]": False

Recorded with .NET SDK 10.0.401 (runtime 10.0.12) on macOS 26 arm64. To run it yourself: dotnet run undo.cs

Seats 14, 15 and 22 were picked, and the first undo took back 22. A foreach over the stack read 22, 15, 14, top first, the order in which Pop would return them. On the empty stack TryPop returned false, so the fifth undo printed nothing to undo instead of throwing. The same structure checks nesting: each opening bracket waits on the stack, and each closing one must match the bracket on top, which is why Seats(B2[14,15)] failed. Replay the program’s picks and undos on a stack that holds 14:

Interactive · step through it The seat picks of undo.cs as pushes and pops Push puts an item on top; pop takes the top item off.

being compared or looked at
being moved or written

Pseudo-code

push(x): top ← top + 1; a[top] ← x
pop(): if empty: error "underflow"; x ← a[top]; top ← top − 1; return x
peek(): return a[top]

A stack of 1 item. Items go on and come off at the same end, the top: the last one in is the first one out (LIFO).

When it finishes: Empty stack.

Size 1

Operations 0

Like a queue, a Stack<T> keeps its items in an array, and Push and Pop touch only the top: both are O(1), except a Push that finds the array full and must copy it into a larger one.

Checkpoint

Check: Stacks, last in first out

Question 1 of 2 What does this print?
Read the code, then choose one answer.
```
var s = new Stack<string>();
s.Push("A");
s.Push("B");
s.Push("C");
Console.WriteLine(string.Join(" ", s));
```
C A B C It does not compile, because a stack cannot be enumerated C B A
Show the answer: Question 1 of 2

Answer: C B A

A stack is last in, first out, and enumerating it follows the same order, top first.
Question 2 of 2 A bracket check reads "(a[b)c]" with a stack. When it reaches the ")", what is on top, and what does it decide?
Choose one answer.

Nothing, because the stack is empty "[", which does not match ")", so the text is not balanced "(", which matches, so the check goes on ")", because closing brackets are pushed too

Show the answer: Question 2 of 2

Answer: "[", which does not match ")", so the text is not balanced

The newest opening bracket must close first, which is exactly the order a stack gives back, and why Seats(B2[14,15)] failed.

A priority queue serves the most urgent item first

The help desk’s requests arrive in no order of urgency. PriorityQueue<TElement,TPriority> stores every element with a priority and always gives back the element with the lowest priority value, so priority 1 is the most urgent:

priority.cs: help desk requests in a PriorityQueue<string, int> C# · priority/priority.cs

// Requests at a station help desk, served by urgency: the lowest priority number comes out first.
var desk = new PriorityQueue<string, int>();
desk.Enqueue("general enquiry", 5);
desk.Enqueue("medical help", 1);
desk.Enqueue("connecting train", 3);
desk.Enqueue("lost ticket", 4);
desk.Enqueue("wheelchair", 2);
Console.WriteLine($"Count {desk.Count}; Peek {desk.Peek()}");
while (desk.TryDequeue(out string? request, out int priority))
{
    Console.WriteLine($"  {priority}  {request}");
}

// Six requests of the same priority, made in the order A to F.
var ties = new PriorityQueue<string, int>();
foreach (string name in new[] { "A", "B", "C", "D", "E", "F" })
{
    ties.Enqueue(name, 1);
}
var order = new List<string>();
while (ties.TryDequeue(out string? name, out _))
{
    order.Add(name);
}
Console.WriteLine($"six requests of priority 1, made A to F, came out {string.Join(" ", order)}");

// UnorderedItems lists what is waiting, in the heap's own order rather than by priority.
var waiting = new PriorityQueue<string, int>([("wheelchair", 2), ("medical help", 1), ("general enquiry", 5), ("lost ticket", 4), ("connecting train", 3)]);
Console.WriteLine($"UnorderedItems  {string.Join(", ", waiting.UnorderedItems.Select(x => $"{x.Element} ({x.Priority})"))}");

Output

Count 5; Peek medical help
  1  medical help
  2  wheelchair
  3  connecting train
  4  lost ticket
  5  general enquiry
six requests of priority 1, made A to F, came out A F E D C B
UnorderedItems  medical help (1), wheelchair (2), general enquiry (5), lost ticket (4), connecting train (3)

Recorded with .NET SDK 10.0.401 (runtime 10.0.12) on macOS 26 arm64. To run it yourself: dotnet run priority.cs

Medical help came out first although it arrived second. Six requests of equal priority, made A to F, came out as A F E D C B: the documentation says the type does not guarantee first-in, first-out order for equal priorities. UnorderedItems listed five waiting requests in the heap’s own order, priorities 1, 2, 5, 4, 3. Inside is a min-heap: A tree kept in an array in which every parent's priority is no larger than its children's, so the smallest is always at the root; adding an item or removing the smallest takes O(log n) steps., which the documentation calls array-backed and quaternary: every parent has up to four children, none with a smaller priority, so the smallest sits at the root. Taking it out moves the last item to the root and lets it sink, in O(log n) steps. The figure draws two children per parent, the same idea with more levels:

Interactive · step through it Three Dequeue calls on the help desk priorities The root leaves; the last key takes its place and sinks while a child is smaller.

being compared or looked at
being moved or written
in its final place
the key, pivot or target

Pseudo-code

extractMin(): min ← a[0]; a[0] ← a[size − 1]; size ← size − 1
i ← 0
while i has a child smaller than a[i]:
c ← the smaller child; swap a[i] and a[c]; i ← c
return min

A min-heap of 5 keys. extractMin removes the root, the smallest key, and repairs the heap from the top.

When it finishes: Taken out: 1 2 3.

Comparisons 0

Swaps 0

The three collections differ in which item comes out next:

What differs	`Queue<T>`	`Stack<T>`	`PriorityQueue`
Next out	the oldest	the newest	the lowest priority
Add	`Enqueue`, O(1)	`Push`, O(1)	`Enqueue`, O(log n)
Take	`Dequeue`, O(1)	`Pop`, O(1)	`Dequeue`, O(log n)

Key idea

Choose by the item that must come out next: the oldest from a queue, the newest from a stack, the most urgent from a priority queue.

Checkpoint

Check: Priority queues

Question 1 of 2 A PriorityQueue<string, int> holds ("print", 3), ("save", 1) and ("send", 2), enqueued in that order. What does the first Dequeue return?
Choose one answer.

save It depends on the order of the Enqueue calls print send

Show the answer: Question 1 of 2

Answer: save

PriorityQueue is a min-heap: the smallest priority sits at the root, and Dequeue takes the root.
Question 2 of 2 Six requests of priority 1 are enqueued in the order A to F. In which order does PriorityQueue promise to return them?
Choose one answer.

A to F, like a queue F to A, like a stack In no particular order: equal priorities have no first-in, first-out promise Sorted by element, A to F

Show the answer: Question 2 of 2

Answer: In no particular order: equal priorities have no first-in, first-out promise

The heap compares priorities only, so equal priorities come out in whatever order its swaps leave them.

Shortest routes with a priority queue Pro: opens with a Pro, Premium or Ultimate pass

A priority queue is the engine of Dijkstra’s shortest-path algorithm, and the .NET one cannot lower a priority it already holds. The run below finds the fastest times across a small rail network and counts the entries that this leaves behind.

In this part:

Dijkstra’s algorithm with entries that go stale
What the stale entries cost

1 diagram · 1 runnable example (C#) · about 5 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

A fair waiting list: equal priorities and cancellations Pro: opens with a Pro, Premium or Ultimate pass

Equal priorities came out in no fixed order, which a waiting list cannot accept. The run below makes the order fair with an arrival number, then cancels two requests that are already waiting.

In this part:

Equal priorities need an arrival number to keep their order
Cancelling a request that is already waiting

1 runnable example (C#) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Choosing any collection by its measured costs Pro: opens with a Pro, Premium or Ultimate pass

Every collection of this module is fast at some operations and slow at others, and the slow ones decide. The run below times the same lookups and inserts in five collections, and the questions after it turn what your code does into a choice.

In this part:

Lookups and inserts in five collections, measured
Choose from the operations your code repeats
A drained queue keeps the memory of its busiest moment

1 runnable example (C#) · about 10 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Practise: a token counter with priority tokens

tokens.cs checks a class that you write: TokenCounter serves priority tokens before general ones, each kind in the order people joined, and Serve returns null when nobody waits. As given, its members throw, and the 6 checks fail:

tokens.cs: six checks of TokenCounter C# · tokens/tokens.cs

// Practice: finish TokenCounter so that every check below passes, then run this file again.
// People take a token as they arrive. Priority tokens are served before general ones, and within each kind
// people are served in the order they arrived. Serve returns the next name, or null when nobody waits.
var checks = new List<(string Name, Func<string> Run, string Expected)>
{
    ("general only, in arrival order", () => Serve(c => { c.Join("Asha", false); c.Join("Ravi", false); }, 2), "Asha Ravi"),
    ("priority first", () => Serve(c => { c.Join("Asha", false); c.Join("Meera", true); }, 2), "Meera Asha"),
    ("priority in arrival order", () => Serve(c => { c.Join("Dev", true); c.Join("Isha", true); c.Join("Kiran", true); }, 3), "Dev Isha Kiran"),
    ("mixed arrivals", () => Serve(c => { c.Join("A", false); c.Join("B", true); c.Join("C", false); c.Join("D", true); }, 4), "B D A C"),
    ("nobody waiting", () => Serve(c => { }, 1), "(none)"),
    ("count of waiting", () => { var c = new TokenCounter(); c.Join("A", true); c.Join("B", false); return c.Waiting.ToString(); }, "2"),
};

int passed = 0;
foreach (var (name, run, expected) in checks)
{
    string verdict;
    try
    {
        string got = run();
        verdict = got == expected ? "ok" : $"FAIL, got \"{got}\"";
    }
    catch (Exception e)
    {
        verdict = $"FAIL, {e.GetType().Name}";
    }
    if (verdict == "ok")
    {
        passed++;
    }
    Console.WriteLine($"{name}: {verdict}");
}
Console.WriteLine($"{passed} of {checks.Count} checks pass");
return passed == checks.Count ? 0 : 1;

// Joins people with setup, then serves times people and lists who came out.
static string Serve(Action<TokenCounter> setup, int times)
{
    var counter = new TokenCounter();
    setup(counter);
    var served = new List<string>();
    for (int i = 0; i < times; i++)
    {
        served.Add(counter.Serve() ?? "(none)");
    }
    return string.Join(" ", served);
}

sealed class TokenCounter
{
    public int Waiting => throw new NotImplementedException("How many people hold a token now?");

    public void Join(string name, bool priority) => throw new NotImplementedException("Keep priority and general tokens apart.");

    public string? Serve() => throw new NotImplementedException("Serve a priority token if there is one, else a general one.");
}

Output (exit status 1)

general only, in arrival order: FAIL, NotImplementedException
priority first: FAIL, NotImplementedException
priority in arrival order: FAIL, NotImplementedException
mixed arrivals: FAIL, NotImplementedException
nobody waiting: FAIL, NotImplementedException
count of waiting: FAIL, NotImplementedException
0 of 6 checks pass

Recorded with .NET SDK 10.0.401 (runtime 10.0.12) on macOS 26 arm64. To run it yourself: dotnet run tokens.cs

Write TokenCounter

Copy tokens.cs and give TokenCounter two Queue<string> fields, one for each kind of token. Join enqueues into one of them, Serve dequeues from the priority line first, and Waiting adds the two counts. Run dotnet run tokens.cs until it prints 6 of 6 checks pass.

These questions return to queues, stacks and priority queues, the idea you know least first:

Practice that adapts to you

Practise this lesson

6 questions about 6 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

Question 1 of 6 Which collection serves people at a ticket counter in the order they joined?
Choose one answer.

Queue<T> HashSet<T> PriorityQueue<TElement,TPriority> Stack<T>

Show the answer: Question 1 of 6

Answer: Queue<T>

Choose a queue when the oldest waiting item must come out next.
Question 2 of 6 A loop drains a queue with while (queue.Count > 0) Handle(queue.Dequeue()); and is rewritten with while (queue.TryDequeue(out var job)) Handle(job);. What does TryDequeue change?
Choose one answer.

It reads the front without removing it It waits until an item arrives It takes the newest item instead of the oldest It checks and takes in one call, returning false instead of throwing when the queue is empty

Show the answer: Question 2 of 6

Answer: It checks and takes in one call, returning false instead of throwing when the queue is empty

Try methods turn the empty case into a false return, which makes draining loops shorter and safer.
Question 3 of 6 An editor must undo the most recent change first, then the one before it. Which collection holds the history?
Choose one answer.

List<T> sorted by time Stack<T> HashSet<T> Queue<T>

Show the answer: Question 3 of 6

Answer: Stack<T>

Undo, nesting and depth-first walks all need the newest item first: a stack.
Question 4 of 6 What does this print?
Read the code, then choose one answer.
```
var s = new Stack<int>();
s.Push(1);
s.Push(2);
s.Peek();
s.Push(3);
Console.WriteLine(s.Pop() + s.Pop());
```
6 5 4 3
Show the answer: Question 4 of 6

Answer: 5

Push and Pop work at the top; Peek reads the top without changing anything.
Question 5 of 6 What does the min-heap inside a PriorityQueue<TElement,TPriority> keep at its root?
Choose one answer.

The element with the highest priority value The element with the lowest priority value The element enqueued most recently The element that was enqueued first

Show the answer: Question 5 of 6

Answer: The element with the lowest priority value

Dequeue takes the root and repairs the heap in O(log n) steps.
Question 6 of 6 A dashboard shows the requests in a PriorityQueue by looping over UnorderedItems and calls the list "the order of service". What is wrong?
Choose one answer.

Nothing: UnorderedItems is sorted by priority UnorderedItems lists the items in arrival order UnorderedItems removes the items it lists UnorderedItems follows the heap's array, not the priorities, so the list is not the order of service

Show the answer: Question 6 of 6

Answer: UnorderedItems follows the heap's array, not the priorities, so the list is not the order of service

To show the order of service, sort the items by priority, or copy the queue and dequeue the copy.

Interview questions

Fresher · When would you use a Queue<T> and when a Stack<T>?

Use a Queue<T> when items must come out in the order they went in, first in, first out: requests waiting for a worker, people at a counter, messages to process in order. Enqueue adds at the back and Dequeue takes the oldest from the front, both in O(1), because the queue moves two positions round a circular array instead of shifting items. Use a Stack<T> when the most recent item must come out first, last in, first out: an undo history, the nesting of brackets or tags, a depth-first walk. Push and Pop both work at the top. Choose by the order in which the next item must come out, and use PriorityQueue<TElement,TPriority> when urgency, not arrival, sets that order.

Mid to senior

You implement Dijkstra's shortest paths with PriorityQueue<TElement,TPriority>, and find that it has no way to lower the priority of an element it already holds. How do you handle a station whose best time improves, what does your approach cost, and when would you choose something else?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Fresher to mid

A waiting list uses PriorityQueue<Request, int> with the quota class as the priority. Two requests of the same class are sometimes served in the wrong order: the later one first. Why, and how do you fix it without losing O(log n) for each request?

Model answer, Pro. First step and follow-ups
Mid to senior

A service buffers incoming messages in a Queue<Message>. After a traffic burst of 1,000,000 messages is drained, the process still uses far more memory than before the burst, although the queue is empty. Why, and what would you change?

Model answer, Pro. First step and follow-ups

Key takeaways

A Queue<T> serves the oldest item first; its front and back move round a circular array, so Enqueue and Dequeue are O(1).
A Stack<T> gives back the newest item first, for undo histories and nested brackets.
A PriorityQueue<TElement,TPriority> serves the lowest priority value first from a min-heap in O(log n), with no order among equal priorities.
Choose a collection by the item your code needs next and the operations it repeats.

Terms in this lesson

circular array: An array used as a ring: the front and back positions move forward and wrap round to the start, so a queue adds and removes items without shifting any. Queue<T> is implemented this way.
FIFO: First in, first out: the order of a queue, which always gives back the item that has waited longest. A Queue<T> adds at the back with Enqueue and takes from the front with Dequeue.
LIFO: Last in, first out: the order of a stack, which always gives back the item added most recently. A Stack<T> adds with Push and takes with Pop, both at its top.
min-heap: A tree kept in an array in which every parent's priority is no larger than its children's, so the smallest is always at the root; adding an item or removing the smallest takes O(log n) steps.

References

Queue<T> class (Microsoft Learn)
Queue<T>.TrimExcess method (Microsoft Learn)
Stack<T> class (Microsoft Learn)
PriorityQueue<TElement,TPriority> class (Microsoft Learn)
PriorityQueue<TElement,TPriority>.Remove method (Microsoft Learn)
LinkedList<T> class (Microsoft Learn)
List<T>.Insert method (Microsoft Learn)
SortedDictionary<TKey,TValue> class (Microsoft Learn)
Collections and data structures (algorithmic complexity of collections) (Microsoft Learn)
Selecting a collection class (Microsoft Learn)

Report a problem with this lesson

In this module: Arrays and collections

Arrays, indices and ranges Free lesson, Pro answers: 15 minutes
Lists and collection expressions Free core, Pro depth: 8 of 20 minutes free
Dictionaries, sets and comparers Free core, Pro depth: 8 of 20 minutes free
Iterators: IEnumerable, yield and lazy sequences Free core, Pro depth: 7 of 20 minutes free
Read-only, immutable and frozen collections Free core, Pro depth: 7 of 20 minutes free
Queues, stacks and priority queues: how to choose Free core, Pro depth: 9 of 25 minutes free

What you will learn

Before you start

What you will learn

Before you start

A queue serves items in the order they arrived

A stack gives back the most recent item first

A priority queue serves the most urgent item first

Shortest routes with a priority queue Pro: opens with a Pro, Premium or Ultimate pass

A fair waiting list: equal priorities and cancellations Pro: opens with a Pro, Premium or Ultimate pass

Choosing any collection by its measured costs Pro: opens with a Pro, Premium or Ultimate pass

Practise: a token counter with priority tokens

Interview questions

You implement Dijkstra's shortest paths with PriorityQueue<TElement,TPriority>, and find that it has no way to lower the priority of an element it already holds. How do you handle a station whose best time improves, what does your approach cost, and when would you choose something else?

A waiting list uses PriorityQueue<Request, int> with the quota class as the priority. Two requests of the same class are sometimes served in the wrong order: the later one first. Why, and how do you fix it without losing O(log n) for each request?

A service buffers incoming messages in a Queue<Message>. After a traffic burst of 1,000,000 messages is drained, the process still uses far more memory than before the burst, although the queue is empty. Why, and what would you change?

Key takeaways

References