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 extended
sequence assignment 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 18-4, implements these ideas.
Example 18-4. PP4E\Dstruct\Basic\stack3.py
"optimize with tuple pair trees"
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:
1368 | Chapter 18: Data Structures