Priority Queue using Doubly Linked List

Priority Queue using Doubly Linked List

• A priority queue is a data structure that stores elements with associated priorities and allows efficient retrieval of the element with the highest priority.

Node Definition

• A node in the doubly linked list holds both the data and the priority.
• Each node has references to the previous and next nodes in the list.

Initialization

• Initialize an empty priority queue by setting its head and tail pointers to null.

Insertion Operation (PUSH())

• When inserting an element with a priority, create a new node with the data and priority.
• Traverse the list to find the correct position based on priority.
• Start from the head and move to the right until you find a node with a lower or equal priority.
• Insert the new node at the correct position by updating the next and previous pointers accordingly.

Deletion Operation (POP())

• To remove the highest-priority element, simply remove the node at the head of the list.
• Update the head pointer to point to the next node.

Retrieval Operation (PEEK() or TOP())

• To retrieve the highest-priority element without removing it, access the data of the node at the head of the list.

Example

• A priority queue can be used to prioritize tasks based on age, ensuring that older individuals are served or processed first.
• In a healthcare triage scenario, a priority queue can be used to prioritize elderly patients who need immediate attention.

Sample Input and Output

• Sample Input 1: Insert tasks with different priorities into the priority queue.
• Sample Output 1: The highest-priority task is retrieved and executed first, followed by tasks in order of their priorities.