Queue, Stack and immutable collections

Queue: first in, first out

A queue is the collection of a waiting line: an element is added at the back and taken from the front, and the two operations are called Enqueue and Dequeue.

var queue = new Queue<string>(); queue.Enqueue("first"); queue.Enqueue("second"); Console.WriteLine(queue.Dequeue()); Console.WriteLine(queue.Peek()); Console.WriteLine(queue.Count);

dotnet run

first
second
1

Dequeue takes the element out, so the first line prints first and the queue is then one element shorter. Peek looks at the front without taking it out, which is why the second line still shows second and the count is 1.

A Dequeue or Peek on an empty queue throws InvalidOperationException. A program that may find the queue empty tests Count or TryDequeue, which returns a bool in the same shape as TryGetValue.

Stack: last in, first out

A stack is the other order: the element added last is the one taken first, and the operations are Push and Pop.

var stack = new Stack<int>(); stack.Push(1); stack.Push(2); Console.WriteLine(stack.Pop()); Console.WriteLine(stack.Peek()); Console.WriteLine(stack.Count);

dotnet run

2
1
1

The 2 came out first because it went in last. Peek then shows 1 without removing it, and one element is left. A stack is the right shape for anything nested: an undo history, a depth-first walk, the parentheses of an expression. The capstone B of this course uses one for the operators of its parser.

Both collections are implemented over an array that grows from the front or the back, so Enqueue and Push are cheap on average, and both are enumerable in their own order: a foreach over a stack walks from the top down.

The immutable collections

An ImmutableArray<T> or ImmutableDictionary<TKey, TValue> never changes: every operation that would modify it returns a new value and leaves the original as it was. They are in System.Collections.Immutable, which is part of the shared framework, so no package is needed.

using System.Collections.Immutable; var array = ImmutableArray.Create(1, 2, 3); var next = array.Add(4); Console.WriteLine($"{array.Length} {next.Length}"); Console.WriteLine(string.Join(",", next)); var map = ImmutableDictionary<string, int>.Empty.Add("a", 1); var bigger = map.Add("b", 2); Console.WriteLine($"{map.Count} {bigger.Count}"); Console.WriteLine(bigger["b"]);

dotnet run

3 4
1,2,3,4
1 2
2

array is still three elements after Add returned a four-element array, and map still holds one key after bigger gained a second. That is the whole point: a value that cannot change can be shared with another thread or another part of the program without a lock and without a copy.

The price is a new structure per change, and the implementations share almost all of the old one, so an update costs a little more than a mutation and far less than a copy. The immutable collections are the right choice for data that is read by many and changed rarely: configuration, a snapshot of a state, a cache of results.

Exercises

  1. Push the letters of a word onto a stack and pop them all. What does the output spell, and why?
  2. Enqueue three jobs and dequeue them in a loop until Count is 0. Which order do they run in?
  3. Call Pop on an empty stack inside a try and print the exception type.
  4. Add a value to an ImmutableArray, keep the original in a variable and print both lengths. Which one changed?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Which collection takes the element that was added first?

    Answer

    Queue

    A queue is first in, first out; a stack takes the most recent element, and the others promise no order.

  2. What does this program print? var queue = new Queue<int>(); queue.Enqueue(1); queue.Enqueue(2); Console.WriteLine(queue.Dequeue()); Console.WriteLine(queue.Count);

    Answer

    1 / 1

    The first element leaves the queue, so it prints 1 and one element is left.

  3. What does this program print? var stack = new Stack<string>(); stack.Push("a"); stack.Push("b"); Console.WriteLine(stack.Peek()); Console.WriteLine(stack.Count);

    Answer

    b / 2

    Peek reads the top without removing it, so the last pushed value shows and the count is unchanged.

  4. What happens on Dequeue of an empty queue?

    Answer

    InvalidOperationException

    The collection reports the misuse with an exception, which is why TryDequeue exists for the case a program expects.

  5. What does this program print? using System.Collections.Immutable; var array = ImmutableArray.Create(1, 2); var bigger = array.Add(3); Console.WriteLine(array.Length); Console.WriteLine(bigger.Length);

    Answer

    2 / 3

    Add returns a new array, so the original keeps two elements while the new value holds three.

  6. Which namespace holds the immutable collections?

    Answer

    System.Collections.Immutable

    The immutable types live in System.Collections.Immutable, an assembly of the shared framework.

  7. What does an ImmutableDictionary.Add return?

    Answer

    A new dictionary that holds the old pairs and the new one

    Every operation returns a new structure, so the caller decides which version to keep.

  8. What does this program print? var stack = new Stack<int>(); stack.Push(1); stack.Push(2); stack.Pop(); Console.WriteLine(stack.Peek());

    Answer

    1

    The Pop removed the 2, so the top is the 1 that was pushed first.

  9. Why can an immutable collection be shared without a lock?

    Answer

    No thread can change a value that exists, so a reader always sees a consistent one

    A value that never changes cannot be seen half-changed, so sharing it between threads needs no synchronisation.

  10. Which collection is the natural one for an undo history?

    Answer

    Stack

    Undo takes back the most recent action first, which is the last-in, first-out order of a stack.

The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev