Queue

A queue is a fundamental linear data structure in computer science that follows the First-In-First-Out (FIFO) principle. Just like a real-world queue (e.g., people lining up at a ticket counter), the first element added to the queue will be the first one to be removed.

Characteristics of Queues

• FIFO Order: Elements are processed in the order they were added. The first element enqueued is the first to be dequeued.
• Linear Structure: Elements are arranged in a sequential manner.
• Two Main Operations:
  • enqueue(item): Adds an item to the rear (end) of the queue.
  • dequeue(): Removes and returns the item from the front (beginning) of the queue.
• Additional Operations (May Vary by Implementation):
  • peek(): Returns the item at the front without removing it.
  • isEmpty(): Checks if the queue is empty.
  • isFull(): Checks if the queue is full (relevant for fixed-size queues).
• Terminology:
  • Front (Head): The end of the queue where elements are removed.
  • Rear (Tail): The end of the queue where elements are added.

Common Operations

Operation	Description	Time Complexity
enqueue	Adds an element to the rear of the queue. May cause an overflow if the queue is full (fixed-size).	$O(1)$
dequeue	Removes and returns the element from the front of the queue. May cause an underflow if the queue is empty.	$O(1)$
peek	Returns the element at the front without removing it.	$O(1)$
isEmpty	Checks if the queue has no elements.	$O(1)$
isFull	Checks if the queue cannot accommodate more elements (applicable to fixed-size queues).	$O(1)$

Implementations of Queues

Using Built-in Data Structures

Most high-level programming languages provide built-in data structures or libraries for implementing queues. For example, in Python, you can use the deque class from the collections module for an efficient queue implementation.

from collections import deque

# Initialize the queue
queue = deque()

# Enqueue elements
queue.append(1)
queue.append(2)
queue.append(3)

# Dequeue an element
first_element = queue.popleft()

# Peek at the front element without removing it
front_element = queue[0]

# Check if the queue is empty
is_empty = len(queue) == 0

Implementing a Queue

Queue Using a Linked List

A linked list is a natural choice for implementing a queue, especially when the size is not fixed. Here, the front of the queue corresponds to the head of the linked list, and the rear corresponds to the tail.

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None

class LinkedListQueue:
    """Queue implementation using a singly linked list."""

    def __init__(self):
        self._front = None  # Reference to the front node
        self._rear = None   # Reference to the rear node
        self._size = 0

    def is_empty(self):
        """Check if the queue is empty."""
        return self._size == 0

    def enqueue(self, val):
        """Add an element to the rear of the queue."""
        new_node = ListNode(val)
        if self.is_empty():
            self._front = self._rear = new_node
        else:
            self._rear.next = new_node
            self._rear = new_node
        self._size += 1

    def dequeue(self):
        """Remove and return the front element of the queue."""
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        removed_value = self._front.val
        self._front = self._front.next
        self._size -= 1
        if self.is_empty():
            self._rear = None
        return removed_value

    def peek(self):
        """Return the front element without removing it."""
        if self.is_empty():
            raise IndexError("Peek from empty queue")
        return self._front.val

    def size(self):
        """Return the number of elements in the queue."""
        return self._size

    def to_list(self):
        """Convert the queue elements to a list."""
        elements = []
        current = self._front
        while current:
            elements.append(current.val)
            current = current.next
        return elements

Queue Using a Circular Array

Using a circular array is an efficient way to implement a queue with a fixed size. The idea is to treat the array as if it wraps around, so we can utilize all available space.

class ArrayQueue:
    """Queue implementation using a circular array."""

    def __init__(self, capacity):
        self._array = [None] * capacity
        self._capacity = capacity
        self._front = 0
        self._size = 0

    def is_empty(self):
        """Check if the queue is empty."""
        return self._size == 0

    def is_full(self):
        """Check if the queue is full."""
        return self._size == self._capacity

    def enqueue(self, val):
        """Add an element to the rear of the queue."""
        if self.is_full():
            raise IndexError("Enqueue to full queue")
        rear = (self._front + self._size) % self._capacity
        self._array[rear] = val
        self._size += 1

    def dequeue(self):
        """Remove and return the front element of the queue."""
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        val = self._array[self._front]
        self._array[self._front] = None  # Optional: Help garbage collection
        self._front = (self._front + 1) % self._capacity
        self._size -= 1
        return val

    def peek(self):
        """Return the front element without removing it."""
        if self.is_empty():
            raise IndexError("Peek from empty queue")
        return self._array[self._front]

    def size(self):
        """Return the number of elements in the queue."""
        return self._size

    def to_list(self):
        """Convert the queue elements to a list."""
        elements = []
        for i in range(self._size):
            index = (self._front + i) % self._capacity
            elements.append(self._array[index])
        return elements

Applications of Queues

Queues are widely used in various computing scenarios, especially where order needs to be preserved.

1. Breadth-First Search (BFS): Used in graph traversal algorithms to explore nodes layer by layer.
2. Resource Scheduling:
   • CPU Scheduling: Managing processes and threads in operating systems.
   • Disk Scheduling: Ordering disk I/O operations to optimize performance.
3. Asynchronous Data Handling:
   • IO Buffers: Temporary storage for data being transferred between devices.
   • Print Spooling: Managing print jobs sent to a printer.
4. Task Management Systems:
   • Job Queues in Web Servers: Handling incoming requests in web applications.
   • Message Queues: Decoupling systems by storing messages for asynchronous processing.
5. Order Processing Systems:
   • E-commerce Platforms (e.g., Amazon Orders): Orders are processed in the sequence they are received.
6. Simulation of Real-world Queues:
   • Customer Service Lines: Modeling and analyzing queues in service systems.
   • Call Centers: Managing incoming calls in the order they are received.
7. To-Do Lists and Task Scheduling:
   • Task Queues in Operating Systems: Managing tasks awaiting execution.
   • Event Queues in GUI Applications: Handling user input events.

Conclusion

Queues are essential data structures that provide a way to handle data in a sequential manner, preserving the order of insertion. Understanding queues, their implementations, and their applications is fundamental for solving many problems in computer science and software engineering.

When implementing queues, it's important to choose the right data structure based on the requirements:

• Linked Lists: Ideal for queues with dynamic sizes where elements are frequently added and removed.
• Circular Arrays: Efficient for fixed-size queues with minimal overhead, useful in systems where maximum capacity is known.

Queues are ubiquitous in areas such as process scheduling, data buffering, and real-time systems, making them a crucial concept to master.