Implementing Stacks

Stacks are a common and straightforward data structure, used in a variety of applications: language processing, graph searches, etc. In short, stacks are a last-in-first-out collection of objects: the last item added to the collection is always the next one to be removed. Clients use stacks by:

• Pushing items onto the top
• Popping items off the top

Depending on client requirements, there may also be tools for such tasks as testing if the stack is empty, fetching the top item without popping it, iterating over a stack's items, testing for item membership, etc.

In Python, a simple list is often adequate for implementing a stack: because we can change lists in place, we can either add and delete items from the front (left) or end (right). Table 17-1 summarizes various built-in operations available for implementing stack-like behavior with Python lists, depending on whether the stack "top" is the first or last node in the list. In this table, string 'c' is the top item on the stack.

Table 17-1. Stacks as Lists

Operation	Top is end-of-list	Top is front-of-list	Top is front-of-list
New	stack=['a','b','c']	stack=['c','b','a']	stack=['c','b','a']
Push	stack.append('d')	stack.insert(0,'d')	stack[0:0] = ['d']
Pop[1]	X = stack[-1]; del stack[-1]	x = stack[0]; del stack[:1]	x = stack[0]; stack[:1] = []

[1] In fact, Python 1.5 introduced a list pop method designed to be used in conjunction with append to implement stacks: to push, say list.append(value), to pop, say x=list.pop( ). The pop method is equivalent to fetching and then deleting the last item at offset -1 (and equal to the last row in column 2 of Table 17-1). Because lists are a type (not a class), though, you still may need to use the stack class techniques in this chapter to do something custom.

This list arrangement works and will be relatively fast. But it also binds stack-based programs to the stack representation chosen: stack operations will all be hardcoded. If we later want to change how a stack is represented, or extend its basic operations, we're stuck: every stack-based program will have to be updated.

For instance, to add logic that monitors the number of stack operations a program performs, we'd have to add code around each hardcoded stack operation. In a large system, this operation may be nontrivial. As we'll see in the next chapter, we may also decide to move stacks to a C-based implementation, if they prove to be a performance bottleneck. As a general rule, hardcoded operations on built-in data structures don't support future migrations as well as we'd sometimes like.

17.2.1 A Stack Module

Perhaps a better approach is to encapsulate stack implementations using Python's code reuse tools. Let's begin by implementing a stack as a module containing a Python list, plus functions to operate on it (see Example 17-1).

Example 17-1. PP2EDstructBasicstack1.py

stack = [] # on first import
error = 'stack1.error' # local exceptions

def push(obj):
 global stack # use 'global' to change
 stack = [obj] + stack # add item to the front

def pop( ):	
 global stack
 if not stack:
 raise error, 'stack underflow' # raise local error
 top, stack = stack[0], stack[1:] # remove item at front
 return top

def top( ):
 if not stack: # raise local error
 raise error, 'stack underflow' # or let IndexError occur
 return stack[0] 

def empty( ): return not stack # is the stack []?
def member(obj): return obj in stack # item in stack?
def item(offset): return stack[offset] # index the stack
def length( ): return len(stack) # number entries
def dump( ): print '' % stack

This module creates a list object (stack) and exports functions to manage access to it. The stack is declared global in functions that change it, but not in those that just reference it. The module also defines an error object (error) that can be used to catch exceptions raised locally in this module. Some stack errors are built-in exceptions: method item triggers IndexError for out-of-bounds indexes.

Most of the stack's functions just delegate the operation to the embedded list used to represent the stack. In fact, the module is really just a wrapper around a Python list. But this extra layer of interface logic makes clients independent of the actual implementation of the stack. So, we're able to change the stack later without impacting its clients.

As usual, one of the best ways to understand such code is to see it in action. Here's an interactive session that illustrates the module's interfaces:

C:...PP2EDstructBasic>python
>>> import stack1
>>> stack1.push('spam')
>>> stack1.push(123)
>>> stack1.top( )
123
>>> stack1.stack
[123, 'spam']
>>> stack1.pop( )
123
>>> stack1.dump( )

