Circular queues and priority queues

Overview

Circular queue and priority queue.

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

   What is a circular queue?

   Model answer

   A circular queue treats the array as a ring, so the position after the last returns to the first. Space freed at the front is therefore reused.

2. 2

   How is the next position calculated in a circular queue?

   Model answer

   The next position is the current pointer plus one, taken modulo the array size. The pointer wraps round to the start after the last element.

3. 3

   A circular queue of size 8 has its rear at index 7. State the index used by the next enqueue.

   Model answer

   The next enqueue uses index 0. The remainder when 8 is divided by 8 is zero, so the pointer wraps round.

4. 4

   How is a full circular queue distinguished from an empty one?

   Model answer

   A separate counter of items held distinguishes the two states. The front and rear pointers otherwise sit in the same relationship in both cases.

5. 5

   Give one advantage of a circular queue over a linear queue.

   Model answer

   A circular queue reuses the space released by earlier dequeues. Data never has to be shifted along the array.

6. 6

   What is a priority queue?

   Model answer

   A priority queue removes the item of highest priority rather than the earliest arrival. Items of equal priority still leave in order of arrival.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.