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

Enqueue and Dequeue Methods, Head Property

The Enqueue and Dequeue methods and the Head property of the QueueAsLinkedList class are given in Program gif.

   program6825
Program: QueueAsLinkedList class Enqueue and Dequeue methods, Head property.

The Head property provides a get accessor that returns the object at the head of the queue. The head of the queue is in the first element of the linked list. In Chapter gif we saw that the running time of LinkedList.First is a constant, Therefore, the normal running time for the Head method is O(1).

The Enqueue method takes a single argument--the object to be added to the tail of the queue. The method simply calls the LinkedList.Append method. Since the running time for Append is O(1), the running time of Enqueue is also O(1).

The Dequeue method removes an object from the head of the queue and returns that object. First, it verifies that the queue is not empty and throws an exception when it is. If the queue is not empty, Dequeue saves the first item in the linked list in the local variable result. Then that item is extracted from the list. Using the LinkedList class from Chapter gif, the time required to extract the first item from a list is O(1) regardless of the number of items in the list. As a result, the running time of Dequeue is also O(1).


next up previous contents index

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