Queue in C#

Queue in C# is a very useful collection for the data which we need to handle with first-in, first-out order. In this article, we are going to cover the main concepts of Queues in C#.

Let’s start.

What Is Queue in C#?

Queue in C# is one of the many collection types available to us. The main characteristic of Queues is that they serve items using the FIFO principle. FIFO represents a first-in, first-out style of serving elements.

Let’s imagine some real-life situations. There are several people in a queue in the bank. The first person who came is the first in the queue and will be served first. Then the second person can come to the cashier. First come, first served.

Another example might be food preparation in a restaurant. A cook will prepare ice cream for the customer who ordered earlier and is the first in the queue of orders.

Queue in C# works similarly. If we want to get an item from the queue, we’re going to get the one that was added first:

Non-generic and Generic Queues

We have the opportunity to use two types of Queues – non-generic and generic queues.

Non-generic Queue can be found in the System.Collections namespace. It is a collection of objects of different types.

Let’s create a non-generic Queue:
public Queue Items = new Queue();

Generic Queue can be found in System.Collections.Generic namespace. When we declare a generic Queue, we specify the type of items we want to store in it.

For example, let’s create an example queue that contains string values:
Queue<string> names = new Queue<string>();

And the one that contains int values:
Queue<int> orderNumbers = new Queue<int>();

Generic vs Non-generic Queues 

Since we can put any type in non-generic Queues they are not type-safe and thus error-prone. So, if we don’t need different types of elements in our Queue, it’s better to use a generic queue and avoid extra boxing and unboxing operations as well.

Queue Constructors

Non-generic Queue has four overloaded constructors to create a queue. Generic Queue has three constructors.

The first one is a parameterless constructor, which we have already used in the previous section. 

The second constructor creates a queue from a collection. Let’s use a list to create non-generic and generic queues:

List<int> numbers = new List<int>() { 3, 2, 4 };
Queue numbersNonGenericQueue = new Queue(numbers);
Queue<int> numbersGenericQueue = new Queue<int>(numbers);

The third constructor allows us to define a queue capacity by ourselves. The capacity is the number of elements that can be added to the queue. When we create a queue it has a default capacity, but when we add elements and the capacity is not enough, it is increased twice. This is an automatic process.

Let’s create queues that can hold five elements:

Queue nonGenericQueue = new Queue(5);
Queue<int> genericQueue = new Queue<int>(5);

When we add six elements, the capacity will become ten. If we are not going to add more elements, we can decrease the capacity.

The non-generic queue can decrease a capacity with TrimToSize method:

nonGenericQueue.TrimToSize();

The TrimToSize method reduces the capacity to the actual number of elements in the queue.

We can use the TrimExcess method to decrease the capacity of generic queues:

genericQueue.TrimExcess();

The TrimExcess method reduces the capacity to the actual number of elements if that number is less than ninety percent of the current capacity.

The non-generic method has one more constructor which can define a capacity and a growth factor as well. A growth factor is a number by which the current capacity is increased. The default growth factor is two. Regardless of the growth factor, the minimum number of increments is four. 

Let’s create a non-generic queue and define a capacity and a growth factor:

public Queue Items = new Queue(3, 10);

When the queue number becomes four, the new capacity will be thirty (3 x 10).

Adding Elements To Queue

Firstly, let’s use our non-generic Items queue and add several elements to it. To add elements in the queue, we should use the Enqueue() method:

Items.Enqueue("Hello");
Items.Enqueue(1);
Items.Enqueue(new int[] { 2, 4, 6 });

We can see that the Items queue can hold any type of element.

Now, it’s time to add elements into the generic queue. Let’s create a class called Order with a few simple properties and then declare order queue and add orders into it:

public class Order
{
    public string ClientName { get; set; } 
    public string[] ProductNames { get; set; } 
    public int TotalPrice { get; set; }
    
    public Order(string clientName, string[] productNames, int totalPrice) =>
        (ClientName, ProductNames, TotalPrice) = (clientName, productNames, totalPrice);
}

Now, we can create an order queue. We should use the Queue class with the Order type:

public Queue<Order> Orders = new Queue<Order>();

Let’s create several orders and add them to the queue:

var order1 = new Order("Ana", new string[] { "Chockolate", "Coffee" }, 20);
var order2 = new Order("George", new string[] { "Juice", "Sandwich" }, 15);
var order3 = new Order("Bob", new string[] { "Ice cream" }, 5);

Orders.Enqueue(order1);
Orders.Enqueue(order2);
Orders.Enqueue(order3);

Unlike the non-generic Items queue, the Orders queue can handle only the Order type elements.

Getting And Removing Elements From Queue

There are two methods we can use to get the first item, Dequeue() and Peek(). The Dequeue() method retrieves and removes the first item from a Queue while the Peek() method doesn’t remove an item.

Let’s try using Dequeue() and Peek() and keep eye on the number of elements:

Console.WriteLine($"Number of orders: {Orders.Count()}");

