Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Enqueue and Dequeue Methods, Head Property

Program gif defines Enqueue and Dequeue methods and the Head property of the QueueAsArray class.

Program: QueueAsArray class Enqueue and Dequeue methods, class Head property.

The Head property provides a get accessor that returns 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 ContainerEmptyException exception. Under normal circumstances, we expect that the queue will not be empty. Therefore, the normal running time of this accessor is O(1).

The Enqueue method takes a single argument which is a the object to be added to the tail of the queue. The Enqueue method first checks that the queue is not full--a ContainerFullException exception is thrown when the queue is full. Next, the position at which to insert the new element is determined by increasing the tail field by one modulo the length of the array. Finally, 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 method removes an object from the head of the queue and returns 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 method first sets aside the object at the head in the local variable result; it increases the head field 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 O(1).

next up previous contents index

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