Queues and Deques in C#

Welcome to our exploration of queues and deques. These structures frequently surface in everyday programming, managing everything from system processes to printer queues. In this lesson, our goal is to understand and implement queues and deques in C#. Let's dive in!

A queue, similar to waiting in line at a store, operates on the "First In, First Out" or FIFO principle. C#'s Queue<T> class enables the implementation of queues. This class includes methods such as Enqueue() for adding items and Dequeue() for removing items.

using System;
using System.Collections.Generic;

// Create a queue and add items
Queue<string> q = new Queue<string>();
q.Enqueue("Apple");
q.Enqueue("Banana");
q.Enqueue("Cherry");

// Remove an item
Console.WriteLine(q.Dequeue());  // Expects "Apple"

The dequeued item, "Apple", was the first item we inserted, demonstrating the FIFO principle of queues.

Before trying to remove items from our queue, let's ensure it is not empty. This precaution will prevent runtime errors when attempting to dequeue from an empty queue.

using System;
using System.Collections.Generic;
using System.Linq;

// Create a queue and enqueue items
Queue<string> q = new Queue<string>();
q.Enqueue("Item 1");
q.Enqueue("Item 2");

// Check if the queue is non-empty, then dequeue an item
if (q.Any())
{
    Console.WriteLine(q.Dequeue());  // Expects "Item 1"
}

A deque, or "double-ended queue," allows the addition and removal of items from both ends. C# provides the LinkedList<T> class for implementing deques. We can add items to both ends of our deque using the AddLast(item) method for the right end and the AddFirst(item) method for the left. Similarly, we can remove elements from the left and right ends using RemoveFirst and RemoveLast.

using System;
using System.Collections.Generic;

// Create a deque and add items
LinkedList<string> d = new LinkedList<string>();
d.AddLast("Middle");
d.AddLast("Right end");
d.AddFirst("Left end");

// Remove an item
Console.WriteLine(d.Last.Value);  // Expects "Right end"
d.RemoveLast();

// Remove an item from the left
Console.WriteLine(d.First.Value); // Expects "Left end"
d.RemoveFirst();