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 |
|
|
|
Push |
|
|
|
Pop[a] |
|
|
|
[a] In fact, Python 1.5 introduced a list
|
Get Programming Python, Second Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.