| 1. |
As discussed in lectures, a queue is a simple data structure that allows items to be added to one end and read/deleted from the other end in chronological order.
That is, items are serviced on a first-in-first-out basis.
A priority queue is similar to a queue: objects are added to the end of the queue and removed from the front.
However, in a priority queue, when an item is added to the queue, it is assigned a priority to indicate the relative importance of the item.
Instead of removing items in chronological order, a priority queue services items with the highest priority before any others.
If there are no items with the highest priority, the second highest priority is serviced, and so on.
Items are no longer removed on a first-in-first-out basis - items are removed depending on their relative importance in the queue.
Items of equal importance (priority) are serviced in chronological order.
There are a number of different ways to represent a priority queue in a computer.
One way involves "linking" the elements together (as in a linked list) maintaining the order of the elements in terms of both their chronology and priority.
Consider a priority queue of characters using the following self-referential data structure:
typedef struct _e {
char item;
int priority;
struct _e *next;
} ELEMENT;
typedef ELEMENT* PRIORITYQUEUE;
Write functions to add and remove elements from the priority queue that match the following prototypes:
// enqueue(pq, c, p) adds c into pq with a priority of p.
PRIORITYQUEUE enqueue(PRIORITYQUEUE pq, char c, int p);
// dequeue(pq, c) removes the leading character from pq, storing the
// character in c. The function generates an error and terminates the
// program if pq is empty.
PRIORITYQUEUE dequeue(PRIORITYQUEUE pq, char *c);
// dequeueP(pq, p, c) removes the leading character from pq with given
// priority p, storing the character in c. The function generates an error
// and terminates the program if there are no elements in pq with priority p.
PRIORITYQUEUE dequeueP(PRIORITYQUEUE pq, int p, char *c);
For example:
Building new PQueue
pq = <empty>
Enqueuing a with priority 1:
pq = (a,1)
Enqueuing b with priority 2:
pq = (a,1) -> (b,2)
Enqueuing c with priority 1:
pq = (a,1) -> (c,1) -> (b,2)
Enqueuing d with priority 5:
pq = (a,1) -> (c,1) -> (b,2) -> (d,5)
Enqueuing e with priority 5:
pq = (a,1) -> (c,1) -> (b,2) -> (d,5) -> (e,5)
Enqueuing f with priority 3:
pq = (a,1) -> (c,1) -> (b,2) -> (f,3) -> (d,5) -> (e,5)
Enqueuing g with priority 1:
pq = (a,1) -> (c,1) -> (g,1) -> (b,2) -> (f,3) -> (d,5) -> (e,5)
Enqueuing x with priority 0:
pq = (x,0) -> (a,1) -> (c,1) -> (g,1) -> (b,2) -> (f,3) -> (d,5) -> (e,5)
Enqueuing y with priority 2:
pq = (x,0) -> (a,1) -> (c,1) -> (g,1) -> (b,2) -> (y,2) -> (f,3) -> (d,5) -> (e,5)
Enqueuing z with priority 5:
pq = (x,0) -> (a,1) -> (c,1) -> (g,1) -> (b,2) -> (y,2) -> (f,3) -> (d,5) -> (e,5) -> (z,5)
Dequeuing leading element. The corresponding character is: x
pq = (a,1) -> (c,1) -> (g,1) -> (b,2) -> (y,2) -> (f,3) -> (d,5) -> (e,5) -> (z,5)
Dequeuing leading element. The corresponding character is: a
pq = (c,1) -> (g,1) -> (b,2) -> (y,2) -> (f,3) -> (d,5) -> (e,5) -> (z,5)
Dequeuing leading element. The corresponding character is: c
pq = (g,1) -> (b,2) -> (y,2) -> (f,3) -> (d,5) -> (e,5) -> (z,5)
Dequeuing leading element. The corresponding character is: g
pq = (b,2) -> (y,2) -> (f,3) -> (d,5) -> (e,5) -> (z,5)
Dequeuing leading element. The corresponding character is: b
pq = (y,2) -> (f,3) -> (d,5) -> (e,5) -> (z,5)
Dequeuing leading element with priority 5. The corresponding character is: d
pq = (y,2) -> (f,3) -> (e,5) -> (z,5)
Dequeuing leading element with priority 2. The corresponding character is: y
pq = (f,3) -> (e,5) -> (z,5)
Dequeuing leading element with priority 5. The corresponding character is: e
pq = (f,3) -> (z,5)
Dequeuing leading element with priority 5. The corresponding character is: z
pq = (f,3)
Dequeuing leading element with priority 5. Error: no matching elements with priority 5 in the PQueue.
|
