Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 182 ยท Collections

Stack, Queue, LinkedList and PriorityQueue

Learn the C# collections for ordering work - Stack (LIFO), Queue (FIFO), LinkedList nodes and PriorityQueue - with Peek, TryPeek, BFS, undo history and task scheduling examples.

Lists and arrays let you reach any item by its position. But many real problems do not need that. They need a very specific rule about which item comes out next. A print queue serves documents in the order they arrived. An "undo" button reverses the most recent change first. An emergency room treats the most urgent patient first, no matter who arrived earlier.

.NET ships a small collection for each of these rules: Stack<T> for last-in, first-out; Queue<T> for first-in, first-out; PriorityQueue<TElement, TPriority> for most-urgent-first; and LinkedList<T> for cheap insertion and removal in the middle. This lesson teaches each one with the pattern it is made for, the methods that are easy to get wrong (Peek versus TryPeek), and when to prefer a plain List<T> instead.

Stack: last in, first out

Picture a stack of plates. You put a new plate on top and you take the top plate off. You never pull one from the middle. A Stack<T> works the same way: Push adds to the top, Pop removes and returns the top, and Peek looks at the top without removing it.

C# Push, Peek and Pop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The last item pushed (red) is the first one popped. Enumerating a stack with foreach also goes from top to bottom, so it shows the pop order without removing anything.

Peek and Pop on an empty collection

Pop() and Peek() throw InvalidOperationException when the stack is empty. That is a perfectly good design when an empty stack means your program has a bug, and a nuisance when it just means "nothing left". For the second case, use TryPop and TryPeek, which return a bool and an out value:

C# TryPop and TryPeek

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

When TryPop fails, the out variable holds default (here 0). Always check the returned bool first. See methods and out parameters for how out works.

Where stacks shine

Stacks suit anything that must be undone in reverse order: undo history, backtracking, the call stack itself, and matching brackets. Here is a bracket checker that uses a stack to make sure every opening symbol is closed by the right partner, in the right order.

C# Balanced brackets with a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The most recent unclosed bracket must be the first one closed, which is exactly the LIFO rule.

Queue: first in, first out

A queue is a line at a shop. People join at the back (Enqueue) and are served from the front (Dequeue). Peek looks at the front. The same TryDequeue and TryPeek variants exist for empty queues.

C# A support-ticket queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Use TryDequeue in a while loop like this when the queue may also be filled while you drain it: the loop ends the moment the queue is empty, with no separate Count check.

Breadth-first search (BFS) explores a graph level by level: all neighbours first, then their neighbours. A queue gives it this order automatically, because items discovered earlier are processed earlier. Compare this with the stack-based depth-first search in HashSet, SortedSet and Set Operations.

C# Shortest path with BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

TryAdd plays the role of the "visited" set: it only succeeds the first time we reach a place. Because a queue visits nearer places first, the first time we reach Office is along a shortest route.

How they are built

Both Stack<T> and Queue<T> store items in an array that grows when it fills. Push and Enqueue are O(1) on average (occasionally the array is copied into a bigger one). A queue uses a circular buffer with a head and a tail index, so Dequeue does not shift the remaining items: it just moves the head. This is why you should not use List<T>.RemoveAt(0) as a queue. That call shifts every remaining item and costs O(n), so a loop that drains a list of a million items from the front takes quadratic time.

Operation Stack Queue
Add Push, O(1) amortized Enqueue, O(1) amortized
Remove Pop, O(1) Dequeue, O(1)
Look Peek, O(1) Peek, O(1)
Contains O(n) O(n)
Index access not supported not supported

LinkedList: a chain of nodes

LinkedList<T> is a doubly linked list. Each item lives in its own LinkedListNode<T> object with Previous and Next references. Because nodes are connected by references, you can insert or remove next to a node you already hold in O(1), without shifting anything.

C# Working with LinkedListNode

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

AddAfter and AddBefore return the new node, so you can keep a handle and use it later. First and Last are null when the list is empty, hence the ! (the null-forgiving operator) on a list we know is not empty.

Why you probably want List instead

