PRIORITY QUEUE ASSIGNMENT
NAME UZAIR MALIK
REG.NO SP23-BCS-065
CLASS BCS-4B
COURSE DSA
NOV 03, 2024
Priority Queue Using Array: Concepts, Implementation, and Example
1.Introduction to Priority Queue:
A priority queue is a data structure that stores elements along with their priorities. It allows
elements to be inserted with an associated priority and supports removing the element with the
highest (or lowest) priority.
2. Types of Priority Queue
• Min Priority Queue: Elements with the lowest priority value are dequeued first.
• Max Priority Queue: Elements with the highest priority value are dequeued first.
• Applications often determine which type of priority queue to use (e.g., Min-Heap or
Max-Heap implementations).
3.Priority Queue Implementation Using Array:
Implementing a priority queue using an array involves maintaining the elements in the array
in such a way that the highest priority element is at the front (index 0) of the array.
Operations:
Insertion: Add the new element at the appropriate position based on its priority.
Deletion: Remove and return the element with the highest priority (at index 0).
Peek: Return the element with the highest priority without removing it.
isEmpty: Checks if the queue is empty.
isFull: (optional, if implementing a fixed-size array): Checks if the queue has reached its
maximum capacity.
4. Algorithms for Priority Queue Operations
Algorithm for Insertion (Enqueue):
1. Take the element and its priority.
2. Find the correct position in the queue based on priority (in a sorted array or list,
higher-priority elements are at the front).
3. Insert the element in its position, shifting other elements if necessary.
Algorithm for Deletion (Dequeue):
1. Identify the element with the highest or lowest priority (depending on the type).
2. Remove the element and shift the remaining elements as needed to maintain order.
1|Page
Algorithm for Peek:
1. Return the element with the highest or lowest priority without removing it.
5. Applications of Priority Queues
• Task Scheduling: Operating systems use priority queues to schedule tasks, giving
preference to higher-priority tasks.
• Dijkstra’s Algorithm: Used for finding the shortest path in graphs by always
expanding the shortest-known distance node.
• Huffman Coding: Used in data compression algorithms to build Huffman trees based
on frequency of characters.
• Event-Driven Simulations: Events are processed in a priority queue to ensure time-
based order.
Example Implementation (Java):
package Queue;
import java.util.Scanner;
public class priorityQueue {
int[] queue;
int size;
int capacity;
public priorityQueue(int capacity) {
this.queue = new int[capacity];
this.capacity = capacity;
this.size = 0;
}
public void insert(int data) {
if (size == capacity) {
System.out.println("Overflow: The priority queue is full.");
2|Page
return;
}
int i = size - 1;
while (i >= 0 && data > queue[i]) {
queue[i + 1] = queue[i];
i--;
}
queue[i + 1] = data;
size++;
System.out.println(data + " inserted.");
}
public int delete() {
if (size == 0) {
System.out.println("Underflow: The priority queue is empty.");
return -1;
}
int removedData = queue[--size];
System.out.println(removedData + " deleted.");
return removedData;
}
public int peek() {
if (size == 0) {
System.out.println("The priority queue is empty.");
return -1;
}
System.out.println("Peek: " + queue[size - 1]);
3|Page
return queue[size - 1];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the capacity of the priority queue: ");
int capacity = scanner.nextInt();
priorityQueue pq = new priorityQueue(capacity);
while (true) {
System.out.println("\nPriority Queue Menu:");
System.out.println("1. Insert");
System.out.println("2. Delete");
System.out.println("3. Peek");
System.out.println("4. Check if Empty");
System.out.println("5. Check if Full");
System.out.println("6. Exit");
System.out.print("Enter your choice: ");
int choice = scanner.nextInt();
4|Page
switch (choice) {
case 1:
System.out.print("Enter the element to insert: ");
int data = scanner.nextInt();
pq.insert(data);
break;
case 2:
pq.delete();
break;
case 3:
pq.peek();
break;
case 4:
System.out.println("Is Empty: " + pq.isEmpty());
break;
case 5:
System.out.println("Is Full: " + pq.isFull());
break;
case 6:
System.out.println("Exiting...");
scanner.close();
return;
default:
System.out.println("Invalid choice! Please try again.");
}
}
}
}
5|Page
Conclusion:
Priority queues are essential data structures in computer science, used in various applications
such as task scheduling, shortest path algorithms, and more. Implementing a priority queue
using an array provides a simple yet efficient way to manage elements based on their priorities.
6|Page
