C# Queue, Stack, LinkedList and PriorityQueue: Collections That Work in Order

Version note: The code in this post uses C# 10 and the .NET 6 APIs; it was built and run with the .NET 10 SDK.

Guess First

We want to hand orders to the shipping service by priority: same-day delivery 0, express 1, standard 3. The smaller number goes first. We added five orders to the PriorityQueue that came with .NET 6 and listed what is inside with foreach. What order appears on the screen?

PriorityQueue<string, int> shipping = new();
shipping.Enqueue("Order 1001 (standard)", 3);
shipping.Enqueue("Order 1002 (express)", 1);
shipping.Enqueue("Order 1003 (standard)", 3);
shipping.Enqueue("Order 1004 (same day)", 0);
shipping.Enqueue("Order 1005 (express)", 1);

foreach ((string order, int priority) in shipping.UnorderedItems)
{
    Console.WriteLine($"{priority} {order}");
}

Why UnorderedItems Is Unordered

0 Order 1004 (same day)
3 Order 1001 (standard)
3 Order 1003 (standard)
1 Order 1002 (express)
1 Order 1005 (express)

The first line is right; the rest is mixed up. The property's name already warns you: UnorderedItems. PriorityQueue does not keep its elements sorted inside; it keeps a min-heap that lives on an array. A heap makes exactly one promise: the smallest priority is always on top. The rest only follows the rule "every parent is smaller than its children," which is not a full ordering. UnorderedItems shows you that array as it is.

Think of a hospital emergency room. The triage nurse does not line everyone in the waiting room up in order; she can only answer "who is the most urgent right now?" at any moment. If you want to process in order, you take the top one with Dequeue:

// shipping: the five-order queue from above
while (shipping.TryDequeue(out string? order, out int priority))
{
    Console.WriteLine($"{priority} {order}");
}

0 Order 1004 (same day)
1 Order 1005 (express)
1 Order 1002 (express)
3 Order 1003 (standard)
3 Order 1001 (standard)

The priorities are now in the right order. But look at the orders with equal priority: 1005 jumped ahead of 1002, which was placed before it, and 1003 ahead of 1001. PriorityQueue is not stable; it does not keep the insertion order of elements with the same priority. We will see how to fix that at the end of the post. First, let's look at two simpler members of this family.

Queue<T>: First In, First Out

Queue<string> orders = new();
orders.Enqueue("Order 1001");
orders.Enqueue("Order 1002");
orders.Enqueue("Order 1003");

Console.WriteLine($"Next: {orders.Peek()}, waiting: {orders.Count}");

while (orders.TryDequeue(out string? order))
{
    Console.WriteLine($"Processing {order}");
}

orders.Dequeue(); // empty queue: InvalidOperationException

Next: Order 1001, waiting: 3
Processing Order 1001
Processing Order 1002
Processing Order 1003
Unhandled exception. System.InvalidOperationException: Queue empty.

The line at the supermarket checkout: whoever arrives first is served first (FIFO, first in first out). Enqueue adds to the end, Dequeue takes from the front, and Peek looks without taking. On an empty queue, Dequeue and Peek throw; wherever it may be empty, use TryDequeue and TryPeek.

Taking from the front of a List<T> means RemoveAt(0), which shifts the whole list every time. Queue<T> uses its internal array as a ring: it keeps two indexes for the head and the tail and never moves elements around. Both Enqueue and Dequeue are O(1). It is the natural answer to "process them in the order they arrive," whether that means processing orders, sending emails, or the addresses a web crawler will visit.

Stack<T>: Last In, First Out

Think of a pile of plates; you take the last plate you put on top first (LIFO, last in first out). That is the undo feature itself:

List<string> cart = new();
Stack<string> history = new();

AddToCart("Dune");
AddToCart("Foundation");
AddToCart("1984");
Console.WriteLine($"Cart: {string.Join(", ", cart)}");

UndoLast();
UndoLast();
Console.WriteLine($"After two undos: {string.Join(", ", cart)}");

Stack<int> original = new(new[] { 1, 2, 3 });
Stack<int> copy = new(original);
Console.WriteLine($"Original: {string.Join(", ", original)} | copy: {string.Join(", ", copy)}");

void AddToCart(string title)
{
    cart.Add(title);
    history.Push(title);
}

