|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
The Push and Pop methods, and the Top property
of the StackAsLinkedList class
are defined in Program 
.
Program: StackAsLinkedList class Push and Pop Methods, Top property.
The implementation of Push is trivial. It takes as its argument the object to be pushed onto the stack and simply prepends that object to the linked list list. Then, one is added to the count variable. The running time of the Push method is constant, since the Prepend method has a constant running time, and updating the count only takes O(1) time.
The Pop method is implemented using the First property and the Extract method of the LinkedList class. The First property is used to get the first item in the linked list. The First get accessor runs in constant time. The Extract method is then called to extract the first item from the linked list. In the worst case, Extract requires O(n) time to extract an item from a linked list of length n. But the worst-case time arises only when it is the last element of the list which is to be extracted. In the case of the Pop method, it is always the first element that is extracted. This can be done in constant time. Assuming that the exception which is raised when Pop is called on an empty list does not occur, the running time for Pop is O(1).
The definition of the Top get accessor is quite simple. It returns the first object in the linked list. Provided the linked list is not empty, the running time of Top is O(1). If the linked list is empty, the Top get accessor throws a ContainerEmptyException exception.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.