Stacks in Python

A stack is a collection of objects that supports fast last-in, first-out (LIFO) semantics for inserts and deletes. Unlike lists or arrays, stacks typically don’t allow for random access to the objects they contain. The insert and delete operations are also often called push and pop.

A useful real-world analogy for a stack data structure is a stack of plates:

New plates are added to the top of the stack. And because the plates are precious and heavy, only the topmost plate can be moved (last-in, first-out). To reach the plates lower down in the stack the topmost plates must be removed one by one.

Stacks and queues are similar. They’re both linear collections of items and the difference lies in the order that items are accessed in:

With a queue you remove the item least recently added (first-in, first-out or FIFO); and with a stack you remove the item most recently added (last-in, first-out or LIFO).

Performance-wise, a proper stack implementation is expected to take O(1) time for insert and delete operations.

Stacks have a wide range of uses in algorithms, for example in language parsing and runtime memory management (“call stack”). A short and beautiful algorithm using a stack is depth-first search (DFS) on a tree or graph data structure.

Python ships with several stack implementations that each have slightly different characteristics. Let’s take a look at them:

✅ The list Built-in

Python’s built-in list type makes a decent stack data structure as it supports push and pop operations in amortized O(1) time.

Python’s lists are implemented as dynamic arrays internally which means they occasional need to resize the storage space for elements stored in them when elements are added or removed. The list over-allocates its backing storage so that not every push or pop requires resizing and you get an amortized O(1) time complexity for these operations.

The downside is that this makes their performance less consistent than the stable O(1) inserts and deletes provided by a linked list based implementation (like collections.deque, see below). On the other hand lists do provide fast O(1) time random access to elements on the stack which can be an added benefit.

Here’s an important performance caveat when using lists as stacks:

To get the amortized O(1) performance for inserts and deletes new items must be added to the end of the list with the append() method and removed again from the end using pop(). Stacks based on Python lists grow to the right and shrink to the left.

Adding and removing from the front is much slower and takes O(n) time, as the existing elements must be shifted around to make room for the new element.

# How to use a Python list as a stack (LIFO):

s = []

s.append('eat')
s.append('sleep')
s.append('code')

>>> s
['eat', 'sleep', 'code']

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
IndexError: "pop from empty list"

✅ The collections.deque Class

The deque class implements a double-ended queue that supports adding and removing elements from either end in O(1) time (non-amortized).

Because deques support adding and removing elements from either end equally well, they can serve both as queues and as stacks.

Python’s deque objects are implemented as doubly-linked lists which gives them excellent and consistent performance for inserting and deleting elements, but poor O(n) performance for randomly accessing elements in the middle of the stack.

collections.deque is a great choice if you’re looking for a stack data structure in Python’s standard library with the performance characteristics of a linked-list implementation.

# How to use collections.deque as a stack (LIFO):

from collections import deque
q = deque()

q.append('eat')
q.append('sleep')
q.append('code')

>>> q
deque(['eat', 'sleep', 'code'])

>>> q.pop()
'code'
>>> q.pop()
'sleep'
>>> q.pop()
'eat'

>>> q.pop()
IndexError: "pop from an empty deque"

✅ The queue.LifoQueue Class

This stack implementation in the Python standard library is synchronized and provides locking semantics to support multiple concurrent producers and consumers.

The queue module contains several other classes implementing multi-producer, multi-consumer queues that are useful for parallel computing.

Depending on your use case the locking semantics might be helpful, or just incur unneeded overhead. In this case you’d be better off with using a list or a deque as a general purpose stack.

# How to use queue.LifoQueue as a stack:

from queue import LifoQueue
s = LifoQueue()

s.put('eat')
s.put('sleep')
s.put('code')

>>> s
<queue.LifoQueue object at 0x108298dd8>

>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'

>>> s.get_nowait()
queue.Empty

>>> s.get()
# Blocks / waits forever...

A good default choice: collections.deque

If you’re not looking for parallel processing support (or don’t want to handle locking and unlocking manually) your choice comes down to the built-in list type or collections.deque.

The difference lies in the data structure used behind the scenes and ease of use.

• list is backed by a dynamic array which makes it great for fast random access but requires occasional resizing when elements are added or removed. The list over-allocates its backing storage so that not every push or pop requires resizing and you get an amortized O(1) time complexity for these operations. But you do need to be careful to only insert and remove items from the right-hand side (append and pop) or otherwise performance slows down to O(n).

• collections.deque is backed by a doubly-linked list which optimizes appends and deletes at both ends and provides consistent O(1) performance for these operations. Not only is its performance more stable, the deque class is also easier to use because you don’t have to worry about adding or removing items from “the wrong end.”

For these reasons, collections.deque makes an excellent choice for implementing a stack (LIFO queue) data structure in Python.

Read the full “Fundamental Data Structures in Python” article series here. This article is missing something or you found an error? Help a brother out and leave a comment below.