O'Reilly logo

Programming Python, Second Edition by Mark Lutz

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

stack=['a','b','c']

stack=['c','b','a']

stack=['c','b','a']

Push

stack.append('d')

stack.insert(0,'d')

stack[0:0] = ['d']

Pop[a]

X = stack[-1];

del stack[-1]

x = stack[0];

del stack[:1]

x = stack[0];

stack[:1] = []

[a] In fact, Python 1.5 introduced a list pop method designed to be used in conjunction with append to implement stacks: to push ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required