void UndoLast()
{
    if (history.TryPop(out string? title))
    {
        cart.Remove(title);
        Console.WriteLine($"Undo: {title}");
    }
}

Cart: Dune, Foundation, 1984
Undo: 1984
Undo: Foundation
After two undos: Dune
Original: 3, 2, 1 | copy: 1, 2, 3

Push puts on top, Pop takes the top one, and Peek looks. All of them are O(1). Undo, the browser's "back" button, expression parsing, and turning a recursive algorithm into a loop are typical uses.

The last line is a trap. When you walk a Stack<T> with foreach, the elements come from top to bottom, that is, in Pop order: 3, 2, 1. new Stack<int>(original) walks original in that order and Pushes each one; the copy ends up reversed. If you want to copy a stack in the same order, you have to reverse it twice: new Stack<int>(original.Reverse()).

LinkedList<T>: Working with Nodes

LinkedList<string> readingList = new(new[] { "Dune", "Foundation", "1984" });

LinkedListNode<string> foundation = readingList.Find("Foundation")!;
readingList.AddAfter(foundation, "Hyperion");
readingList.AddFirst("The Hobbit");
readingList.Remove(foundation);

Console.WriteLine(string.Join(" -> ", readingList));
Console.WriteLine($"First: {readingList.First!.Value}, Last: {readingList.Last!.Value}, Count: {readingList.Count}");

The Hobbit -> Dune -> Hyperion -> 1984
First: The Hobbit, Last: 1984, Count: 4

LinkedList<T> is a doubly linked list. Every element lives inside a LinkedListNode<T>, and the node knows the one before it (Previous) and the one after it (Next). Like the cars of a train: to add a car in the middle you do not move the other cars, you only change two couplings. If you hold the node, AddAfter, AddBefore and Remove(node) are O(1); the head and tail of the list are always O(1) too.

But the price is high. There is no index; you cannot write readingList[2]. To find a value, Find walks from the start: O(n). Because every node is a separate object on the heap, nodes are scattered around memory, and modern CPU caches do not like that; in practice, walking a List<T> from start to end is usually faster than walking a LinkedList<T> with the same number of elements. Choose LinkedList<T> only when you hold on to the nodes and insert and remove in the middle often.

LinkedList and Dictionary: Recently Viewed Books

The classic way to meet that "hold on to the node" condition is to keep the nodes in a dictionary. The "three books you viewed last" box on a book page is exactly this, a small LRU (least recently used) cache:

RecentlyViewed recent = new(capacity: 3);
recent.Visit("Dune");
recent.Visit("Foundation");
recent.Visit("1984");
recent.Visit("Dune");
recent.Visit("The Hobbit");

Console.WriteLine(string.Join(" > ", recent.Items));

class RecentlyViewed
{
    private readonly int _capacity;
    private readonly LinkedList<string> _order = new();
    private readonly Dictionary<string, LinkedListNode<string>> _nodes = new();

    public RecentlyViewed(int capacity) => _capacity = capacity;

    public IEnumerable<string> Items => _order;

    public void Visit(string title)
    {
        if (_nodes.TryGetValue(title, out LinkedListNode<string>? node))
        {
            _order.Remove(node); // we hold the node: O(1)
            _order.AddFirst(node);
            return;
        }

        if (_order.Count == _capacity)
        {
            LinkedListNode<string> oldest = _order.Last!;
            _order.RemoveLast(); // the oldest: the end of the list
            _nodes.Remove(oldest.Value);
        }

        _nodes[title] = _order.AddFirst(title);
    }
}

The Hobbit > Dune > 1984

When Dune was viewed a second time, it moved to the front of the list. When The Hobbit came along, the capacity was full, so Foundation, the one not viewed for the longest time, was dropped. The dictionary answers "where is this book in the list?" in O(1), and the linked list takes that node out and puts it at the front in O(1). Neither collection can do this alone; together, every operation finishes in constant time.

PriorityQueue<TElement, TPriority> in Depth

Back to the start. PriorityQueue takes two type parameters: the element that goes into the queue and its priority. The priority is not part of the element itself; the same element can be added with different priorities. Enqueue and Dequeue are O(log n), and Peek is O(1). The way to fix the mix-up among equal priorities is to add a sequence number to the priority:

PriorityQueue<string, (int Priority, long Sequence)> shipping = new();
long sequence = 0;

