8.3 Queue Implementations and Priority Queues

Queues and priority queues are essential data structures in computer science. They follow the First-In-First-Out principle, with elements added at the rear and removed from the front. This chapter explores different implementations and their efficiency.

Priority queues take it a step further by ordering elements based on priority. We'll dive into heap-based implementations, which offer optimal time complexity for operations like insert and extract-max, making them crucial for various algorithms and applications.

Queue Fundamentals

FIFO Principle and Basic Operations

• FIFO (First-In-First-Out) defines the order of element processing in queues
• Elements enter the queue at one end (rear) and exit from the other end (front)
• Enqueue operation adds an element to the rear of the queue
• Dequeue operation removes and returns the element from the front of the queue
• Peek function allows viewing the front element without removing it
• isEmpty() checks if the queue contains no elements
• isFull() determines if the queue has reached its maximum capacity (for fixed-size implementations)

Circular Queue Implementation

• Circular queue optimizes space utilization in array-based implementations
• Uses a fixed-size array and two pointers: front and rear
• When rear reaches the end of the array, it wraps around to the beginning
• Modulo arithmetic (%) calculates the next position for enqueue and dequeue operations
• Allows reuse of empty spaces at the beginning of the array
• Distinguishes between empty and full states using a size variable or special marker

Queue Implementations

Array-based Queue

• Uses a fixed-size array to store elements
• Maintains front and rear indices to track the queue boundaries
• Enqueue operation increments rear index and adds element at that position
• Dequeue operation removes element at front index and increments it
• Time complexity for enqueue and dequeue operations: $O(1)$
• Space complexity: $O(n)$, where n represents the maximum number of elements
• May lead to "false full" condition when rear reaches array end while front > 0
• Circular array implementation addresses the "false full" issue

Linked List-based Queue

• Utilizes a singly linked list to store queue elements
• Maintains head and tail pointers for efficient enqueue and dequeue operations
• Enqueue operation adds a new node to the tail of the linked list
• Dequeue operation removes the node at the head of the linked list
• Time complexity for enqueue and dequeue operations: $O(1)$
• Space complexity: $O(n)$, where n represents the number of elements in the queue
• Dynamic size allows the queue to grow and shrink as needed
• Eliminates the need for circular implementation or "false full" condition handling

Priority Queues and Heaps

Priority Queue Concepts

• Priority queue orders elements based on their priority rather than insertion order
• Supports operations like insert, delete, and extract-max (or extract-min)
• Can be implemented using various data structures (arrays, linked lists, heaps)
• Heap-based implementation provides optimal time complexity for operations
• Applications include task scheduling, Dijkstra's algorithm, and event-driven simulations
• Balances insertion and deletion operations efficiently

Heap Structure and Types

• Heap represents a complete binary tree with a specific ordering property
• Max-Heap maintains the property that each node is greater than or equal to its children
• Min-Heap ensures each node is less than or equal to its children
• Can be efficiently implemented using an array representation
• Parent of node at index i resides at index $(i-1) / 2$
• Left child of node at index i resides at index $2i + 1$
• Right child of node at index i resides at index $2i + 2$
• Heap property facilitates efficient access to the maximum (or minimum) element

Heap Operations and Applications

• Insert operation adds a new element to the heap and restores the heap property
• Delete operation removes a specific element from the heap and restructures it
• Extract-Max (or Extract-Min) removes and returns the root element of the heap
• Heapify process converts an arbitrary array into a valid heap structure
• Heap Sort algorithm uses a max-heap to sort elements in ascending order
• Time complexity for insert and extract operations: $O(log n)$
• Heapify operation has a time complexity of $O(n)$ for building the initial heap
• Heap Sort achieves $O(n log n)$ time complexity for sorting n elements