Programming Python (179 page)

• Pushing items onto the top
  

• Popping items off the top
  

In Python, a
simple list is often adequate for implementing a stack:
because we can change lists in place arbitrarily, we can add and delete
items from either the beginning (left) or the end (right).
Table 18-1
summarizes various built-in operations
available for implementing stack-like behavior with Python lists and
in-place changes. They vary depending on whether the stack “top” is the
first or the last node in the list; in this table, the string
'b'
is the initial top item on the
stack.

Even more conveniently, Python grew a list
pop
method later in its life designed to be
used in conjunction with
append
to
implement stacks and other common structures such as queues, yielding
the even simpler coding options listed in
Table 18-2
.

By default,
pop
is equivalent
to fetching, and then deleting, the last item at offset −1. With an
argument,
pop
deletes and returns the
item at that offset—
list.pop(-1)
is
the same as
list.pop()
. For in-place
change operations like
append
,
insert
,
del
, and
pop
, no new list is created in memory, so
execution is quick (performance may further depend upon which end is the
“top,” but this in turn depends on Python’s current list implementation,
as well as measurement concepts we’ll explore later). Queues can be
coded similarly, but they pop at the other end of the list.

Other built-in coding schemes are possible as well. For instance,
del stack[:1]
is yet another way to
delete the first item in a list-based stack in-place. Depending on which
end is interpreted as the top of the stack, the following sequence
assignment statement forms can be used to fetch and remove the top item
as well, albeit at the cost of making a new list object each
time:

# top is front of list
top, stack = stack[0], stack[1:]        # Python 1.X+
top, *stack = stack                     # Python 3.X
# top is end of list
stack, top = stack[:-1], stack[-1]      # Python 1.X+
*stack, top = stack                     # Python 3.X

With so many built-in stack options, why bother implementing
others? For one thing, they serve as a simple and familiar context for
exploring data structure concepts in this book. More importantly,
though, there is a practical programming motive here. List
representations work and will be relatively fast, but they also bind
stack-based programs to the stack representation chosen: all stack
operations will be hardcoded throughout a program. If we later want to
change how a stack is represented or extend its basic operation set,
we’re stuck—every stack-based program will have to be updated, and in
every place where it accesses the stack.

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 update may be
nontrivial work. As we’ll discuss in
Chapter 20
, 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.

As we’ll see later, built-in types such as lists are actually
class-like objects in Python that we can subclass to customize, too.
This might be only a partial fix, though; unless we anticipate future
changes and make instances of a subclass, we may still have a
maintenance issue if we use built-in list operations directly and ever
want to extend what they do in the
future.

Of course, the real solution to
such code maintenance dilemmas is to
encapsulate
—that is, wrap up—stack implementations
behind interfaces, using Python’s code reuse tools. As long as clients
stick to using the interfaces, we’re free to change the interfaces’
implementations arbitrarily without having to change every place they
are called. Let’s begin by implementing a stack as a module containing a
Python list, plus functions to operate on it;
Example 18-1
shows one way to code
this.

"a shared stack module"
stack = []                                   # on first import
class error(Exception): pass                 # local excs, stack1.error
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                      # 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: the 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 simple wrapper around a Python list. Because this extra layer of
interface logic makes clients independent of the actual implementation
of the stack, though, 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—it implements a stack of arbitrary Python
objects:

C:\...\PP4E\Dstruct\Basic>
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()
True
>>>
for c in 'spam': stack1.push(c)
...
>>>
while not stack1.empty():
...
print(stack1.pop(), end=' ')
...
m a p s >>>
>>>
stack1.pop()
stack1.error: stack underflow

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
). Nothing is preventing clients from
accessing (and even changing)
stack1.stack
directly, but doing so defeats
the purpose of interfaces like this
one:

>>>
for c in 'spam': stack1.push(c)
...
>>>
stack1.dump()

>>>
>>>
for i in range(stack1.length()):
...
print(stack1.item(i), end=' ')
...
m a p s >>>

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 that
can generate independent objects, we need to use classes.

To illustrate, let’s define a full-featured stack
class
. The
Stack
class shown in
Example 18-2
defines a new datatype with a variety of behaviors. 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.

"a multi-instance stack class"
class error(Exception): pass                 # 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
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, repr(),..
def __eq__(self, other):
return 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):                # see also __iter__
return self.stack[offset]                 # instance[i], [i:j], in, for
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 18-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 first imported. Let’s make a
couple of stacks to see how all this 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 stack 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:
# __len__ tests stack truth
...
print(z.pop(), end=' ')
...
m a p s >>>
>>>
z = x + y
# __add__ handles stack +
>>>
z
# holds three different types
[Stack:['spam', 123, 3.1415]]
>>>
for item in z:
# __getitem__ does for
...
print(item, end=' ')
...
spam 123 3.1415 >>>
>>>
z.reverse()
# __getattr__ delegates to list
>>>
z
[Stack:[3.1415, 123, 'spam']]

Like lists and dictionaries,
Stack
defines both methods and operators for
manipulating instances by attribute references and expressions.
Additionally, it defines the
__getattr__
special 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
, and so on). Many of the module’s
operations become operators in the class.
Table 18-3
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).

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 or may not be mutable. Class-based types may also fall somewhere in
between these
categories.