Enqueue("Order 1001 (standard)", 3);
Enqueue("Order 1002 (express)", 1);
Enqueue("Order 1003 (standard)", 3);
Enqueue("Order 1004 (same day)", 0);
Enqueue("Order 1005 (express)", 1);

while (shipping.TryDequeue(out string? order, out (int Priority, long Sequence) key))
{
    Console.WriteLine($"{key.Priority} {order}");
}

void Enqueue(string order, int priority) => shipping.Enqueue(order, (priority, sequence++));

0 Order 1004 (same day)
1 Order 1002 (express)
1 Order 1005 (express)
3 Order 1001 (standard)
3 Order 1003 (standard)

Tuples are compared by their first field, and by the second one when the first is equal. If the priority is the same, the smaller sequence number, meaning the one that came first, wins. The queue is now "prioritized but fair."

By default the smaller one comes out first. If you want the larger one first, you pass a comparer. For questions like "the N most expensive books," the min-heap itself works in your favor:

using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

List<Book> books = new()
{
    new("Dune", 12.99m),
    new("Foundation", 9.50m),
    new("The Hobbit", 10.99m),
    new("1984", 8.99m),
    new("Brave New World", 11.49m),
    new("Hyperion", 14.25m),
};

PriorityQueue<Book, decimal> topThree = new();
foreach (Book book in books)
{
    if (topThree.Count < 3)
    {
        topThree.Enqueue(book, book.Price);
    }
    else
    {
        topThree.EnqueueDequeue(book, book.Price); // add, then drop the cheapest
    }
}

while (topThree.TryDequeue(out Book? book, out decimal price))
{
    Console.WriteLine($"{book.Title} {price}");
}

PriorityQueue<string, decimal> largestFirst = new(Comparer<decimal>.Create((x, y) => y.CompareTo(x)));
largestFirst.Enqueue("Order 2001", 25.00m);
largestFirst.Enqueue("Order 2002", 140.50m);
largestFirst.Enqueue("Order 2003", 61.75m);
Console.WriteLine($"Largest order first: {largestFirst.Dequeue()}");

record Book(string Title, decimal Price);

Brave New World 11.49
Dune 12.99
Hyperion 14.25
Largest order first: Order 2002

A three-slot min-heap holds the three most expensive books seen so far, with the cheapest of the three on top. Each new book is added with EnqueueDequeue, and the cheapest one is dropped. Sorting the whole list is O(n log n), while this approach is O(n log k) and keeps only k elements in memory. For jobs like finding "the 10 slowest requests" in a log with millions of lines, the difference is large.

One thing is missing: you cannot change the priority of an element already in the queue. The .NET 6 workaround is to add it once more with the new priority and skip the stale entries as you dequeue. .NET 9 brought a Remove method for this; we will come back to it in the version posts of the series.

Common Pitfalls

Thinking UnorderedItems is sorted. It is what its name says: the internal layout of the heap. If you want order, take items out with Dequeue.

Assuming PriorityQueue behaves FIFO for equal priorities. The output above showed the opposite. You provide the fairness yourself by adding a sequence number to the priority.

Using List<T> and RemoveAt(0) for a queue. Every removal shifts the whole list. Queue<T> does the same job in O(1).

Forgetting that copying a stack reverses it. new Stack<T>(stack) produces a reversed copy.

Choosing LinkedList<T> because "I will insert in the middle" without thinking it through. If you do not hold the node, you first do an O(n) search with Find and the gain is gone; on top of that, walking it is slow because of the scattered memory.

Calling Dequeue, Pop or Peek on an empty collection. All three throw InvalidOperationException. Use their counterparts that start with Try.

A Small Experiment

★☆☆ Add a redo feature to the cart example: keep the undone books in a second Stack<string> and put them back into the cart.

★★☆ Give RecentlyViewed a dictionary that matches book titles case-insensitively (StringComparer.OrdinalIgnoreCase from the previous post), and show that visiting "dune" moves "Dune" to the front.

★★★ Write a shipping queue whose priorities can change: keep the current priority of every order in a Dictionary<string, int>, Enqueue an order again when its priority changes, and skip stale entries whose priority does not match the dictionary while you Dequeue.

The collections in this post kept elements in insertion order or by priority. In the next post we move on to collections that always keep their contents sorted: SortedList, SortedDictionary, SortedSet, and IComparer<T>, which sets the sorting rule.