Understanding Queues

What Is a Queue?

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. This means the first element added to the queue is the first one removed.

Real-Life Examples of a Queue

• A line of people waiting at a ticket counter

• Tasks waiting in a printer queue

• Call center waiting system

These examples match the FIFO behavior: whoever comes first is served first.

How a Queue Works

A queue has two main ends:

• Front ? where elements are removed

• Rear ? where elements are added

Common Queue Operations

• Enqueue: Insert an element at the rear

• Dequeue: Remove an element from the front

• Peek: View the front element

• IsEmpty: Check if the queue is empty

Visual Representation of a Queue

Front -> [10] [20] [30] [40] <- Rear

After enqueue(50):

Front -> [10] [20] [30] [40] [50] <- Rear

After dequeue():

Front -> [20] [30] [40] [50] <- Rear

Implementing a Queue Using an Array

public class Queue
{
    private int[] items;
    private int front;
    private int rear;
    private int count;

    public Queue(int size)
    {
        items = new int[size];
        front = 0;
        rear = -1;
        count = 0;
    }

    public void Enqueue(int value)
    {
        rear = (rear + 1) % items.Length;
        items[rear] = value;
        count++;
    }

    public int Dequeue()
    {
        int value = items[front];
        front = (front + 1) % items.Length;
        count--;
        return value;
    }

    public int Peek()
    {
        return items[front];
    }

    public bool IsEmpty()
    {
        return count == 0;
    }
}

This is known as a circular queue, which avoids wasted space.

Implementing a Queue Using a Linked List

public class Node
{
    public int Data;
    public Node Next;
}

public class LinkedQueue
{
    private Node front;
    private Node rear;

    public void Enqueue(int value)
    {
        Node newNode = new Node { Data = value };
        if (rear == null)
        {
            front = rear = newNode;
            return;
        }
        rear.Next = newNode;
        rear = newNode;
    }

    public int Dequeue()
    {
        int value = front.Data;
        front = front.Next;
        if (front == null) rear = null;
        return value;
    }

    public int Peek()
    {
        return front.Data;
    }

    public bool IsEmpty()
    {
        return front == null;
    }
}

Linked list queues grow dynamically and are very flexible.

Types of Queues

1. Simple Queue

Follows FIFO order.

2. Circular Queue

Reuses empty space after deletion.

3. Priority Queue

Elements are removed based on priority, not order.

4. Double-Ended Queue (Deque)

Elements can be added/removed from both ends.

Time Complexity of Queue Operations

All basic operations take O(1) time:

• Enqueue

• Dequeue

• Peek

• IsEmpty

Real-Life Applications of Queues

Queues are widely used in:

1. Operating Systems

• Process scheduling

• CPU task management

2. Networking

• Packet routing

• Bandwidth management

3. Data Streaming

• Handling real-time data

4. Customer Support Systems

• Maintaining waiting customers

5. Printers

• Managing print jobs

Example: Reverse a Queue Using a Stack

Queue<int> q = new Queue<int>();
q.Enqueue(10);
q.Enqueue(20);
q.Enqueue(30);

Stack<int> s = new Stack<int>();

while (q.Count > 0)
{
    s.Push(q.Dequeue());
}

while (s.Count > 0)
{
    q.Enqueue(s.Pop());
}

Summary

Queues are essential for processes that need ordered execution. They provide predictable behavior and are used in many real-world systems.

Key takeaways:

• Follows FIFO principle

• Fast enqueue and dequeue operations

• Used in operating systems, networking, and scheduling systems

• Implemented using arrays or linked lists