A linked list sounds ideal for insertion, but in practice it is rarely the fastest choice in .NET. Every node is a separate heap object, so items are scattered in memory, the CPU cache works poorly, and each item carries about 24 bytes of overhead (two references plus an object header). Contains and finding the n-th item are O(n), and there is no indexer at all. A List<T> that inserts in the middle moves memory in one fast block copy, and wins for most sizes you will meet.

Reach for LinkedList<T> when you hold nodes and do many insertions or removals around them, for example an LRU cache that moves a node to the front on each access. Otherwise use List<T>, Queue<T> or Deque-style logic built on them.

PriorityQueue: the most urgent first

PriorityQueue<TElement, TPriority> (added in .NET 6) hands out items in priority order instead of arrival order. Each item is stored together with a priority; Dequeue returns the element with the smallest priority value by default, so it is a min-heap. A lower number means "more urgent".

C# Dequeue returns the smallest priority

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The heap keeps the smallest priority at the root. Enqueue and Dequeue are O(log n), Peek is O(1). Internally it is an array, so iteration order is not sorted; only Dequeue gives you ordered output. Do not enumerate a priority queue and expect priority order.

To get the largest first, pass a comparer that reverses the order:

C# Max-priority and a scheduler

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Tuples compare element by element, so (1, 1) comes before (1, 2). This makes tuple priorities a neat way to break ties.

PriorityQueue is not stable. Two elements with the same priority may be dequeued in any order, not necessarily the order you enqueued them. If order among equals matters, add a running counter to the priority, for example (priority, sequenceNumber).

There is no built-in way to change the priority of an item already inside, or to remove an arbitrary item. The usual workaround is to enqueue the item again with its new priority and skip the stale copy when it surfaces. Dijkstra's shortest-path algorithm uses exactly this trick.

Choosing between them

You need Use
Undo, backtracking, reversing, parsing nested things Stack<T>
Fair processing in arrival order, BFS, buffering work Queue<T>
Always process the most urgent or cheapest item next PriorityQueue<TElement, TPriority>
Many inserts/removals next to nodes you already hold LinkedList<T>
Random access by index, or insertion in the middle of small data List<T>

None of these types is thread-safe. If several threads share a queue or stack, use ConcurrentQueue<T>, ConcurrentStack<T> or a Channel<T>; see Choosing the Right Collection for a preview.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. You push 1, 2, 3 onto a Stack<int> and then call Pop() once. What is returned?

    A stack is last-in, first-out, so the most recently pushed item (3) comes out first.
  2. 2. Which call should you use to take the next item from a Queue<T> that might be empty, without risking an exception?

    TryDequeue returns false instead of throwing InvalidOperationException when the queue is empty.
  3. 3. Why is List<T>.RemoveAt(0) a poor way to implement a queue?

    Queue<T> uses a circular buffer and moves a head index, making Dequeue O(1). RemoveAt(0) copies all the other items down one slot.
  4. 4. A PriorityQueue<string, int> contains tasks with priorities 5, 1 and 3. Which is dequeued first by default?

    The default is a min-heap: the smallest priority value is the most urgent and comes out first.
  5. 5. Which statement about PriorityQueue is true?

    The heap is only partially ordered, so foreach does not give sorted output, and ties may come out in any order. Add a sequence number to the priority to break ties.

Summary

  • Stack<T> is last-in, first-out: Push, Pop, Peek; use it for undo, backtracking and matching nested structures.
  • Queue<T> is first-in, first-out: Enqueue, Dequeue, Peek; use it for fair processing and breadth-first search.
  • Pop, Peek and Dequeue throw on an empty collection; TryPop, TryPeek and TryDequeue return false instead.
  • Do not use List<T>.RemoveAt(0) as a queue; it is O(n).
  • LinkedList<T> gives O(1) insert and remove next to a node you hold, but costs memory and cache speed; prefer List<T> by default.
  • PriorityQueue<TElement, TPriority> is a min-heap with O(log n) Enqueue and Dequeue; it is unstable and not sorted when enumerated.
  • None of these collections is thread-safe.

Next: SortedDictionary, SortedList and Ordering