Is Queue thread safe in C#?

No. Two threads calling Enqueue or Dequeue on the same Queue at once can corrupt it. Use ConcurrentQueue from System.Collections.Concurrent, whose Enqueue and TryDequeue are safe to call from many threads, or wrap every access to a normal queue in a lock.

Runnable C# Docs: Queue

Q: What is a Queue in C#?

Queue in System.Collections.Generic is a first in, first out (FIFO) collection. Enqueue adds an item at the back, Dequeue removes and returns the item at the front, and Peek returns the front item without removing it. All three take constant time.

Q: What happens when you Dequeue an empty queue in C#?

Dequeue and Peek on an empty queue throw InvalidOperationException. Check queue.Count > 0 first, or use TryDequeue(out var item) and TryPeek(out var item), which return false instead of throwing (available since .NET Core 2.0).

Q: What is the difference between Peek and Dequeue?

Peek returns the item at the front and leaves it in the queue, so calling it twice returns the same item. Dequeue returns the front item and removes it, so the next call returns the item behind it.

Q: Why use a Queue instead of a List?

Removing the first item of a List with RemoveAt(0) shifts every other item, so it gets slower as the list grows. A Queue removes from the front in constant time, and its API states the intent: items are processed in arrival order.

A Queue<T> works like a line at a counter: the first item added is the first one taken out (FIFO, first in, first out). You add at the back with Enqueue and take from the front with Dequeue, both in constant time.

Enqueue, Dequeue and Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var printJobs = new Queue<string>();
        printJobs.Enqueue("invoice.pdf");
        printJobs.Enqueue("photo.png");
        printJobs.Enqueue("report.docx");

        Console.WriteLine("Waiting: " + printJobs.Count);
        Console.WriteLine("Next up: " + printJobs.Peek()); // look, do not remove

        string job = printJobs.Dequeue();                   // remove the front
        Console.WriteLine("Printing " + job);
        Console.WriteLine("Next up: " + printJobs.Peek());

        while (printJobs.Count > 0)
        {
            Console.WriteLine("Printing " + printJobs.Dequeue());
        }
        Console.WriteLine("Waiting: " + printJobs.Count);
    }
}

Output:

Waiting: 3
Next up: invoice.pdf
Printing invoice.pdf
Next up: photo.png
Printing photo.png
Printing report.docx
Waiting: 0

Peek is for deciding what to do with the next item before committing to it; Dequeue commits. The while (queue.Count > 0) loop that dequeues until empty is the standard way to process a queue, and it keeps working if the loop body enqueues more items, which a foreach does not allow.

The empty queue exception and TryDequeue

Dequeue and Peek on an empty queue throw InvalidOperationException. There is no "null when empty" behavior, even for reference types.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tickets = new Queue<int>();

        try
        {
            tickets.Dequeue();
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        tickets.Enqueue(41);
        tickets.Enqueue(42);

        int ticket;
        while (tickets.TryDequeue(out ticket))
        {
            Console.WriteLine("Serving ticket " + ticket);
        }

        Console.WriteLine(tickets.TryPeek(out ticket)); // false: empty
    }
}

Output:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue and TryPeek return true and set the out variable when there is an item, and return false when the queue is empty. They arrived in .NET Core 2.0; on older .NET Framework code, check Count > 0 before calling Dequeue.

Looking inside a queue

A queue can be enumerated without removing anything. foreach, ToArray and Contains all see the items from front to back.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var line = new Queue<string>(new[] { "Ana", "Ben", "Chloe" });

        foreach (string name in line)
        {
            Console.Write(name + " ");
        }
        Console.WriteLine();

        Console.WriteLine(line.Contains("Ben"));
        string[] snapshot = line.ToArray();
        Console.WriteLine(snapshot[0] + " is first, " + snapshot.Length + " in line");
        Console.WriteLine(line.Count); // nothing was removed
    }
}

Output:

Ana Ben Chloe 
True
Ana is first, 3 in line
3

There is no index: line[1] does not compile, and you cannot remove an item from the middle. If you need either, the data is not really a queue; use a List<T> or a LinkedList<T>. As with other collections, enqueuing or dequeuing inside a foreach over the same queue throws InvalidOperationException.

Breadth first search with a queue

The queue's ordering is exactly what breadth first search needs: visit everything one step away, then everything two steps away, and so on. Here it finds how many connections separate Ana from everyone else in a small network:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var friends = new Dictionary<string, string[]>
        {
            ["Ana"] = new[] { "Ben", "Chloe" },
            ["Ben"] = new[] { "Ana", "Dev" },
            ["Chloe"] = new[] { "Ana", "Dev", "Eli" },
            ["Dev"] = new[] { "Ben", "Chloe", "Fay" },
            ["Eli"] = new[] { "Chloe" },
            ["Fay"] = new[] { "Dev" },
        };

        var distance = new Dictionary<string, int> { ["Ana"] = 0 };
        var queue = new Queue<string>();
        queue.Enqueue("Ana");

        while (queue.Count > 0)
        {
            string person = queue.Dequeue();
            foreach (string next in friends[person])
            {
                if (!distance.ContainsKey(next))
                {
                    distance[next] = distance[person] + 1;
                    queue.Enqueue(next);
                }
            }
        }

        foreach (var pair in distance)
        {
            Console.WriteLine(pair.Key + ": " + pair.Value + " step(s) from Ana");
        }
    }
}

