Push, Pop, and Top Member Functions

The Push, Pop, and Top, member functions of the StackAsLinkedList class are defined in Program .

  
Program: StackAsLinkedList Class Push, Pop, and Top Member Function Definitions

The implementation of Push is trivial. It takes as its lone argument a reference to the Object to be pushed onto the stack and simply prepends a pointer to that object to the linked list list. Then, one is added to the count variable. The running time of the Push function is constant, since the Prepend function has a constant running time, and updating the count only takes O(1) time.

The Pop function is implemented using two of the LinkedList<T> member functions--First and Extract. The First function is used to obtain the first item in the linked list. The function First runs in constant time. The Extract function is then called to remove the first item from the linked list. In the worst case, Extract requires O(n) time to delete 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 deleted. In the case of the Pop function, it is the first element which is deleted. 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).

There is a subtle point in this implementation: Since it is not possible for two different variables to occupy the same memory address, all of the pointers in the linked list will be unique provided no object is pushed onto the stack more than once. This ensures that the datum deleted from the linked list by the Extract function is precisely the one returned by the First function.

The only way that an object can be pushed safely onto the stack more than once is if the stack does not own its contained objects. If the stack owns its objects, then when the stack is deleted its destructor first deletes all the contained objects. As a result, if an object is pushed onto the stack twice, that object's destructor would be called twice. Such a program is not valid since deleting an object which has already been deleted is an error.

The definition of the Top function is quite simple. It simply returns a reference to 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 function throws a domainerror exception.

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