Priority Queue Overview
A priority queue is a list of elements, maintained in sorted order according to the priority of each element. For the purposes of this homework, the priority will be a non-negative integer, and the highest-priority element will be the one whose priority value is the smallest. The list will be maintained in ascending priority order so that the highest-priority element will be at the front of the list.
The implementation you’ll create will allow the queue to hold any kind of data since the data element of a queue node will be a void* pointer.
Use these structures:
#define MAX_NAME_LENGTH 64
typedef struct {
char title[MAX_NAME_LENGTH];
char artist[MAX_NAME_LENGTH];
} Song;
typedef struct PQueueStruct {
int priority;
void *data;
struct PQueueStruct *next;
} PQueueNode;
and implement these functions:
int enqueue(PQueueNode **pqueue, int priority, void *data)
This will put the data in the priority queue in the correct place. If there is already one or more nodes in the list having the same priority as the data that you are enqueueing, then put the new node after all of the nodes having that priority. Return zero from this function.
void *dequeue(PQueueNode **pqueue)
Remove the front of the list and return the data from that list node (not the list node itself). If the pqueue is empty, then return NULL. Free the queue node itself in your function (but not the data!).
void *peek(PQueueNode *pqueue)
Return the data from the rst node in the pqueue (not the node itself). If the pqueue is empty, then return NULL. The peek operation does not actually remove a node from the pqueue!
void printQueue(PQueueNode *pqueue, void (printFunction)(void*))
Print the data from each node in the queue.
int getMinPriority(PQueueNode *pqueue)
Return the priority of the rst node in the pqueue. If the pqueue is empty, return -1.
int queueLength(PQueueNode *pqueue)
Return the number of nodes in the pqueue.
void printSong(void *data)
Print an instance of Song as "%s" (%s), with the title eld and name eld. Assume that a pointer to Song is passed into this function. You’ll have to cast the /tt data parameter to a Song in order to get to the title and artist elds.
Each priority-queue node will be a container for an instance of some other data structure| this keeps the definition of the queue node independent of the speci c data that the queue node contains. The void* pointer can point to anything |it’s up to the user of the priority queue to cast the pointer to a pointer of the appropriate underlying data type.
Passing a Function as a Parameter
To keep this independence between the queue nodes and the underlying data (and since we’re not using an object-oriented language), when we want to print the contents of a queue node (speci cally, the object to which the queue node is pointing), it’s necessary to pass in a function that speci es how to print the underlying data object. For an example of how to use a function as a parameter, see function-parameter.c on the course GitLab site (https://gitlab.uvm.edu/Jason.Hibbeler/forstudents f20/tree/master/CS201).
Deliverables
Submit only two les: pqueue.netid.h and pqueue.netid.c. Do not put a main() in your le. Put only the seven functions described above.