Question

One of the benefits of having our data structures be generalized to hold any type of data is that we can have data structures store instances of data structures. As we mentioned in class, a priority queue is a queue where entries are added (enqueued) according to their priority level (and in order when priority is tied). So the entry with the highest priority that was added to the priority queue the earliest would be at the front and would be the entry that is removed (dequeued).

Given that entries with the same priority will have to be organized in the order they were enqueued (first-in, first out), one possible option is to create a PriorityQueue that holds Queue objects. At the top level, the PriorityQueue can organize entries according to priority level and ensure that the separate priority groups are maintained in their proper order. At the next level, each component Queue would be responsible for all of the entries with the same priority level, and can maintain them in the order in which they were enqueued.

For this problem, assume that there are only 5 priority levels (1 = very low; 2 = low;
3 = medium; 4 = high; 5 = very high). Give a detailed description of how you could implement the PriorityQueue as described above. Your answer should include:

•  How the top-level organization would work.

•  What properties your class would need.

•  A short description of how each of the three main queue operations (enqueue, dequeue,

  and getFront) would work.

Answer 1

Priority queue is the extension of normal queue.

> Every item is associated with the priority.

> The item is with the highest priority is dequeued first than the the item with the lowest priority.

> If the two items are having the same priority, then according to the items in the queue they are dequeued.

Coming to the elements i.e characters with the highest ASCII value will be dequeued first than the elements with the lowest ASCII value.

There are three types of priority queue operations are:

> insert()

> GetHighestpriority()

> deleteHighestpriority()  

Deleting the items from the list.

Inserting the elements into the queue, thw element can be inserted at the last of the position which is the order of O(1).

These priority queues are implemented using the Heaps. Heaps only gerally used to implement the priority queues.

Applications of Priority Queue:
1) CPU Scheduling algorithm.
2) Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc
3) All queue applications where priority property is involved.

A priority queue is a concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

----Properties of priority class needed are:

> add() - Inserts the elements in the priority queue.

> clear() - It clears all the elements in the priority queue.

> comparator() - It returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.

> contains() - It returns true if there are no elements in the priority queue.

> iterator() - It returns an iterator over the elements in this queue.

> remove() - It removes all the elements in the priority queue.

> splititerator() - Creates the late- binding over the elements in the priority queue.

These are the some of the methods in the priority class java.

The operations of priority queue are :

> Enqueue

> Dequeue

In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item.

In Enqueue, Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement than that of stacks.

In Dequeue, Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access.

These are the operations in the queue.

These priority queues are implemented in the many different languages like python, java, C, C++.