>>> stack1.pop( )
'spam'
>>> stack1.empty( )
1
>>> for c in 'spam': stack1.push(c)
...
>>> while not stack1.empty( ):
... print stack1.pop( ),
...
m a p s

Other operations are analogous, but the main thing to notice here is that all stack operations are module functions. For instance, it's possible to iterate over the stack, but we need to use counter-loops and indexing function calls (item ). There's nothing preventing clients from accessing (and changing) stack1.stack directly, but doing so defeats the purpose of interfaces like this one.

17.2.2 A Stack Class

Perhaps the biggest drawback of the module-based stack is that it supports only a single stack object. All clients of the stack module effectively share the same stack. Sometimes we want this feature: a stack can serve as a shared-memory object for multiple modules. But to implement a true stack datatype, we need to use classes.

To illustrate, let's define a full-featured stack class. The Stack class shown in Example 17-2 defines a new datatype, with a variety of behavior. Like the module, the class uses a Python list to hold stacked objects. But this time, each instance gets its own list. The class defines both "real" methods, and specially named methods that implement common type operations. Comments in the code describe special methods.

Example 17-2. PP2EDstructBasicstack2.py

error = 'stack2.error' # when imported: local exception

class Stack:
 def __init__(self, start=[]): # self is the instance object
 self.stack = [] # start is any sequence: stack..
 for x in start: self.push(x) 
 self.reverse( ) # undo push's order reversal
 def push(self, obj): # methods: like module + self
 self.stack = [obj] + self.stack # top is front of list
 def pop(self):	
 if not self.stack: raise error, 'underflow'
 top, self.stack = self.stack[0], self.stack[1:]
 return top
 def top(self):
 if not self.stack: raise error, 'underflow'
 return self.stack[0]
 def empty(self):
 return not self.stack # instance.empty( )

 # overloads
 def __repr__(self):
 return '[Stack:%s]' % self.stack # print, backquotes,..
 def __cmp__(self, other): 
 return cmp(self.stack, other.stack) # '==', '>, '<=', '!=',..
 def __len__(self): 
 return len(self.stack) # len(instance), not instance
 def __add__(self, other): 
 return Stack(self.stack + other.stack) # instance1 + instance2
 def __mul__(self, reps): 
 return Stack(self.stack * reps) # instance * reps
 def __getitem__(self, offset): 
 return self.stack[offset] # intance[offset], in, for
 def __getslice__(self, low, high): 
 return Stack(self.stack[low : high]) # instance[low:high]
 def __getattr__(self, name):
 return getattr(self.stack, name) # instance.sort()/reverse( )/..

Now distinct instances are created by calling the Stack class like a function. In most respects, the Stack class implements operations exactly like the stack module in Example 17-1. But here, access to the stack is qualified by self, the subject instance object. Each instance has its own stack attribute, which refers to the instance's own list. Furthermore, instance stacks are created and initialized in the __init__ constructor method, not when the module is imported. Let's make a couple of stacks to see how this all works in practice:

>>> from stack2 import Stack
>>> x = Stack( ) # make a stack object, push items
>>> x.push('spam')
>>> x.push(123)
>>> x # __repr__ prints a stack
[Stack:[123, 'spam']]

>>> y = Stack( ) # two distinct stacks objects
>>> y.push(3.1415) # they do not share content
>>> y.push(x.pop( ))
>>> x, y
([Stack:['spam']], [Stack:[123, 3.1415]])


>>> z = Stack( ) # third distinct stack object
>>> for c in 'spam': z.push(c)
...
>>> while z: print z.pop( ),  # __len__ tests stack truth
...
m a p s

>>> z = x + y # __add__ handles stack +
>>> z # holds three different types
[Stack:['spam', 123, 3.1415]]
>>> for item in z: print item,  # __getitem__ does for
...
spam 123 3.1415

Like lists and dictionaries, Stack defines both methods and operators for manipulating instances by attribute qualification and expressions. Additionally, it defines the __getattr__ metaclass method to intercept references to attributes not defined in the class and to route them to the wrapped list object (to support list methods: sort, append, reverse, etc.). Many of the module's operations become operators in the class. Table 17-2 shows the equivalence of module and class operations (columns 1 and 2) and gives the class method that comes into play for each (column 3).

