5.11 Simulating Stacks with Lists

The preceding chapter introduced the function-call stack. Python does not have a built-in stack type, but you can think of a stack as a constrained list. You push using list method append, which adds a new element to the end of the list. You pop using list method pop with no arguments, which removes and returns the item at the end of the list.

Let’s create an empty list called stack, push (append) two strings onto it, then pop the strings to confirm they’re retrieved in last-in, first-out (LIFO) order:


In [1]: stack = []

In [2]: stack.append('red')

In [3]: stack
Out[3]: ['red']

In [4]: stack.append('green')

In [5]: stack
Out[5]: ['red', 'green']

In [6]: stack.pop()
Out[6]: 'green'

In [7]: stack
Out[7]: ['red']

In [8]: stack.pop()
Out[8]: 'red'

In [9]: stack
Out[9]: []

In [10]: stack.pop()
-------------------------------------------------------------------------
IndexError                              Traceback (most recent call last)
<ipython-input-10-50ea7ec13fbe> in <module>()
----> 1 stack.pop()

IndexError: pop from empty list

For each pop snippet, the value that pop removes and returns is displayed. Popping from an empty stack causes an IndexError, just like accessing a nonexistent list element with []. To prevent an IndexError, ensure that len(stack) is greater than 0 before calling pop. You can run out of memory if you keep pushing items faster than you pop them.

In the exercises, you’ll use a list to simulate another popular collection called a queue in which you insert at the back and delete from the front. Items are retrieved from queues in first-in, first-out (FIFO) order.

tick mark Self Check

  1. (Fill-In) You can simulate a stack with a list, using methods _____ and _____ to add and remove elements, respectively, only at the end of the list.
    Answer: append, pop.

  2. (Fill-In) To prevent an IndexError when calling pop on a list, first ensure that _____.
    Answer: the list’s length is greater than 0.