Queues and Linear Queues

Overview

Recall questions on what a queue is, its typical uses, the front and rear pointers and the working of a linear 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 queue?

   Model answer

   An abstract data type in which items are added at one end, the rear, and removed from the other end, the front. It is a first in, first out (FIFO) structure: the item that has been waiting longest is the next one to leave.

2. 2

   Give four typical uses of a queue.

   Model answer

   A print spooler holding documents waiting for a printer; a buffer holding keystrokes or data waiting to be processed; the ready queue of processes waiting for the processor in an operating system; and the queue of vertices still to be visited in a breadth-first search.

3. 3

   What do the front and rear pointers of a queue hold, and how is a queue in an array of maxSize elements initialised?

   Model answer

   The front pointer holds the index of the first item in the queue, and the rear pointer holds the index of the last item that was added — not the next free slot. The queue is initialised with front = 0 and rear = -1, together with a counter, size, holding the number of items currently stored, initialised to 0. A rear pointer of -1 with a size of 0 means nothing has yet been added.

4. 4

   Describe a linear queue.

   Model answer

   A queue held in an array in which items are added at successively higher indices and removed from the front. The front and rear pointers both only ever move forwards through the array, so the queue creeps along it as items are added and removed.

5. 5

   Describe how an item is added to a linear queue.

   Model answer

   First test whether the queue is full; if it is, report overflow and do not add. Otherwise increase the rear pointer by one, store the new item at the array position the rear pointer now gives, and increase the size counter by one.

6. 6

   Describe how an item is removed from a linear queue.

   Model answer

   First test whether the queue is empty; if it is, report underflow and do not remove. Otherwise take the item at the array position given by the front pointer, increase the front pointer by one so it points at the next item, and decrease the size counter by one. The item taken is returned.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.