Table 17-2. Module/Class Operation Comparison

Module Operations	Class Operations	Class Method
module.empty( )	not instance	__len__
module.member(x)	x in instance	__getitem__
module.item(i)	instance[i]	__getitem__
module.length( )	len(instance)	__len__
module.dump( )	print instance	__repr__
range( ) counter loops	for x in instance	__getitem__
manual loop logic	instance + instance	__add__
module.stack.reverse( )	instance.reverse( )	__getattr__
module.push/pop/top	instance.push/pop/top	push/pop/top

In effect, classes let us extend Python's set of built-in types with reusable types implemented in Python modules. Class-based types may be used just like built-in types: depending on which operation methods they define, classes can implement numbers, mappings, and sequences, and may be mutable or not. Class-based types may also fall somewhere in between these categories.

17.2.3 Customization: Performance Monitors

So far we've seen how classes support multiple instances and integrate better with Python's object model by defining operator methods. One of the other main reasons for using classes is to allow for future extensions and customizations. By implementing stacks with a class, we can later add subclasses that specialize the implementation for new demands.

For instance, suppose we've started using the Stack class in Example 17-2, but we start running into performance problems. One way to isolate bottlenecks is to instrument data structures with logic that keeps track of usage statistics, which we can analyze after running client applications. Because Stack is a class, we can add such logic in a new subclass, without affecting the original stack module (or its clients). The subclass in Example 17-3 extends Stack to keep track of overall push/pop usage frequencies and to record the maximum size of each instance.

Example 17-3. PP2EDstructBasicstacklog.py

from stack2 import Stack # extends imported Stack

class StackLog(Stack): # count pushes/pops, max-size
 pushes = pops = 0 # shared/static class members
 def __init__(self, start=[]): # could also be module vars
 self.maxlen = 0
 Stack.__init__(self, start)
 def push(self, object): 
 Stack.push(self, object) # do real push
 StackLog.pushes = StackLog.pushes + 1 # overall stats
 self.maxlen = max(self.maxlen, len(self)) # per-instance stats
 def pop(self): 
 StackLog.pops = StackLog.pops + 1 # overall counts
 return Stack.pop(self) # not 'self.pops': instance
 def stats(self):
 return self.maxlen, self.pushes, self.pops # get counts from instance

This subclass works the same as the original Stack; it just adds monitoring logic. The new stats method is used to get a statistics tuple through an instance:

>>> from stacklog import StackLog
>>> x = StackLog( )
>>> y = StackLog( ) # make two stack objects
>>> for i in range(3): x.push(i) # and push object on them
...
>>> for c in 'spam': y.push(c)
...
>>> x, y # run inherited __repr__
([Stack:[2, 1, 0]], [Stack:['m', 'a', 'p', 's']])
>>> x.stats(), y.stats( )
((3, 7, 0), (4, 7, 0))
>>>
>>> y.pop(), x.pop( )
('m', 2)
>>> x.stats(), y.stats( ) # my maxlen, all pushes, all pops
((3, 7, 2), (4, 7, 2))

Notice the use of class attributes to record overall pushes and pops, and instance attributes for per-instance maximum length. By hanging attributes on different objects, we can expand or narrow their scopes.

17.2.4 Optimization: Tuple Tree Stacks

One of the nice things about wrapping objects up in classes is that you are free to change the underlying implementation without breaking the rest of your program. Optimizations can be added in the future, for instance, with minimal impact; the interface is unchanged, even if the internals are. There are a variety of ways to implement stacks, some more efficient than others. So far, our stacks have used slicing and concatenation to implement pushing and popping. This method is relatively inefficient: both operations make copies of the wrapped list object. For large stacks, this practice can add a significant time penalty.

One way to speed up such code is to change the underlying data structure completely. For example, we can store the stacked objects in a binary tree of tuples: each item may be recorded as a pair: (object, tree), where object is the stacked item, and tree is either another tuple pair giving the rest of the stack or None to designate an empty stack. A stack of items [1,2,3,4] would be internally stored as a tuple tree (1,(2,(3,(4,None)))).

