Head, Enqueue, and Dequeue Member Functions

Program  defines the Head, Enqueue and Dequeue member functions of the QueueAsArray class.

  
Program: QueueAsArray Class Head, Enqueue and Dequeue Member Function Definitions

The Head member function simply returns a reference to the object found at the head of the queue, having first checked to see that the queue is not empty. If the queue is empty, it throws a domainerror exception. Under normal circumstances, we expect that the queue will not be empty. Therefore, the normal running time of this function is O(1).

The Enqueue function takes a single argument which is a reference to an object to be added to the tail of the queue. The Enqueue function first checks that the queue is not full--a domainerror exception is thrown when the queue is full. Next, the position at which to insert the new element is determined by increasing the member variable tail by one modulo the length of the array. Finally, a pointer to the object to be enqueued is put into the array at the correct position and the count is adjusted accordingly. Under normal circumstances (i.e., when the exception is not thrown), the running time of Enqueue is O(1).

The Dequeue function removes an object from the head of the queue and returns a reference to that object. First, it checks that the queue is not empty and throws an exception when it is. If the queue is not empty, the function sets aside a reference to the object at the head in the local variable result; it increases the head member variable by one modulo the length of the array; adjusts the count accordingly; and returns result. All this can be done in a constant amount of time so the running time of Dequeue is a constant.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.