Data Structures and Algorithms with Object-Oriented Design Patterns in Python
next up previous index

push, pop, and getTop Methods

Program gif defines the push, pop and getTop methods of the StackAsArray class. The first of these, push, adds an element to the stack. In addition to self, it takes as its argument the object, obj, to be pushed onto the stack.

   program5295
Program: StackAsArray class push, pop, and getTop methods.

The push method first checks to see if there is room left in the stack. If no room is left, it raises a ContainerFull exception. Otherwise, it simply puts the object into the array, and then increases the _count variable by one. In a correctly functioning program, stack overflow should not occur. If we assume that overflow does not occur, the running time of the push method is clearly O(1).

The pop method removes an item from the stack and returns that item. The pop method first checks if the stack is empty. If the stack is empty, it raises a ContainerEmpty exception. Otherwise, it simply decreases _count by one and returns the item found at the top of the stack. In a correctly functioning program, stack underflow will not occur normally. The running time of the pop method is O(1).

Finally, the getTop method returns the top item in the stack. The getTop method does not modify the stack. In particular, it does not remove the top item from the stack. The getTop method first checks if the stack is empty. If the stack is empty, it raises a ContainerEmpty exception. Otherwise, it returns the top item, which is found at position tex2html_wrap_inline60683 in the array. Assuming stack underflow does not occur normally, the running time of the getTop method is O(1).


next up previous index

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