Python objects can be implemented in either Python or an integrated language such as
C. Types coded in C use patterns similar to those here.
In the end, though, we’ll also see that Python’s built-in support can often take the place
of homegrown solutions in this domain. Although custom data structure implemen-
tations are sometimes necessary and still have much to offer in terms of code mainte-
nance and evolution, they are not always as paramount in Python as they are in less
programmer-friendly languages.
Implementing Stacks
Stacks are a common and straightforward data structure, used in a variety of applica-
tions: language processing, graph searches, and so on. For instance, expression evalu-
ation in the next chapter’s calculator GUI is largely an exercise in juggling stacks, and
programming languages in general typically implement function calls as stack opera-
tions in order to remember what to resume as calls return. Stacks can also help in XML
parsing: they are a natural for tracking progress any time constructs might be arbitrarily
nested.
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. Unlike the queues we used for thread
communication, which add and delete at opposite ends, all the activity in stacks hap-
pens at the top. 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
whether the stack is empty, fetching the top item without popping it, iterating over a
stack’s items, testing for item membership, and so on.
Built-in Options
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.
Table 18-1. Stacks as lists
Operation Top is end-of-list Top is front-of-list Top is front-of-list
New stack=['a', 'b'] stack=['b', 'a'] stack=['b', 'a']
Push stack.append('c') stack.insert(0,'c') stack[0:0]=['c']1360 | Chapter 18: Data Structures