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

The ``Tail'' Operations

Program gif defines the Tail property and the EnqueueTail and DequeueTail methods of the DequeAsArray class.

   program7923
Program: DequeAsArray class ``Tail'' operations.

The Tail property provides a get accessor that returns the object found at the tail of the deque, having first checked to see that the deque is not empty. If the deque is empty, it throws a ContainerEmptyException exception. Under normal circumstances, we expect that the deque will not be empty. Therefore, the normal running time of this method is O(1).

The EnqueueTail method simply calls the Enqueue method inherited from the QueueAsArray class. Its running time was shown to be O(1).

The DequeueTail method removes an object from the tail of the deque and returns that object. First, it checks that the deque is not empty and throws an exception when it is. If the deque is not empty, the method sets aside the object at the tail in the local variable result; it decreases the tail 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 DequeueTail is a constant.


next up previous contents index

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