This tuple-based representation is similar to the notion of "cons-cells" in Lisp-family languages: the object on the left is the car, and the rest of the tree on the right is the cdr. Because we add or remove only a top tuple to push and pop items, this structure avoids copying the entire stack. For large stacks, the benefit might be significant. The next class, shown in Example 17-4, implements these ideas.

Example 17-4. PP2EDstructBasicstack3.py

class Stack:
 def __init__(self, start=[]): # init from any sequence
 self.stack = None # even other (fast)stacks
 for i in range(-len(start), 0): 
 self.push(start[-i - 1]) # push in reverse order
 def push(self, node): # grow tree 'up/left'
 self.stack = node, self.stack # new root tuple: (node, tree)
 def pop(self): 
 node, self.stack = self.stack # remove root tuple
 return node # TypeError if empty
 def empty(self): 
 return not self.stack # is it 'None'?
 def __len__(self): # on: len, not
 len, tree = 0, self.stack
 while tree:
 len, tree = len+1, tree[1] # visit right subtrees
 return len
 def __getitem__(self, index): # on: x[i], in, for
 len, tree = 0, self.stack
 while len < index and tree: # visit/count nodes
 len, tree = len+1, tree[1] 
 if tree:
 return tree[0] # IndexError if out-of-bounds
 else: raise IndexError # so 'in' and 'for' stop
 def __repr__(self): return '[FastStack:' + `self.stack` + ']' 

This class's __getitem__ method handles indexing, in tests, and for loop iteration as before, but this version has to traverse a tree to find a node by index. Notice that this isn't a subclass of the original Stack class. Since nearly every operation is implemented differently here, inheritance won't really help. But clients that restrict themselves to the operations that are common to both classes can still use them interchangeably -- they just need to import a stack class from a different module to switch implementations. Here's a session with this stack version; as long as we stick to pushing, popping, indexing, and iterating, this version is essentially indistinguishable from the original:

>>> from stack3 import Stack
>>> x = Stack( )
>>> y = Stack( )
>>> for c in 'spam': x.push(c)
...
>>> for i in range(3): y.push(i)
...
>>> x
[FastStack:('m', ('a', ('p', ('s', None))))]
>>> y
[FastStack:(2, (1, (0, None)))]

>>> len(x), x[2], x[-1]
(4, 'p', 'm')
>>> x.pop( )
'm'
>>> x
[FastStack:('a', ('p', ('s', None)))]
>>>
>>> while y: print y.pop( ),
...
2 1 0

17.2.5 Optimization: In-place List Modifications

Perhaps a better way to speed up the stack object, though, is to fall back on the mutability of Python's list object. Because lists can be changed in place, they can be modified more quickly than any of the prior examples. In-place change operations like append are prone to complications when a list is referenced from more than one place. But because the list inside the stack object isn't meant to be used directly, we're probably safe here. The module in Example 17-5 shows one way to implement a stack with in-place changes; some operator overloading methods have been dropped to keep this simple. The new Python pop method it uses is equivalent to indexing and deleting the item at offset -1 (top is end-of-list here).

Example 17-5. PP2EDstructBasicstack4.py

error = 'stack4.error' # when imported: local exception

class Stack:
 def __init__(self, start=[]): # self is the instance object
 self.stack = [] # start is any sequence: stack..
 for x in start: self.push(x) 
 def push(self, obj): # methods: like module + self
 self.stack.append(obj) # top is end of list
 def pop(self):	
 if not self.stack: raise error, 'underflow'
 return self.stack.pop( ) # like fetch and delete stack[-1]
 def top(self):
 if not self.stack: raise error, 'underflow'
 return self.stack[-1]
 def empty(self):
 return not self.stack # instance.empty( )
 def __len__(self): 
 return len(self.stack) # len(instance), not intance
 def __getitem__(self, offset): 
 return self.stack[offset] # instance[offset], in, for
 def __repr__(self): return '[Stack:%s]' % self.stack 

This version works like the original in module stack2, too -- just replace stack2 with stack4 in the previous interaction to get a feel for its operation. The only obvious difference is that stack items are in reverse when printed (i.e., the top is the end):

