Circular and Priority Queues

Overview

Recall questions on adding to, removing from and testing a circular queue, tracing one held in an array, how a priority queue works and is used, and comparing linear and circular queues.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe a circular queue.

   Model answer

   A queue held in an array in which the positions are treated as though they form a ring: when a pointer passes the last index of the array it wraps round to index 0. This is achieved with modulo arithmetic on the pointers, so that slots freed at the front of the array are reused and no space is wasted.

2. 2

   Describe how an item is added to a circular queue.

   Model answer

   First test whether the queue is full; if it is, report overflow. Otherwise set rear = (rear + 1) MOD maxSize, store the new item at that position, and increase the size counter by one. The MOD operation makes the rear pointer wrap round to 0 after the last index.

3. 3

   Describe how an item is removed from a circular queue.

   Model answer

   First test whether the queue is empty; if it is, report underflow. Otherwise take the item at the position given by the front pointer, set front = (front + 1) MOD maxSize, and decrease the size counter by one. The item taken is returned.

4. 4

   How do you test a circular queue for empty and for full?

   Model answer

   Using the size counter: the queue is empty when size = 0 and full when size = maxSize. A counter is used because in a circular queue the pointer positions alone cannot distinguish a full queue from an empty one — in both cases the rear pointer sits immediately behind the front pointer.

5. 5

   A circular queue is held in an array of 5 elements, indices 0 to 4, with front = 0, rear = -1 and size = 0. Trace the pointers as A, B, C and D are added and then two items are removed.

   Model answer

   Add A: rear = 0, A at index 0, size 1. Add B: rear = 1, B at index 1, size 2. Add C: rear = 2, size 3. Add D: rear = 3, size 4. Remove: returns A, front = 1, size 3. Remove: returns B, front = 2, size 2. The queue now holds C and D at indices 2 and 3, with front = 2 and rear = 3.

6. 6

   Continuing that queue — front = 2, rear = 3, size = 2 in an array of 5 — two more items E and F are added. Show that the queue wraps round.

   Model answer

   Add E: rear = (3 + 1) MOD 5 = 4, so E is stored at index 4 and size becomes 3. Add F: rear = (4 + 1) MOD 5 = 0, so F is stored at index 0, reusing the slot that A vacated, and size becomes 4. The queue now holds C, D, E, F reading from index 2 round to index 0. A linear queue would have reported itself full when the rear pointer reached index 4.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.