Queues - potatoscript/dsa GitHub Wiki

A queue is like a line at your favorite amusement park 🎢! When you stand in line to ride a roller coaster, the first person in line is the first one to ride the coaster. 🏰

In computer science, this is called First In, First Out (FIFO) — the first item that enters the queue is the first one to leave. Think of it like waiting your turn in line: the person who comes first gets served first.

Front → [Person 1] → [Person 2] → [Person 3] → Back

If a new person joins the line (let’s call them "Person 4"), they go to the back:

Front → [Person 1] → [Person 2] → [Person 3] → [Person 4] → Back

And when it's time to serve someone (let’s say "Person 1"), they get served first from the front:

Serve Person 1: Front → [Person 2] → [Person 3] → [Person 4] → Back

Queues are used in many real-world situations:

• ✅ Print Jobs: Think about when you send multiple documents to print. The first document you send will be the first to print.
• ✅ Task Scheduling: The operating system handles tasks in a queue, the first task in is the first to be processed.
• ✅ Handling Requests: When servers handle multiple requests from users, the first request to arrive is the first to be processed.

In C#, we can use the Queue<T> class to easily implement a queue:

Queue<string> customerQueue = new Queue<string>();

customerQueue.Enqueue("Customer 1");
customerQueue.Enqueue("Customer 2");
customerQueue.Enqueue("Customer 3");

string servedCustomer = customerQueue.Dequeue();  // Serves "Customer 1"
Console.WriteLine("Served: " + servedCustomer);

If you just want to see who is at the front without removing them, you can peek:

string frontCustomer = customerQueue.Peek();  // Shows "Customer 2" without removing
Console.WriteLine("Front customer: " + frontCustomer);

Queue<string> customerQueue = new Queue<string>();
customerQueue.Enqueue("Customer 1");
customerQueue.Enqueue("Customer 2");
customerQueue.Enqueue("Customer 3");

Console.WriteLine("Queue after enqueueing customers:");
foreach (var customer in customerQueue)
{
    Console.WriteLine(customer);
}

Output:

Customer 1
Customer 2
Customer 3

string servedCustomer = customerQueue.Dequeue();
Console.WriteLine("Served Customer: " + servedCustomer);

Console.WriteLine("Queue after serving a customer:");
foreach (var customer in customerQueue)
{
    Console.WriteLine(customer);
}

Output:

Served Customer: Customer 1
Customer 2
Customer 3

• ❌ Dequeueing from an empty queue: You can’t remove an item from an empty queue! Always check if the queue is empty before dequeuing.

if (customerQueue.Count > 0)
{
    customerQueue.Dequeue();
}
else
{
    Console.WriteLine("Queue is empty!");
}

In many operating systems, tasks are placed in a queue and processed in the order they arrive. This is how tasks are scheduled to execute on your computer, ensuring fairness.

When several print jobs are sent to a printer, they are placed in a queue. The first print job that arrives is the first to be printed.

Queue<string> taskQueue = new Queue<string>();

// Adding tasks
taskQueue.Enqueue("Task 1");
taskQueue.Enqueue("Task 2");
taskQueue.Enqueue("Task 3");

// Processing tasks
while (taskQueue.Count > 0)
{
    string task = taskQueue.Dequeue();
    Console.WriteLine("Processing " + task);
}

• Enqueue: O(1) — Adding to the end is quick!
• Dequeue: O(1) — Removing from the front is also quick!
• Peek: O(1) — Viewing the front without changing the queue is fast!

Create a queue of print jobs and remove them one by one, simulating a printer processing the jobs.

Simulate a customer service line where customers are added to the queue and served one by one.

Write a program that simulates a task scheduler. Add a few tasks to the queue and process them one by one.

• Single Queue: A simple, one-line queue.
• Circular Queue: The queue “wraps around” when the end is reached, using the available space more efficiently.
• Priority Queue: Items with higher priority are processed before items with lower priority.
• Double-Ended Queue (Deque): A queue where you can add or remove items from both ends.

✅ Queues store data in a First In, First Out (FIFO) order.
✅ Add (Enqueue) to the back, remove (Dequeue) from the front.
✅ Use them for managing tasks, print jobs, customer service lines, and more!
✅ Big O for queue operations: O(1) — fast and efficient!