1. Introduction
A Priority Queue is an advanced form of a queue where each element is associated with a priority. Elements are dequeued based on their priority rather than their position in the queue. The element with the highest priority is dequeued before elements of lower priority. In cases where two elements have the same priority, they are dequeued based on their order in the queue.
2. Implementation Steps
1. Define the PriorityQueue class and initialize an empty list to store elements and their priorities.
2. Implement the enqueue method to add an element with its priority to the queue.
3. Implement the dequeue method to remove and return the element with the highest priority.
4. Implement the peek method to view the highest-priority element without removing it.
5. Implement a method to check if the priority queue is empty.
3. Implementation in Ruby Programming
class PriorityQueue
def initialize
@items = [] # Initializing an empty array to store the queue elements and their priorities
end
# A helper method to sort the queue based on priorities
def sort_by_priority
@items.sort! { |a, b| b[1] <=> a[1] }
end
# Adding an item and its priority to the queue
def enqueue(item, priority)
@items.push([item, priority])
sort_by_priority
end
# Removing the highest priority item from the queue
def dequeue
@items.shift[0]
end
# Viewing the highest priority item without removing it
def peek
@items.first[0]
end
# Checking if the queue is empty
def is_empty?
@items.empty?
end
end
# Client code
pq = PriorityQueue.new
pq.enqueue("Task A", 2)
pq.enqueue("Task B", 1)
pq.enqueue("Task C", 3)
puts "Highest priority task: #{pq.peek}" # Output: Task C
puts "Removing highest priority task: #{pq.dequeue}" # Output: Task C
puts "Now, highest priority task: #{pq.peek}" # Output: Task A
Output:
Highest priority task: Task C Removing highest priority task: Task C Now, highest priority task: Task A
Explanation:
1. The PriorityQueue class is initialized with an empty array @items to store the queue's elements and their priorities.
2. The sort_by_priority method sorts the @items array based on the priority. The highest priority item is placed at the front.
3. The enqueue method adds an element and its priority to the @items array and then sorts it based on priority.
4. The dequeue method removes and returns the first element (highest priority) from the @items array.
5. The peek method returns the first element (highest priority) from the @items array without removing it.
6. The is_empty? method checks if the @items array is empty, indicating that the priority queue is empty.