Queues

Overview

Recall questions on queues and FIFO, adding and removing items, linear and circular queues, tracing a circular queue, telling full from empty, priority queues, breadth-first traversal, keyboard buffers, and the complexity of queue operations.

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 queue, and what does FIFO mean?

   Model answer

   A queue is a data structure in which items are added at one end, the rear, and removed from the other end, the front. FIFO stands for first in, first out: the item that has been waiting longest is the next one served, like a queue of people at a till.

2. 2

   Contrast a stack and a queue in one sentence each, being precise about which item leaves first.

   Model answer

   A stack removes the item added most recently, because items go on and come off the same end. A queue removes the item added earliest, because items join at the rear and leave from the front.

3. 3

   Describe the algorithm for adding an item to a queue.

   Model answer

   Check whether the queue is full; if it is, report the error and stop. Otherwise write the new item at the position given by the rear pointer, move the rear pointer on by one, and increase the count of items held. The item now waits behind everything already in the queue.

4. 4

   Describe the algorithm for removing an item from a queue.

   Model answer

   Check whether the queue is empty; if it is, report the error and stop. Otherwise read the item at the position given by the front pointer, move the front pointer on by one, decrease the count of items held, and return the item read.

5. 5

   What is a linear queue and what problem does it have?

   Model answer

   A linear queue stores items in an array with the front pointer moving forward as items leave and the rear pointer moving forward as items arrive. The problem is that both pointers only ever move in one direction, so the space at the start of the array that has been vacated cannot be reused, and the queue reports itself full while much of the array is empty.

6. 6

   How does a circular queue solve that problem?

   Model answer

   The array is treated as if its end joined back onto its beginning. When a pointer moves past the last index it wraps round to index zero, which is done by taking the remainder after dividing the incremented pointer by the array size. Vacated space at the start is therefore reused and the queue is only genuinely full when every position holds an item.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.