Queue Data Structures PDF

Page 1 of 49 QUEUE o​ is a linear data structure that is open at both ends and the operations follows the FIFO (First In, First Out) principle. This means that the element inserted first will be removed first. (First Come First Serve)...

Page 1 of 49 QUEUE o​ is a linear data structure that is open at both ends and the operations follows the FIFO (First In, First Out) principle. This means that the element inserted first will be removed first. (First Come First Serve) Source: https://medium.com/@isuriweerarathna/queue-in-data-structures-a-java-journey-d45fa0f57bce Other Applications: Call Center and Printing Jobs o​ a list in which all ✔​additions (Enqueue) to the list are made at one end (back/rear of the queue), and ✔​all deletions (Dequeue) from the list are made at the other end (front of the queue). The element which is first pushed into the order, the delete operation is first performed on that. Source: https://www.geeksforgeeks.org/introduction-to-queue-data-structure-and-algorithm-tutorials/ Two Main Operations: (1) ENQUEUE and (2) DEQUEUE 1.​ Enqueue: Adding an element to the rear (Back/Tail/End) of the queue.  Page 2 of 49 ENQUEUE Operations: = self.front): print("Elements in the circular queue are:", end = " ") for i in range(self.front, self.rear + 1): print(self.queue[i], end = " ") print () else: print ("Elements in Circular Queue are:", end = " ") for i in range(self.front, self.size): print(self.queue[i], end = " ") for i in range(0, self.rear + 1): print(self.queue[i], end = " ") print () if ((self.rear + 1) % self.size == self.front): print("Queue is Full") # Driver Code ob = CircularQueue(5) ob.enqueue(14) ob.enqueue(22) ob.enqueue(13) ob.enqueue(-6) ob.display() print ("Deleted value = ", ob.dequeue()) print ("Deleted value = ", ob.dequeue()) ob.display() ob.enqueue(9) ob.enqueue(20) ob.enqueue(5) ob.display() # This code is contributed by AshwinGoel Source: https://www.geeksforgeeks.org/introduction-to-circular-queue/  Page 26 of 49 ​ Time Complexity: o​ Enqueue: O(1) because no loop is involved for a single enqueue. o​ Dequeue: O(1) because no loop is involved for one dequeue operation. Applications of Circular Queue: 1.​ Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues. 2.​ Traffic system: In computer controlled traffic system, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set. 3.​ CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur. PRIORITY QUEUE A Priority Queue is a type of abstract data type (ADT) similar to a regular queue but with an added concept of priority. In a priority queue, each element is associated with a priority, and elements with higher priority are dequeued before elements with lower priority, regardless of their order of insertion. Key Characteristics of a Priority Queue 1.​ Prioritization: o​ Each element has an associated priority value. o​ Elements with higher priority are served first. In case of equal priority, elements are dequeued in the order they were added (depending on implementation). 2.​ Operations: o​ Insert (Enqueue): Add an element with an associated priority. o​ Remove (Dequeue): Remove the element with the highest priority. o​ Peek: Return the highest-priority element without removing it. 3.​ Types: o​ Max Priority Queue: Elements with the highest priority are dequeued first. o​ Min Priority Queue: Elements with the lowest priority are dequeued first. Real-World Examples of Priority Queue 1.​ Task Scheduling in Operating Systems:  Page 27 of 49 o​ High-priority tasks (e.g., system processes) are executed before low-priority tasks (e.g., user applications). 2.​ Hospital Emergency Rooms: o​ Patients with more severe conditions are attended to first, regardless of their arrival time. 3.​ Network Packet Management: o​ Important data packets are transmitted before less critical ones in communication systems. 4.​ Dijkstra’s Algorithm: o​ Used in shortest-path algorithms where nodes are processed based on priority (e.g., distance from the source). Implementation of Priority Queue 1.​ Using Arrays or Lists: o​ Insert elements in any order. o​ Search for the highest/lowest priority element during dequeue. 2.​ Using Heap (Efficient Method): o​ A Max-Heap or Min-Heap is often used for efficient insertions and deletions. o​ Insert and remove operations in a heap take O(log n) time. Priority Queue using Array: Algorithm Array-Based Implementation In this approach, we store elements in an array, with their priorities included. Enqueue (Insert): Dequeue (Remove): 1.​ Check if the array is full. 1.​ Check if the array is empty. 2.​ Add the new element and its priority at 2.​ Remove the element with the highest (or the end of the array. lowest) priority. 3.​ Rearrange the array to maintain the 3.​ Shift the remaining elements to fill the priority order (based on max or min gap. priority). Input: Array `queue[]`, size `size`, rear index Input: Array `queue[]`, front index `front`, rear `rear`, element `e`, priority `p` index `rear` Output: Updated queue with element `e` inserted Output: Element with highest priority removed from the queue Step 1: If `rear == size - 1`, then Print "Queue is full" Step 1: If `front > rear`, then Exit Print "Queue is empty"  Page 28 of 49 Step 2: Else, Exit Increment `rear` by 1 Step 2: Else, Insert element `e` and priority `p` at Store `queue[front]` in a variable (the `queue[rear]` highest-priority element) Step 3: Rearrange the array to maintain priority Increment `front` by 1 order: Step 3: Return the stored element For i from `rear` to `0`: Step 4: End If `queue[i].priority < queue[i-1].priority`, Swap them Step 4: End Priority Queue using Array (enqueue) Page 29 of 49 Page 30 of 49  Page 31 of 49 OUTPUT =========================== class PriorityQueue: def __init__(self, size): """ Initialize the priority queue with a fixed size. Attributes: - queue: Array to store elements and their priorities.  Page 32 of 49 - size: Maximum size of the queue. - rear: Index of the last element in the queue. """ self.queue = [None] * size self.size = size self.rear = -1 def is_full(self): """ Check if the queue is full. """ return self.rear == self.size - 1 def is_empty(self): """ Check if the queue is empty. """ return self.rear == -1 def enqueue(self, element, priority): """ Insert an element into the queue based on its priority. Args: - element: The value to be added. - priority: The priority associated with the element. """ if self.is_full(): print("Queue is full!") return # Increment rear and insert the new element at the rear self.rear += 1 self.queue[self.rear] = (element, priority) # Rearrange the queue to maintain priority order for i in range(self.rear, 0, -1): if self.queue[i] < self.queue[i - 1]: # Compare priorities # Swap if current priority is less than previous self.queue[i], self.queue[i - 1] = self.queue[i - 1], self.queue[i] else: break # Stop if order is correct print(f"Enqueued: ({element}, {priority})") def dequeue(self): """ Remove and return the element with the highest priority (lowest priority value). """ if self.is_empty(): print("Queue is empty!")  Page 33 of 49 return None # Remove the front element element = self.queue # Shift elements to the left for i in range(self.rear): self.queue[i] = self.queue[i + 1] self.queue[self.rear] = None self.rear -= 1 print(f"Dequeued: {element}") return element def display(self): """ Display the queue. """ if self.is_empty(): print("Queue is empty!") else: print("Queue:", self.queue[:self.rear + 1]) # Example usage pq = PriorityQueue(5) # Create a priority queue with size 5 pq.enqueue(10, 3) # Add (10, priority 3) pq.enqueue(20, 2) # Add (20, priority 2) pq.enqueue(30, 1) # Add (30, priority 1) pq.display() pq.enqueue(15, 2) # Add (15, priority 2) pq.display() pq.enqueue(40, 4) # Add (40, priority 4) pq.display() pq.enqueue(50, 1) # Add (50, priority 1) pq.display() pq.dequeue() # Remove the element with the highest priority pq.display() Priority Queue using Array (dequeue) Page 34 of 49  Page 35 of 49 OUTPUT  Page 36 of 49 class PriorityQueue: def __init__(self, size): """ Initialize the priority queue with a fixed size. Attributes: - queue: Array to store elements and their priorities. - size: Maximum size of the queue. - rear: Index of the last element in the queue. """ self.queue = [None] * size self.size = size self.rear = -1 def is_full(self): """ Check if the queue is full. """ return self.rear == self.size - 1 def is_empty(self): """ Check if the queue is empty. """ return self.rear == -1 def enqueue(self, element, priority): """ Insert an element into the queue based on its priority. Args: - element: The value to be added. - priority: The priority associated with the element. """ if self.is_full():  Page 37 of 49 print("Queue is full!") return # Increment rear and insert the new element at the rear self.rear += 1 self.queue[self.rear] = (element, priority) # Rearrange the queue to maintain priority order for i in range(self.rear, 0, -1): if self.queue[i] < self.queue[i - 1]: # Compare priorities # Swap if current priority is less than previous self.queue[i], self.queue[i - 1] = self.queue[i - 1], self.queue[i] else: break # Stop if order is correct print(f"Enqueued: ({element}, {priority})") def dequeue(self): """ Remove and return the element with the highest priority (lowest priority value). """ if self.is_empty(): print("Queue is empty!") return None # Remove the front element element = self.queue # Shift elements to the left for i in range(self.rear): self.queue[i] = self.queue[i + 1] self.queue[self.rear] = None self.rear -= 1 print(f"Dequeued: {element}") return element def display(self): """ Display the queue. """ if self.is_empty(): print("Queue is empty!") else: print("Queue:", self.queue[:self.rear + 1]) # Example usage pq = PriorityQueue(5) # Create a priority queue with size 5 pq.enqueue(10, 3) # Add (10, priority 3) pq.enqueue(20, 2) # Add (20, priority 2) pq.enqueue(30, 1) # Add (30, priority 1)  Page 38 of 49 pq.display() pq.enqueue(15, 2) # Add (15, priority 2) pq.display() pq.enqueue(40, 4) # Add (40, priority 4) pq.display() pq.enqueue(50, 1) # Add (50, priority 1) pq.display() pq.dequeue() # Remove the element with the highest priority pq.display() Explanation of the Code: 1.​ Initialization: o​ queue is initialized as an array with a fixed size. o​ front points to the first element in the queue. o​ rear points to the last element in the queue. 2.​ dequeue: o​ Checks if the queue is empty by verifying front > rear. o​ If not empty, retrieves the element at front and increments front. 3.​ enqueue: o​ Adds elements to the queue and rearranges them based on priority. 4.​ Display: o​ Prints the current state of the queue from front to rear. Algorithm: List-Based Priority Queue In this approach, elements are stored in a linked list. Each node contains the data and its priority. The list is typically kept sorted by priority during insertion. Enqueue (Insert): Dequeue (Remove): 1.​ Create a new node with the given 1.​ Check if the list is empty. element and priority. 2.​ Remove the node at the head of 2.​ Insert the new node in the correct the list (highest-priority element). position in the list based on its priority. Input: Linked list `queue`, element `e`, Input: Linked list `queue` priority `p` Output: Element with the highest priority Output: Updated queue with element `e` removed from the queue inserted Step 1: If the list is empty, Step 1: Create a new node with element Print "Queue is empty" `e` and priority `p` Exit Step 2: Else,  Page 39 of 49 Step 2: If the list is empty or `p` is higher Store the data of the head node than the priority of the head node, (highest-priority element) Insert the new node at the head Move the head pointer to the next Exit node Step 3: Else, Delete the old head node Traverse the list to find the correct Step 3: Return the stored data position for `p` Step 4: End Insert the new node before the first node with a lower priority Step 4: End # Priority Queue using Array  Page 40 of 49 OUTPUT  Page 41 of 49 ============================= class PriorityQueue: def __init__(self, size): self.queue = [] # Array to hold elements and their priorities self.size = size def is_full(self): return len(self.queue) == self.size def is_empty(self): return len(self.queue) == 0 def enqueue(self, element, priority): if self.is_full(): print("Priority Queue is full!") else: # Insert the element and priority as a tuple self.queue.append((element, priority)) # Sort the queue based on priority (ascending order) self.queue.sort(key=lambda x: x) print(f"Enqueued: ({element}, {priority})") def dequeue(self): if self.is_empty(): print("Priority Queue is empty!") return None else: # Remove the element with the highest priority (lowest value) dequeued_element = self.queue.pop(0) print(f"Dequeued: {dequeued_element}") return dequeued_element # Example Usage pq = PriorityQueue(5) # Create a priority queue with size 5  Page 42 of 49 pq.enqueue(10, 1) pq.enqueue(20, 2) pq.enqueue(30, 3) pq.enqueue(15, 2) # Adding (15, 2) print("Queue after enqueue operations:", pq.queue) pq.dequeue() # Removing the element with the highest priority print("Queue after dequeue operation:", pq.queue) Explanation 1.​ Initialization: o​ The PriorityQueue class uses a Python list (self.queue) to store elements and their priorities as tuples (element, priority). 2.​ Enqueue Operation: o​ A new element is added to the array. o​ The array is then sorted based on the priority (ascending order) to maintain the correct order of priorities. 3.​ Dequeue Operation: o​ The element with the highest priority (lowest priority value) is removed from the front of the array. 4.​ Output: o​ The operations produce the required transformations in the queue. # Priority Queue using Link List  Page 43 of 49 OUTPUT:  Page 44 of 49 ===================== class PriorityQueue: def __init__(self, size): self.queue = [] # Array to hold elements and their priorities self.size = size def is_full(self): return len(self.queue) == self.size def is_empty(self): return len(self.queue) == 0 def enqueue(self, element, priority): if self.is_full(): print("Priority Queue is full!") else: # Insert the element and priority as a tuple self.queue.append((element, priority)) # Sort the queue based on priority (ascending order) self.queue.sort(key=lambda x: x) print(f"Enqueued: ({element}, {priority})") def dequeue(self): if self.is_empty(): print("Priority Queue is empty!") return None else: # Remove the element with the highest priority (lowest value) dequeued_element = self.queue.pop(0) print(f"Dequeued: {dequeued_element}") return dequeued_element # Example Usage pq = PriorityQueue(5) # Create a priority queue with size 5 pq.enqueue(10, 1) pq.enqueue(20, 2)  Page 45 of 49 pq.enqueue(30, 3) pq.enqueue(15, 2) # Adding (15, 2) print("Queue after enqueue operations:", pq.queue) pq.dequeue() # Removing the element with the highest priority print("Queue after dequeue operation:", pq.queue) Explanation 1.​ Enqueue: o​ Adds elements in order of their priority. o​ A new node is inserted in the correct position to maintain ascending order of priority. 2.​ Dequeue: o​ Removes the element with the highest priority (lowest priority value) at the head of the list. 3.​ Display: o​ Traverses the linked list to print the current state of the priority queue. Priority Queue vs Regular Queue Aspect Regular Queue Priority Queue Order of Dequeue FIFO (First In, First Out) Based on priority Insertion Time O(1) in most implementations O(logn) with heaps Deletion Time O(1) for regular queue O(logn) with heaps Use Case Simple tasks or commands Tasks requiring prioritization Double ended queue o​ deque (pronounced "deck") is an irregular acronym of double-ended queue. o​ in deque, you can perform both insertion and deletion operations at both of its ends. That’s why it is called a Double-Ended Queue (Deque).  Page 46 of 49 Source: https://www.simplilearn.com/tutorials/data-structure-tutorial/dequeue-in-data-structure PROPERTIES OF DEQUE This flexibility makes it capable of functioning both as a stack (Last-In-First-Out, LIFO) and a queue (First-In-First-Out, FIFO). A.​ A deque can perform both the insertion and deletion using the LIFO (Last In First Out) principle. The insertion and deletion in deque can be limited to one node. When you do that, the deque becomes a stack. Hence, it follows the Last In First Out Principle for insertion and deletion. Source: https://www.simplilearn.com/tutorials/data-structure-tutorial/dequeue-in-data-structure As shown in the image above, initially, there were four elements inside this deque. However, after repeating the removal of an element twice, data elements 2 and 12 get removed from the deque, respectively. You inserted element 2 at last and removed it at first. This example demonstrates the LIFO principle.  Page 47 of 49 B.​ A Deque can perform insertion and deletion operations using the FIFO (First In First Out) principle. As deque can operate on both ends, you can extract queue properties by limiting insertion at the front node and removal at the rear node. Doing this will allow deque to act as a linear queue. As shown in the image above, the element which enters at first will also leave the queue first. This is how deque can use the FIFO principle to perform insertion and deletion. Types of Deque in Data Structure There are two types of deque which are created by restricting certain operations. 1.​ Input-Restricted Deque: Insertion is allowed at only one end, but deletion can occur from both ends.  Page 48 of 49 2.​ Output-Restricted Deque: Deletion is allowed at only one end, but insertion can occur at both ends. Representation of DEQUE: Circular queue or Doubly-linked List Common Operations Operation Description push_front(e) Insert an element e at the front. push_rear(e) Insert an element e at the rear. pop_front() Remove and return the element from the front. pop_rear() Remove and return the element from the rear. peek_front() View the front element without removing it. peek_rear() View the rear element without removing it. is_empty() Check if the deque is empty. is_full() Check if the deque is full (in fixed-size). Applications 1.​ Palindrome Checking:  Page 49 of 49 o​ A deque can be used to check if a string is a palindrome by comparing characters from both ends. 2.​ Sliding Window Problems: o​ Efficient for maintaining a window of elements, such as finding the maximum of every subarray of size k in an array. 3.​ Scheduling and Resource Allocation: o​ Deques are used in job scheduling systems where tasks can be added or removed from either end. 4.​ Undo/Redo Operations: o​ Used to manage the history in text editors or browsers. 5.​ Implementing Complex Data Structures: o​ Structures like priority deques or double-ended priority queues (used in certain algorithms) are built on deques. ADVA NTAGES DISADVANTAGES Flexibility: Supports operations at both ends. Memory Overhead: Versatility: Can mimic both stack and queue When implemented using linked lists, each behaviors. element requires extra memory for pointers. Efficiency: Deques have constant time Limited Operations in Fixed Size: complexity for insertion and deletion In array-based deques, the size is often at both ends in linked list-based fixed, limiting scalability. implementations. Reference: https://cplusplus.com/reference/deque/deque/#google_vignette https://www.thedshandbook.com/double-ended-queue-deque/ https://www.simplilearn.com/tutorials/data-structure-tutorial/dequeue-in-data-structure