>>> from stack4 import Stack
>>> x = Stack( )
>>> x.push('spam')
>>> x.push(123)
>>> x
[Stack:['spam', 123]]
>>>
>>> y = Stack( )
>>> y.push(3.1415)
>>> y.push(x.pop( ))
>>> x, y
([Stack:['spam']], [Stack:[3.1415, 123]])
>>> y.top( )
123

17.2.6 Timing the Improvements

The in-place changes stack object probably runs faster than both the original and the tuple-tree version, but the only way to really be sure how much faster is to time the alternative implementations. Since this could be something we'll want to do more than once, let's first define a general module for timing functions in Python. In Example 17-6, the built-in time module provides a clock function that we can use to get the current CPU time in floating-point seconds, and the function timer.test simply calls a function reps times and returns the number of elapsed seconds by subtracting stop from start CPU times.

Example 17-6. PP2EDstructBasic imer.py

def test(reps, func, *args):
 import time
 start = time.clock( ) # current CPU tim in float seconds
 for i in xrange(reps): # call function reps times
 apply(func, args) # discard any return value
 return time.clock( ) - start # stop time - start time

Next, we define a test driver script (see Example 17-7). It expects three command-line arguments: the number of pushes, pops, and indexing operations to perform (we'll vary these arguments to test different scenarios). When run at the top level, the script creates 200 instances of the original and optimized stack classes, and performs the specified number of operations on each stack.[2] Pushes and pops change the stack; indexing just accesses it.

[2] If you have a copy of the first edition of this book lying around, you might notice that I had to scale all test factors way up to get even close to the run times I noticed before. Both Python and chips have gotten a lot faster in five years.

Example 17-7. PP2EDstructBasicstacktime.py

import stack2 # list-based stacks: [x]+y
import stack3 # tuple-tree stacks: (x,y)
import stack4 # in-place stacks: y.append(x)
import timer # general function timer function

rept = 200
from sys import argv
pushes, pops, items = eval(argv[1]), eval(argv[2]), eval(argv[3])

def stackops(stackClass):
 #print stackClass.__module__
 x = stackClass('spam') # make a stack object
 for i in range(pushes): x.push(i) # exercise its methods
 for i in range(items): t = x[i]
 for i in range(pops): x.pop( )

print 'stack2:', timer.test(rept, stackops, stack2.Stack) # pass class to test
print 'stack3:', timer.test(rept, stackops, stack3.Stack) # rept*(push+pop+ix)
print 'stack4:', timer.test(rept, stackops, stack4.Stack)

Here are some of the timings reported by the test driver script. The three outputs represent the measured run times in seconds for the original, tuple, and in-place stacks. For each stack type, the first test creates 200 stack objects and performs roughly 120,000 stack operations (200 rept x (200 pushes + 200 indexes + 200 pops)), in the test duration times listed. These results were obtained on a 650 MHz Pentium III Windows machine, and a Python 1.5.2 install:

C:...PP2EDstructBasic>python stacktime.py 200 200 200
stack2: 1.67890008213
stack3: 7.70020952413
stack4: 0.694291724635

C:...PP2EDstructBasic>python stacktime.py 200 50 200
stack2: 1.06876246669
stack3: 7.48964866994
stack4: 0.477584270605

C:...PP2EDstructBasic>python stacktime.py 200 200 50
stack2: 1.34536448817
stack3: 0.795615917129
stack4: 0.57297976835

C:...PP2EDstructBasic>python stacktime.py 200 200 0
stack2: 1.33500477715
stack3: 0.300776077373
stack4: 0.533050336077

If you look closely enough, you'll notice that the results show that the tuple-based stack (stack3) performs better when we do more pushing and popping, but worse if we do much indexing. Indexing lists is extremely fast for built-in lists, but very slow for tuple trees -- the Python class must traverse the tree manually. The in-place change stacks (stack4) are almost always fastest, unless no indexing is done at all -- tuples won by a hair in the last test case. Since pushes and pops are most of what clients would do to a stack, tuples are a contender, despite their poor indexing performance. Of course, we're talking about fractions of a second after many tens of thousands of operations; in many applications, your users probably won't care either way.