Output:

Ana: 0 step(s) from Ana
Ben: 1 step(s) from Ana
Chloe: 1 step(s) from Ana
Dev: 2 step(s) from Ana
Eli: 2 step(s) from Ana
Fay: 3 step(s) from Ana

Each person is enqueued once, the first time they are reached, and because the queue hands them back in the order they were found, the first time is always along a shortest path. Swap the queue for a Stack and the same loop becomes depth first search, which no longer finds shortest paths.

The same shape handles level order traversal of a tree, flood fill on a grid, and crawling links: start with one item in the queue, and while it is not empty, dequeue one and enqueue its unvisited neighbors.

Queue vs List for FIFO work

You can use a List<T> as a queue with Add and RemoveAt(0), but RemoveAt(0) shifts every remaining element down one slot. Draining a list of 100,000 items that way does about five billion element moves; a Queue<T> does 100,000 constant time steps. Internally a queue is a circular buffer: it tracks a head and a tail index into an array and only reallocates when full.

Operation	`Queue<T>`	`List<T>` used as a queue
Add at back	`Enqueue`, O(1)	`Add`, O(1)
Remove from front	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
Look at front	`Peek`	`list[0]`
Index access	Not available	`list[i]`

ConcurrentQueue for multiple threads

Queue<T> is not thread safe. When several threads add or take items, use ConcurrentQueue<T> from System.Collections.Concurrent. It has Enqueue, TryDequeue and TryPeek but no Dequeue, because with other threads around, "check Count then Dequeue" could fail between the two calls.

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        var events = new ConcurrentQueue<int>();

        // 4 parallel iterations each add 1,000 items.
        Parallel.For(0, 4, worker =>
        {
            for (int i = 0; i < 1000; i++) events.Enqueue(i);
        });
        Console.WriteLine(events.Count);

        int total = 0;
        int item;
        while (events.TryDequeue(out item)) total++;
        Console.WriteLine(total + " processed");
    }
}

Output:

4000
4000 processed

With a plain Queue<T> in place of ConcurrentQueue<T>, the count would come out wrong or the program would throw, depending on timing. For producer and consumer threads that should wait for work instead of spinning, BlockingCollection<T> (which wraps a ConcurrentQueue<T> by default) or System.Threading.Channels adds blocking and completion. See lock for protecting a normal collection by hand.

PriorityQueue

When items should leave by priority rather than arrival order (the most urgent ticket first, the shortest path so far in Dijkstra's algorithm), .NET 6 and later provide PriorityQueue<TElement, TPriority>. The lowest priority value comes out first:

var triage = new PriorityQueue<string, int>();
triage.Enqueue("sprained ankle", 3);
triage.Enqueue("chest pain", 1);
triage.Enqueue("headache", 5);

while (triage.TryDequeue(out string patient, out int priority))
{
    Console.WriteLine($"{priority}: {patient}");
}
// 1: chest pain
// 3: sprained ankle
// 5: headache

Items with equal priority can come out in any order; add a sequence number to the priority if arrival order must break ties.

Common mistakes

Dequeuing without checking. An empty queue throws InvalidOperationException; loop on Count > 0 or use TryDequeue.
Calling Peek and expecting the item to be gone. Only Dequeue removes.
Enqueuing inside foreach over the queue. Throws; process with a while loop instead.
Sharing a Queue<T> between threads. Use ConcurrentQueue<T> or a lock.
Using List.RemoveAt(0) as a queue on large data. Each call is O(n).

Frequently Asked Questions

What is a Queue in C#?

Queue<T> in System.Collections.Generic is a first in, first out (FIFO) collection. Enqueue adds an item at the back, Dequeue removes and returns the item at the front, and Peek returns the front item without removing it. All three take constant time.

What happens when you Dequeue an empty queue in C#?

Dequeue and Peek on an empty queue throw InvalidOperationException. Check queue.Count > 0 first, or use TryDequeue(out var item) and TryPeek(out var item), which return false instead of throwing (available since .NET Core 2.0).

What is the difference between Peek and Dequeue?

Peek returns the item at the front and leaves it in the queue, so calling it twice returns the same item. Dequeue returns the front item and removes it, so the next call returns the item behind it.

Is Queue<T> thread safe in C#?

No. Two threads calling Enqueue or Dequeue on the same Queue<T> at once can corrupt it. Use ConcurrentQueue<T> from System.Collections.Concurrent, whose Enqueue and TryDequeue are safe to call from many threads, or wrap every access to a normal queue in a lock.

Why use a Queue instead of a List?

Removing the first item of a List<T> with RemoveAt(0) shifts every other item, so it gets slower as the list grows. A Queue<T> removes from the front in constant time, and its API states the intent: items are processed in arrival order.

Related concepts