A priority queue is a queue where a numeric priority is associated with each ele
ID: 3784594 • Letter: A
Question
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. By “bounded”, it is meant that the priority queue has a maximum capacity specified when it is created, and it can never contain more than that number of items. Your specification 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)
please divide it into the form of
a queue adt
DIVIDED INTO
sets
signatures
preconditions
semantics
need a solution like this
Name: Queue<G>
Sets:
Q : set of queues containing items from G G : set of items that can be in the queue
B : {true, false}
N0: set of non-negative integers
Signatures:
newQueue<G>(n) : N0 Q Q.isEmpty: B
Q.isFull: B
Q.add(g): G Q
Q.remove: G
Preconditions: For all q Q, g G newQueue<G>(n): n > 0 q.isEmpty: none
q.isFull: none
q.add(g): q is not full q.remove:q is not empty
Semantics: For q Q, g G, n N0 newQueue<G>(n) : create a queue of items from G with capacity n
q.isEmpty: returns true if q is empty, false otherwise
q.isFull: return true if q is full, false otherwise q.add(g): enqueues g at the back of the queue q.remove: removes then returns the item at the front of the queue
Explanation / Answer
#include<stdio.h>
#inlude<string.h>
#include<stdlib.h>
#define MAX 6
Int intArray[MAX];
Int itemCount =0;
Int peek(){
Return intArray[itemCount – 1];
}
Boolean isEmpty(){
Return itemcount == 0;
}
Boolean isFull(){
Return itemCount == Max;
}
Int size(){
Return itemCount;
}
vOid insert (int data){
int i=0;
if(isFull()){
// if queue is empty, insert the data
If(itemCount == 0){
intArray[itemCount++] = data;
}else{
// start from the right end of the queue
For(i=itemCount -1;i>=0;i--){
// if data is larger, shift existing item to right end
If(data>intArray[i]){
intArray[i+1] = intArray[i];
}else{
Break;
}
}
// insert the data
IntArray[i+1]=data;
itemCount++;
}
}
}
Int removeData(){
Return intArray[--itemCount];
}
Int main(){
Insert(3)
Insert(5)
Insert(9)
Insert(1)
Insert(12)
Insert(15)
If(isFull()){
Printf(“Queue is full ”);
}
// remove one item
Int num =removeData();
Printf(“element removed :%d ”,num);
Insert(16) //insert more items
//now the queue is full,elements will not be inserted
Insert(17)
Insert(18)
Printf(“elements at front %d ”,peek());
Printf(“queue:”);
While(!isEmpty()){
Int n =removeData();
Printf(“%d”,n);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.