COMP1927 13s1 Final Exam

Question 5 (4 marks)

A priority queue is a linear structure where each item has an associated value which specifies its priority for removal from the structure. Answer the following questions on priority queues:

Consider a priority queue where the items are character values, and the priorities are determined by the alphabetical ordering of the items. Items which have lower alphabetical ordering are assigned higher priority (e.g. 'A' has higher priority than 'B'). Show the intermediate states of an initially-empty priority queue PQ when the following operations are performed on the queue in the order shown:
```
PQueueJoin(PQ, 'X')
PQueueJoin(PQ, 'A')
PQueueJoin(PQ, 'J')
PQueueLeave(PQ)
PQueueJoin(PQ, 'K')
PQueueLeave(PQ)
PQueueLeave(PQ)
```
For each state of the queue, write the items in order of highest priority to lowest priority.
Priority queues (PQs) can be viewed as a generalisation of linear structures like Stacks and FIFO Queues. Briefly describe how you might implement Stacks and Queues as PQs. In particular, specify what kind of value could be used as the priority value and how the priority values would be ordered.

Type the answer to this question into the file called q5.txt and submit it using the command:

submit q5