Queues and Circular Queues

Overview

Recall questions on queues and their uses, front and rear pointers, enqueue and dequeue, the wasted space of a linear queue, circular queues with modulo arithmetic, telling full from empty, tracing operations, and static and dynamic 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

   What is a queue?

   Model answer

   A first in, first out (FIFO) data structure: items are added at one end, the rear or back, and removed from the other end, the front or head. The item that has been waiting longest is always the next to leave, so the order of arrival is preserved.

2. 2

   Give three uses of a queue in a computer system.

   Model answer

   A print spooler holding jobs in the order they were submitted. Keyboard and other input buffers, so that keystrokes are processed in the order typed even when the processor is busy. Process scheduling, where processes wait in a ready queue for the processor. Queues are also used for buffering streamed data and for breadth-first traversal of a graph or tree.

3. 3

   What pointers does a queue need, and what do they hold?

   Model answer

   A front pointer, holding the position of the item that will be removed next, and a rear pointer, holding the position of the last item added (or of the next free slot, depending on convention). Many implementations also keep a count of the number of items and a record of the maximum size, which makes the full and empty tests straightforward.

4. 4

   How do you create an empty queue?

   Model answer

   Declare an array of the maximum size, plus the front and rear pointers and, usually, a counter. Set the front pointer to 0, the rear pointer to -1 (so that the first enqueue places an item at index 0) and the counter to 0. Recording the maximum size allows the full test.

5. 5

   Describe the enqueue operation on a linear queue.

   Model answer

   Check first whether the queue is full — if the rear pointer already holds the last index there is no room, so report the error. Otherwise move the rear pointer on by one, store the new item at the index the rear pointer now holds and increase the item count. The front pointer is not affected.

6. 6

   Describe the dequeue operation on a linear queue.

   Model answer

   Check first whether the queue is empty - if the count is zero, or the front pointer has passed the rear pointer, report underflow. Otherwise read the item at the front pointer, increment the front pointer by one and reduce the count, then return the item read. The item's slot is left behind and is not reused.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.