A priority queue is a queue in that each element has some priority and all elements are processed based on their priorities. and the element with high priority is processed before the element with low priority.
if the two elements have the same priority then we follow the FIFO rule means the element that comes first will place first and delete first. and the element that has the highest priority is always at the front of the queue.
and in priority queue element has the highest priority has inserted first and also deleted first.

Here in the above example, we implement a priority queue using a linked list. in each node, we have three parts. in the first part, we store the priority of element and in the second part we store the value of the element and in the third part, we store the linked part of the next element.
if we want to insert a new element that has priority 3 then we need to insert the element after node three.
if the two elements have the same priority then we follow the FIFO rule means the element that comes first will place first and delete first. and the element that has the highest priority is always at the front of the queue.
and in priority queue element has the highest priority has inserted first and also deleted first.

Here in the above example, we implement a priority queue using a linked list. in each node, we have three parts. in the first part, we store the priority of element and in the second part we store the value of the element and in the third part, we store the linked part of the next element.
if we want to insert a new element that has priority 3 then we need to insert the element after node three.
Program to implement priority queue using a linked list in the python programming language.
class EmptyQueueError(Exception): pass class Node: def __init__(self, value, pr): self.info = value self.priority = pr self.link = None class PriorityQueue: def __init__(self): self.front = None def enqueue(self, data, data_priority): temp = Node(data, data_priority) if self.is_empty() or data_priority < self.front.priority: temp.link = self.front self.front = temp else: p = self.front while p.link != None and p.link.priority <= data_priority: p = p.link temp.link = p.link p.link = temp def dequeue(self): if self.is_empty(): raise EmptyQueueError("Queue is empty") x = self.front.info self.front = self.front.link return x def is_empty(self): return self.front == None def display(self): if self.is_empty(): print("Queue is empty") return print("Queue is : ") p = self.front while p is not None: print(p.info, " ", p.priority) p = p.link print() def size(self): n = 0 p = self.front while p is not None: n += 1 p = p.link return n ############################ if __name__ == '__main__': qu = PriorityQueue() while True: print("1. Enqueue") print("2. Dequeue") print("3. Display all queue elements") print("4. Display size of the queue") print("5. Quit") choice = int(input("Enter your choice : ")) if choice == 1: x = int(input("Enter the element : ")) pr = int(input("Enter its priority : ")) qu.enqueue(x, pr) elif choice == 2: x = qu.dequeue() print("Element is : ", x) elif choice == 3: qu.display() elif choice == 4: print("Size of queue ", qu.size()) elif choice == 5: break else: print("Wrong choice ") print()
Also, read these posts
- What are Data Structures and algorithms
- Algorithm design and analysis
- Classification of algorithms
- How to calculate the running time of an algorithm.
- Worst Average and Best-case analysis of the algorithm.
- Big o notation
- Big o notation examples
- Linked List in Data Structures
- Traversing in Linked list
- Operations on the linked list
- Insertion in the linked list
- Deletion in a linked list
- Reversing a linked list
- Sorting a linked list
- Find and remove the loop in the linked list
- Doubly linked list
- Insertion in the doubly linked list
- Deletion in the doubly linked list
- Reversing a doubly linked list
- Circular linked list
- Insertion in the circular linked list
- Deletion in the circular linked list
- Merge two linked list
- Header linked list
- Sorted linked list
- Stack in data structures
- Queue in data structures
- Circular queue
- Dequeue in the data structure
- Polish notation
- Tree in the data structure
- Binary tree
- Array representation of the binary tree
- linked representation of a binary tree
- Traversing in the binary tree
- Inorder traversal in the binary tree
- Preorder traversal in the binary tree
- Postorder traversal in the binary tree
- Level order traversal in the binary tree
- Binary search tree
- Insertion in the binary search tree
- Deletion in the binary search tree
- Heap in data structures
- What are Data Structures and algorithms
- Algorithm design and analysis
- Classification of algorithms
- How to calculate the running time of an algorithm.
- Worst Average and Best-case analysis of the algorithm.
- Big o notation
- Big o notation examples
- Linked List in Data Structures
- Traversing in Linked list
- Operations on the linked list
- Insertion in the linked list
- Deletion in a linked list
- Reversing a linked list
- Sorting a linked list
- Find and remove the loop in the linked list
- Doubly linked list
- Insertion in the doubly linked list
- Deletion in the doubly linked list
- Reversing a doubly linked list
- Circular linked list
- Insertion in the circular linked list
- Deletion in the circular linked list
- Merge two linked list
- Header linked list
- Sorted linked list
- Stack in data structures
- Queue in data structures
- Circular queue
- Dequeue in the data structure
- Polish notation
- Tree in the data structure
- Binary tree
- Array representation of the binary tree
- linked representation of a binary tree
- Traversing in the binary tree
- Inorder traversal in the binary tree
- Preorder traversal in the binary tree
- Postorder traversal in the binary tree
- Level order traversal in the binary tree
- Binary search tree
- Insertion in the binary search tree
- Deletion in the binary search tree
- Heap in data structures
0 Comments