C# Queue with Examples
A queue is a fundamental data structure that follows the First-In-First-Out (FIFO) principle. Similar to a queue or queue in real life, new objects are added at the back and removed away from the front. Programmers frequently utilize queues to handle requests, schedule jobs, and construct breadth-first search engines.
The Queue class in C# allows you to:
- Enqueue: Adds a component to the queue's end.
- Dequeue: Takes out and puts back in the queue the element that was at the front.
- Peek: Without deleting it, returns the element at the front of the queue.
- Count: Returns the total number of queued entries.
- Clear: Eliminates all queued components.
Creating a Queue
To create a new instance of a Queue in C#, the following syntax can be used:
Queue<T> queue = new Queue<T>();
The <T> represents the elements you want to store in the queue. Replace it with the desired data type, such as int, string, or a custom class.
Example for Creating an Empty Queue:
Queue<int> queue = new Queue<int>();
This creates an empty queue that can hold integers.
Example for Creating a Queue with Strings:
Queue<string> queue = new queue <string>(new[] { "apple", "banana", "mango" });
This creates a queue of strings with three initial elements: "apple", "banana", and "mango".
Enumerating and Iterating Elements in Queue
You can access and handle each queue element sequentially by enumerating and iterating. You can accomplish this in one of two ways: by developing a custom iterator or by utilizing a foreach loop.
1. Using foreach loop:
The foreach loop offers a practical method for repeatedly iterating through a Queue's components. It manages the internal structure of the queue without the need for explicit indexing and handles the process of accessing each entry automatically. Here's an illustration:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<string> queue = new Queue<string>();
// Enqueue elements to the queue
queue.Enqueue("Apple");
queue.Enqueue("Banana");
queue.Enqueue("Mango");
// Iterate and print each element in the queue
foreach (string fruit in queue)
{
Console.WriteLine(fruit);
}
// Dequeue elements from the queue
while (queue.Count > 0)
{
string dequeuedFruit = queue.Dequeue();
Console.WriteLine("Dequeued: " + dequeuedFruit);
}
}
}
Output:
The foreach loop in this example outputs each fruit to the console after iterating over the elements in the queue. Each element is automatically dequeued and assigned to the fruit variable by the loop.
2. Iterating with Custom Iterator
To iterate through the elements in a Queue, in addition to foreach, you can construct a custom iterator. This strategy gives you more power and freedom over the iteration process. Here is an example of how to implement a unique queue iterator:
using System;
using System.Collections;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<string> queue = new Queue<string>();
queue.Enqueue("Apple");
queue.Enqueue("Banana");
queue.Enqueue("Mango");
foreach (string fruit in CustomIterator(queue))
{
Console.WriteLine(fruit);
}
}
static IEnumerable<string> CustomIterator(Queue<string> queue)
{
while (queue.Count > 0)
{
yield return queue.Dequeue();
}
}
}
Output:
The CustomIterator method is defined in this code as a static method with a Queue<string> parameter. The method uses the yield return statement to return each queue item one at a time.
The CustomIterator method returns several elements, each being iterated in the foreach loop and reported to the console.
Utilizing the yield keyword to construct a custom iterator gives you more control over the iteration procedure and enables you to modify the logic or include more transformations as necessary.
Adding Elements to the Queue
To add elements to the queue, you can use the Enqueue method.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<int> queue = new Queue<int>();
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);
Console.WriteLine("Queue elements:");
while (queue.Count > 0)
{
int element = queue.Dequeue();
Console.WriteLine(element);
}
}
}
Output:
Accessing and Removing Elements from the Queue
The Queue class in C# provides methods to access and remove elements from the front of the queue. Let's explore two essential methods: Peek and Dequeue.
1. Peek method
You can access the element at the head of the queue using the Peek method without taking it out of the queue.
Example:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<string> queue = new Queue<string>();
queue.Enqueue("Apple");
queue.Enqueue("Banana");
queue.Enqueue("Mango");
string frontElement = queue.Peek();
Console.WriteLine("Front element: " + frontElement);
}
}
Output:
2. Dequeue method
The Dequeue method removes and returns the element at the front of the queue.
Example:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<string> queue = new Queue<string>();
queue.Enqueue("Apple");
queue.Enqueue("Banana");
queue.Enqueue("Mango");
string removedElement = queue.Dequeue();
Console.WriteLine("Removed element: " + removedElement);
}
}
Output:
Checking Queue Size
The Queue class also provides the Count property, which allows you to determine the number of elements in the queue.
Example:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<string> queue = new Queue<string>();
queue.Enqueue("Apple");
queue.Enqueue("Banana");
queue.Enqueue("Cherry");
int size = queue.Count;
Console.WriteLine("Queue size: " + size);
}
}
Output:
In this example, the Count property gets the number of elements in the queue, which is then printed to the console.
Checking if the Queue is Empty
Like the stack, multiple ways exist to check if a queue is empty in C#. You can use the Count property or check if the count is zero. The IsEmpty method is another option that directly checks whether the queue is empty without accessing the Count property.
Example:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<int> queue = new Queue<int>();
// Method 1: Using the Count property
if (queue.Count == 0)
{
Console.WriteLine("Queue is empty");
}
// Method 2: Checking if Count is 0
if (queue.Count == 0)
{
Console.WriteLine("Queue is empty");
}
}
}
Output:
In this example, we check if the queue's count is zero to see if it is empty. If the queue is empty, the message "Queue is empty" is printed.
Note: Depending on your programming preferences and needs, it's critical to apply the proper technique when determining if the stack or queue is empty. You will get the same outcome if you use the Count property or compare the count to zero.
Clearing the Queue
The Queue class in C# provides a convenient Clear method to remove all elements from a queue. This operation effectively clears the entire queue, making it empty.
Queue-clearing example:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<string> queue = new Queue<string>();
queue.Enqueue("Apple");
queue.Enqueue("Banana");
queue.Enqueue("Mango");
Console.WriteLine("Queue before clearing:");
foreach (string element in queue)
{
Console.WriteLine(element);
}
queue.Clear();
Console.WriteLine("Queue after clearing:");
if (queue.Count == 0)
{
Console.WriteLine("Queue is empty");
}
}
}
Output:
In the above example, we create a queue of strings, add elements to the queue using the Enqueue method, and then display the elements before clearing the queue. The queue becomes empty after calling the Clear method, as indicated by the output.
Modifying Elements:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<string> queue = new Queue<string>();
// Enqueue some elements
queue.Enqueue("Apple");
queue.Enqueue("Banana");
queue.Enqueue("Cherry");
// Display the initial queue
Console.WriteLine("Initial Queue:");
foreach (string fruit in queue)
{
Console.WriteLine(fruit);
}
// Modify an element at a specific position
string[] queueArray = queue.ToArray();
int indexToModify = 1; // Index of the element to modify
string modifiedElement = "Mango"; // New value for the modified element
queueArray[indexToModify] = modifiedElement;
queue = new Queue<string>(queueArray);
// Display the modified queue
Console.WriteLine("\nModified Queue:");
foreach (string fruit in queue)
{
Console.WriteLine(fruit);
}
}
}
Output:
In this example, "Apple," "Banana," and "Cherry" are three components that are enqueued into a Queue<string> with the name queue. The initial queue is then shown.
We use the ToArray() function to convert the queue to an array to change an element at an exact point. We supply the new value for the modified element (modifiedElement) and the index of the element to modify (indexToModify). We use the changed array to build a new queue after updating the array as necessary.
Sorting and Ordering in Queue
Like a SortedSet, the Queue data structure in C# does not naturally provide sorting and ordering. However, sorting and ordering in a queue can still be accomplished by utilizing extra data structures and operations. This enables you to process the elements based on specified criteria and in a particular sequence. Let's look into how we can make this happen.
Converting the queue to a List: One method is to convert the queue to a List or an array and then use the built-in sorting algorithms to arrange the contents. The sorted List or array can be used to construct a new queue after sorting. You can then process the components in the desired sequence as a result.
Example:
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
Queue<int> queue = new Queue<int>();
// Enqueue some elements
queue.Enqueue(5);
queue.Enqueue(2);
queue.Enqueue(8);
queue.Enqueue(3);
queue.Enqueue(1);
// Convert the queue to a List and sort it
List<int> sortedList = queue.ToList();
sortedList.Sort();
// Create a new queue from the sorted List
Queue<int> sortedQueue = new Queue<int>(sortedList);
// Dequeue and display the sorted elements
Console.WriteLine("Sorted Queue:");
while (sortedQueue.Count > 0)
{
int element = sortedQueue.Dequeue();
Console.WriteLine(element);
}
}
}
Output:
Using a Custom Comparer: Implementing a custom comparer that specifies the sorting criteria for the entries in the queue is an additional approach. You can set your standards for sorting the elements by giving the sorting algorithm a custom comparer. This enables greater flexibility in sorting and ranking according to particular needs.
Example:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<int> queue = new Queue<int>();
// Enqueue some elements
queue.Enqueue(5);
queue.Enqueue(2);
queue.Enqueue(8);
queue.Enqueue(3);
queue.Enqueue(1);
// Create a custom comparer for sorting the elements in descending order
Comparer<int> customComparer = Comparer<int>.Create((x, y) => y.CompareTo(x));
// Convert the queue to a List and sort it using the custom comparer
List<int> sortedList = new List<int>(queue);
sortedList.Sort(customComparer);
// Create a new queue from the sorted List
Queue<int> sortedQueue = new Queue<int>(sortedList);
// Dequeue and display the sorted elements
Console.WriteLine("Sorted Queue:");
while (sortedQueue.Count > 0)
{
int element = sortedQueue.Dequeue();
Console.WriteLine(element);
}
}
}
Output:
Creating a Priority Queue: In a priority queue, a priority value is given to each element in the queue. The elements are then handled following their priorities, enabling bespoke ordering. You can manage the processing order and arrive at the appropriate sorting by giving the queue's elements precedence.
Example:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Create a priority queue using SortedDictionary<TKey, TValue>
SortedDictionary<int, string> priorityQueue = new SortedDictionary<int, string>();
// Enqueue elements with priorities
priorityQueue.Add(3, "Apple");
priorityQueue.Add(1, "Banana");
priorityQueue.Add(2, "Cherry");
//process the elements based on their priority (ascending order)
foreach (KeyValuePair<int, string> item in priorityQueue)
{
Console.WriteLine(item.Value);
}
}
}
Output:
Adding Sorted Elements: As an alternative, you can add elements to the queue by comparing them to already-existing elements in a sorted way. You can loop through the currently-queued elements each time you enqueue an element to choose the best location for insertion. Thanks to this technique, the elements will be added to the queue in the desired sequence.
Example:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
Queue<int> sortedQueue = new Queue<int>();
// Enqueue elements in a sorted manner
AddSorted(sortedQueue, 5);
AddSorted(sortedQueue, 2);
AddSorted(sortedQueue, 8);
AddSorted(sortedQueue, 3);
AddSorted(sortedQueue, 1);
// Process the elements in the sorted queue
while (sortedQueue.Count > 0)
{
int element = sortedQueue.Dequeue();
Console.WriteLine(element);
}
}
static void AddSorted(Queue<int> queue, int element)
{
Queue<int> tempQueue = new Queue<int>();
while (queue.Count > 0 && queue.Peek() < element)
{
tempQueue.Enqueue(queue.Dequeue());
}
tempQueue.Enqueue(element);
while (queue.Count > 0)
{
tempQueue.Enqueue(queue.Dequeue());
}
queue.Clear();
while (tempQueue.Count > 0)
{
queue.Enqueue(tempQueue.Dequeue());
}
}
}
Output:
Performance and Time Complexity
Performance: Depending on the particular implementation and the tasks being carried out, the performance of a queue implementation can change. Take into account the anticipated workload, as well as how frequently enqueuing, dequeuing, and peeking operations occur. For some usage conditions, several implementations offer more excellent performance characteristics.
Time Complexity: Considering how time-intensive standard queue operations are is crucial. Most queue operations, including Enqueue, Dequeue, and Peek, have an O(1) (constant time) time complexity, meaning they execute in constant time regardless of how many elements are in the queue. When working with certain queue implementations, it's crucial to be aware of any potential changes in temporal complexity.
Applications
Process Scheduling: Algorithms for process scheduling, such as First-Come, First-Served (FCFS), Round Robin, and Priority Scheduling, frequently employ queues. The queue aids in controlling the execution order of processes, guaranteeing fairness and effective resource allocation.
Event handling: Queues are frequently used in event-driven programming and event handling. To ensure they are treated in the order they happened, events can be enqueued in a queue and processed individually.
Message Queues: Queues are used in messaging systems to store and manage messages between various components or systems. Asynchronous and dependable communication is made possible by processing messages by the receiving component after they have been enqueued in a queue.
Task Processing: Queues are employed in task processing systems when several tasks or jobs must be completed in a particular sequence. Worker threads or processes pick up tasks from a queue and carry them out one at a time.
Breadth-First-Search: Queues are a crucial component of the Breadth-First Search algorithm, used to navigate or search across data structures resembling trees or graphs. By guaranteeing that nodes or vertices are explored in breadth-first order, the queue aids in maintaining the exploration order.