A priority queue is a queue where a numeric priority is asso

A priority queue is a queue where a numeric priority is associated with each element. Access to elements that have been inserted into the queue is limited to inspection and removal of the elements with smallest and largest priority only. A priority queue may have multiple items that are of equal priority.

Give the ADT speci?cation for a bounded priority queue using the speci?cation method described in Topic 5 of the lecture notes. By “bounded”, it is meant that the priority queue has a maximum capacity speci?ed when it is created, and it can never contain more than that number of items.

Your speci?cation must specify the following operations:

newPriorityQueue: make a new queue

insert: inserts an element with a certain priority

isEmpty: test if the queue is empty

isFull: test if the queue is full

maxItem: obtain the item in the queue with the highest priority

minItem: obtain the item in the queue with the lowest priority

deleteMax: remove from the queue the item with the highest priority

deleteAllMax: remove from the queue all items that are tied for the highest priority

deleteMin: remove from the queue the item with the lowest priority

frequency: obtain the number of times a certain item occurs in the queue (with any priority)

  

Topic 5:A List ADT

----------------------
Name: List<G>

---------------------
Sets:

L : set of lists containing items from G

G : set of items that can be in the list

B : {true,false}

---------------------
Signatures:

newList<G> : ? L

L.isEmpty: ? B

L.insertFirst(g): G ? L

---------------------

Preconditions: For all l ? L, g ? G

newList<G>: none

l.isEmpty: none

l.insertFirst(g): none

l.?rstItem: l is not empty

l.deleteFirst: l is not empty

---------------------
Semantics: For l ? L, g ? G

newList<G>: construct new empty list to hold elements from G.

l.isEmpty: return true if l is empty, false otherwise

l.insertFirst(g): g is added to l at the beginning.

l.?rstItem: returns the ?rst item in l.

l.deleteFirst: removes the ?rst item in l.

  

Please answer the quesion in the form of topic 5, that is Name/Sets/Signatures/Preconditions/Semantics.

Thank you

Solution

New Priority Queue: make a new queue

Priority_queue<P,I> Q(int(*cmp)(p,p)):

Creates an instance Q of priority_queue<P,I> based on the given order defined by compare function cmp and initializes it with empty priority queue.

Precondition cmp must be defined a given order on P.

insert: inserts an element with the certain priority

priority queue_item Q.insert(P x,I i) :Adding an item x with the priority with I into queue.

Is Empty: test if queue is emptybool Q.empty()   returns queue is empty ,false other wise.

Is Full: test if queue is full

bool Q.isFull() returns queue is full ,false other wise.

Max Item: obtain the item in the queue with highest priority

Priority queue_item Q.maxItem() :returning item in the Q with max priority I

Precondition: Queue is not empty

Min Item: obtain the item in queue with the lowest priority

Priority queue_item Q.minItem() :returning item in the Q with minimum priority I

Precondition: Queue is not empty

Delete Max: remove from the queue item with the highest priority

P Q. deleteMax() : deletes item with the maximum priority in priority queue and returning priority.

Precondition: Queue is not empty

Delete AllMax: remove from the queue all items that are tied for highest priority

priorityqueue_item[]   Q. deleteAllMax() : deletes item or items with maximum priority in the priority queue and returning list of items that can be deleted.

Precondition: Queue is not empty

Delete Min: remove from queue the item with the lowest priority frequency: obtain number of times a certain item occurs in the queue (with any priority)

P Q. deleteMn() : deletes the item with minimum priority in priority queue and returning priority.

Precondition: Queue is not empty

Here P represents the Priority and I represents value