Skip to Main Content
Programming Python, 3rd Edition
book

Programming Python, 3rd Edition

by Mark Lutz
August 2006
Intermediate to advanced content levelIntermediate to advanced
1600 pages
51h 46m
English
O'Reilly Media, Inc.
Content preview from Programming Python, 3rd Edition

Implementing Stacks

Stacks are a common and straightforward data structure, used in a variety of applications: language processing, graph searches, and so on. 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 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.

In Python, a simple list is often adequate for implementing a stack: because we can change lists in place, we can add and delete items from either the beginning (left) or the end (right). Table 20-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 the last node in the list. In this table, the string 'c' is the top item on the stack.

Table 20-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

x = stack[-1];

del stack[-1]

x = stack[0];

del stack[:1]

x = stack[0];

stack[:1] = []

Other coding schemes are possible as well. For instance, Python 1.5 introduced a list pop method designed to be used in conjunction with append to implement ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Learning Python, 3rd Edition

Learning Python, 3rd Edition

Mark Lutz

Publisher Resources

ISBN: 0596009259Supplemental ContentErrata Page