Question

Q2 [ 20 pts]. In computer science, a priority queue is an abstract data type which is like a regular queue data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to the order in which they were enqueued A typical priority queue supports following operations 1. insert(item, priority): Inserts an item with given priority 2. getHighestPriority(): Returns the highest priority item. 3. deleteHighestPriority) Removes the highest priority item from the priority queue In the figure below priority queue, element with maximum ASCII value will have the highest priority operation argument return value size remove max remove x A E MPP 6 remove max 6 A sequence of operations on a priority queue Write and Test a Java code to implement the priority queue. You may implement the priority queue using ordered arrays or linked list. What is the time complexity of insert/remove functions in the priority queue?

Data Structure

Java code

Answer 1

// Java code to implement Priority Queue
// using Linked List
import java.util.* ;

class Solution
{
  
  
// Node
static class Node {
    Character data;
  
    // Lower values indicate higher priority
    int priority;
  
     Node next;
  
}

static Node node = new Node();
  
// Function to Create A New Node
static Node newNode(Character d, int p)
{
    Node temp = new Node();
    temp.data = d;
    temp.priority = p;
    temp.next = null;
  
    return temp;
}
  
// Return the value at head
static Character peek(Node head)
{
    return (head).data;
}
  
// Removes the element with the
// highest priority form the list
static Node pop(Node head)
{
    Node temp = head;
    (head) = (head).next;
    return head;
}  

// size method for counting size of queue
static int size(Node head)
{
    int cnt=0;
    Node start =(head);
    while(start!=null)
    {
        cnt=cnt+1;
        start=start.next;
    }
    return cnt;
}

//getHighestPriority() will return item which have highest priority
static Character getHighestPriority(Node head)
{
    Node start =(head);
    Node temp=(start);
    while(start.next!=null)
    {
        temp=start;
        start=start.next;
    }
    start=temp.next;
    return start.data;
}

//deleteHighestPriority() for removing maximum priority argument
static Node deleteHighestPriority(Node head)
{
    Node start =(head);
    Node temp=(start);
    while(start.next!=null)
    {
        temp=start;
        start=start.next;
    }
    start=temp.next;
    Character c = getHighestPriority(head);
    temp.next=null;
    System.out.println("\n\nRemove max priority argument");
    System.out.println("Removed element is : " + c);
    return head;
}
// insert() method for insert items according to priority
static Node insert(Node head, Character d, int p)
{
    Node start = (head);
  
    // Create new Node
    Node temp = newNode(d, p);
  
    // Special Case: The head of list has lesser
    // priority than new node. So insert new
    // node before head node and change head node.
    if ((head).priority > p) {
  
        // Insert New Node before head
        temp.next = head;
        (head) = temp;
    }
    else {
  
        // Traverse the list and find a
        // position to insert new node
        while (start.next != null &&
               start.next.priority < p) {
            start = start.next;
        }
  
        // Either at the ends of the list
        // or at required position
        temp.next = start.next;
        start.next = temp;
    }
    return head;
}

// mothod printqueue for printing priority queue
static void printqueue(Node pq)
{
    int cnt=0;
    Node temp=pq;
    while (isEmpty(temp)==0&&cnt<5) {
        System.out.print(peek(temp)+" ");
        temp=pop(temp);
        cnt++;
    }
}
  
// Function to check is list is empty
static int isEmpty(Node head)
{
    return ((head) == null)?1:0;
}
  
// Driver code
public static void main(String args[])
{
    // Create a Priority Queue
  
    Character c;
    //inserting arguments P,Q,E
    System.out.println("Inserting arguments P,Q,E");
    Node pq = newNode('P',((int)'P'-(int)'A') );
    pq =insert(pq, 'Q',((int)'Q'-(int)'A' ));
    pq =insert(pq, 'E',((int)'E'-(int)'A') );
  
    System.out.println("Now Queue has size is "+size(pq)+" and Queue is: ");
    printqueue(pq);
  
    pq=deleteHighestPriority(pq);
    System.out.println("Now Queue has size is "+size(pq)+" and Queue is: ");
    printqueue(pq);
  
    System.out.println("\n\nInserting arguments X,A,M");
    pq =insert(pq, 'X',((int)'X'-(int)'A' ));
    pq =insert(pq, 'A',((int)'A'-(int)'A' ));
    pq =insert(pq, 'M',((int)'M'-(int)'A' ));
    System.out.println("Now Queue has size is "+size(pq)+" and Queue is: ");
    printqueue(pq);
  
    pq=deleteHighestPriority(pq);
    System.out.println("Now Queue has size is "+size(pq)+" and Queue is: ");
    printqueue(pq);
  
    System.out.println("\n\nInserting arguments P,L,E");
    pq =insert(pq, 'P',((int)'P'-(int)'A' ));
    pq =insert(pq, 'L',((int)'L'-(int)'A') );
    pq =insert(pq, 'E',((int)'E'-(int)'A') );
    System.out.println("Now Queue has size is "+size(pq)+" and Queue is: ");
    printqueue(pq);
  
  
    pq=deleteHighestPriority(pq);
    System.out.println("Now Queue has size is "+size(pq)+" and Queue is: ");
    printqueue(pq);
}
}