raise IndexError() # so 'in' and 'for' stop
def repr(self):
return '[FastStack:' + repr(self.stack) + ']'
This class’s getitem method handles indexing, in tests, and for loop iteration as
before (when no iter is defined), 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 cli-
ents 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 mod-
ule 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 indistin-
guishable 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(), end=' ')
...
2 1 0 >>>Optimization: In-Place List Modifications
The last section tried to speed up pushes and pops with a different data structure, but
we might also be able to speed up our stack object by falling 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 such as 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.
The module in Example 18-5 shows one way to implement a stack with in-place
changes; some operator overloading methods have been dropped to keep this simple.
The Python pop method it uses is equivalent to indexing and deleting the item at
Implementing Stacks| 1369