|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Program 
defines the Tail property
and the EnqueueTail and DequeueTail methods
of the DequeAsArray class.
Program: DequeAsLinkedList class ``Tail'' operations.
The Tail property provides a get accessor
that returns the object at the tail of the deque.
The tail of the deque is in the last element of the linked list.
In Chapter we saw that the running time of
LinkedList.getLast is a constant,
Therefore, the normal running time for this accesor is O(1).
The EnqueueTail method simply calls the Enqueue method inherited from the QueueAsLinkedList 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 verifies that the deque is not empty
and throws an exception when it is.
If the deque is not empty,
DequeueTail saves the last item in the linked list
in the local variable result.
Then that item is extracted from the linked list.
When using the LinkedList class from Chapter ,
the time required to extract the last item from a list is O(n),
where 
is the number of items in the list.
As a result,
the running time of DequeueTail is O(n).
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.