var firstRemovedOrder = Orders.Dequeue();
Console.WriteLine($"Dequeue the first order. Client: {firstRemovedOrder.ClientName}. Remaining orders: {Orders.Count()}");

var firstOrder = Orders.Peek();
Console.WriteLine($"Peek the first order. Client: {firstOrder.ClientName}. Remaining orders: {Orders.Count()}");

And we can see the result:

Number of orders: 3
Dequeue the first order. Client: Ana. Remaining orders: 2
Peek the first order. Client: George. Remaining orders: 2

We can use  Clear() method to remove all the elements at the same time:

Orders.Clear();
Console.WriteLine($"Number of orders: {Orders.Count()}"); // Number of orders: 0

As we expected, the number of elements is zero and the Queue is empty.

If we’d like to get the elements other than the first one, we can enumerate the queue as we do for other collections:

public static int? GetOrderTotalPriceByClient(string clientName)
{
    foreach(var order in Orders)
    {
        if (order.ClientName == clientName) 
            return order.TotalPrice;
    }
    return null;
}

Let’s call GetOrderTotalPriceByClient method now:

Console.WriteLine($"Order total price: {GetOrderTotalPriceByClient("Bob")}"); //Order total price: 5

How to Convert Queue to Other Collections

It’s possible to create different collections from queues. Let’s discuss a few collections we can convert Queue to.

Convert Queue To List

The ToList method helps us to create a list from a queue:

List<Order> ordersList = Orders.ToList();

If we need to have a read-only list, we can use ToImmutableList method:

ImmutableList<Order> ordersList = Orders.ToImmutableList<Order>();

Convert Queue To Array

Queue elements can be copied to an array using CopyTo method.

We can create the Order array and copy the Queue elements beginning at the specified index of the destination array:

Order[] ordersArray = new Order[Orders.Count];
Orders.CopyTo(ordersArray, 0);

Also, it is possible to create a new array with ToArray() method:

Order[] ordersArray = Orders.ToArray();

We can use ToImmutableArray method and create the immutable array:

ImmutableArray<Order> ordersImmutableArray = Orders.ToImmutableArray<Order>();

ordersImmutableArray is read-only, so it is not possible to change its elements after the creation.

Queue To Dictionary

In order to create a dictionary from a queue, we can use ToDictionary method.

Let’s assume that Order has a unique ClientName and define it as a key of a dictionary:

Dictionary<string, Order> ordersDictionary = Orders.ToDictionary(x => x.ClientName, x => x);

Thread Safety In Queues

Sometimes we need to use more than one thread. These threads may read, update or delete the same objects at the same time and that might be problematic. We are not guaranteed to control the object’s state properly and get the expected behavior at the end. 

In order to ensure thread safety for non-generic queues, we should use the Synchronized wrapper method of the Queue class.

Let’s create a new synchronized queue SynchronizedItems from our Items queue and check thread safety:

Queue synchronizedItems = Queue.Synchronized(Items);
Console.WriteLine($"Items is thread safe: {Items.IsSynchronized}"); //Items is thread safe: False
Console.WriteLine($"SynchronizedItems is thread safe: {synchronizedItems.IsSynchronized}"); //SynchronizedItems is thread safe: True

If we need to create a thread-safe generic queue, we should use ConcurrentQueue class instead of Queue.  ConcurrentQueue class is located in System.Collections.Concurrent namespace.

Let’s create a thread-safe Order queue:

ConcurrentQueue<Order> concurrentOrders = new ConcurrentQueue<Order>();

Priority Queues

Since C# 10, we can use a new generic class PriorityQueue. When the PriorityQueue object is declared, we should pass a type of the element and type of the priority, which defines the sorting of elements in the queue.

Let’s create the Order queue with int sorting priority and enqueue the orders with desired priority:

PriorityQueue<Order, int> priorityOrders = new PriorityQueue<Order, int>();

var order1 = new Order("Ana", new string[] { "Chockolate", "Coffee" }, 20);
var order2 = new Order("George", new string[] { "Juice", "Sandwich" }, 15);
var order3 = new Order("Bob", new string[] { "Ice cream" }, 5);

priorityOrders.Enqueue(order1, 2);
priorityOrders.Enqueue(order2, 1);
priorityOrders.Enqueue(order3, 3);

Console.WriteLine($"First client is {priorityOrders.Peek().ClientName}"); //First client is George

We can see, that “George” is the first item in the queue.

Now, let’s create one more Order queue with the string sorting priority:

PriorityQueue<Order, string> priorityOrders = new PriorityQueue<Order, string>();

priorityOrders.Enqueue(order1, "C");
priorityOrders.Enqueue(order2, "AA");
priorityOrders.Enqueue(order3, "A");

Console.WriteLine($"First client is {priorityOrders.Peek().ClientName}"); //First client is Bob

As we expected, “Bob” is the first in the queue now.

Conclusion

In this article, we have learned what Queue in C# is, how to save, get and remove elements from Queue, how to implement thread-safe queues in C#. Also, we have gone through some priority queue examples.