Stacks in Python — A Practical Guide to LIFO Data Structures
Before we talk tech, which can feel pretty abstract until you get familiar with the concepts, let’s ground it in something real. Let’s talk pancakes.
Imagine you’re making pancakes. Every time you finish making a pancake, you place it on the “ready to eat” plate right on top of the last one. You’re not lifting up all the pancakes to slide the new one underneath, and you’re not splitting the pancakes in half to squeeze it in the middle. You’re just adding to the top of the pile, one by one.
Now it’s time to eat. You peel off the pancake on top, then the one underneath, and so on. You’re not reaching into the middle or pulling out the one on the bottom; you’re taking them in the reverse order you placed them on the plate.
That’s the basic idea behind a stack. Making and eating pancakes follows the Last In First Out (LIFO) principle. LIFO simply means the last item added is the first one taken out.
Why Stacks Matter in Programming
Yes, in the example of pancakes, you can add or remove a pancake from any place in the pancake stack, but in programming stacks, only the top element on the stack is accessible. Their LIFO architecture makes stacks ideal for:
- Reversing data like using “undo” to reverse actions in apps like Photoshop or Google Docs.
- Traversing trees or graphs to complete a depth-first search (DFS) when navigating folder structures or parsing hierarchical data (JSON, XML)
- Managing function calls using the call stack which keeps track of where each function should return after executing
Stacks are easy to implement. Python has multiple built-in ways to work with them.
Implementing a Stack in Python
Python doesn’t have a built-in Stack class like list or set but you can create a custom class when needed. There are several ways to create a stack based on what you’re using it for.
Using Native Lists (append / pop)
Native lists make simple, fast small stacks. Native lists are a great choice when you need quick stack implementation for small to medium data sets. Think individual scripts and small applications. Native lists are inefficient when it comes to thread safety and large data volumes.
You can make a native list by using Python’s built-in list data structure with stack operations like push() to add an element to and pop() to remove an element from the top of the stack.
Output: 2
Leveraging collections.deque
Use collections.deque when you need a fast, memory-efficient stack. collections.deque is great for large stacks in applications that demand high performance. An example of this use case is when you’re app involves single-producer/ single-consumer threading.
collections.deque is faster and more memory efficient than appends and pops through it does require a little more overhead. It’s thread-safe for single-producer/ single-consumer but not for multithreaded scenarios.
Output: 2
Thread-Safe Stacks With queue.LifoQueue
queue.LifoQueue creates stacks for programs where thread safety is critical and you need built-in locking mechanisms to avoid race conditions. This is a great option for multi-threaded applications where multiple threads push() and pop() concurrently. queue.LifoQueue is slightly slower than native lists or collection.deque due to the locking mechanisms.
Output: 2
Building a Custom Stack Class
When you want to build-in custom behavior, validation, or enforce constraints, your best option is to build a custom stack class. Custom classes gives you more control over stack operations such as adding custom error handling or working with additional methods.
Core Stack Operations
Understanding fundamental stack operations is key to maximizing your stack’s capabilities.
push
Adds or inserts an item to the top of the stack
pop()
Removes and returns the top item
peek/ top
Returns the top item without removing it
is_empty and size checks
Quickly check if the stack is empty or how many elements it holds.
The code below walks through what all the operations will look like on a single stack.
Output:
original stack: [‘a’, ‘b’, ‘c’]
after push(‘d’): [‘a’, ‘b’, ‘c’, ‘d’]
after peek(): d
after pop(): d
current stack: [‘a’, ‘b’, ‘c’]
Is empty? False
Size: 3
Real-World Use Cases for Stacks
Stacks, like pancakes, are everywhere. You just need to know where to look sometimes.
Expression and Evaluation Parsing
Stacks help evaluate infix/postfix expressions and parse nested structures like parentheses, HTML tags, or programming syntax.
You can find the expression and evaluation parsing stack use case in compilers/ interpreters, calculator apps, syntax parsing, and HTML/XML tag validation.
Undo/redo Functionality
Two stacks can track user actions, one for undo and the second for redo.
Most people (if not all people) are familiar with this one. You can find it in word processors, design tools, and code editors.
Outputs:
Undo stack: []
Redo stack: [‘typed: hello’]
Undo stack: [‘typed: hello’]
Redo stack: []
Depth-First Search and Backtracking
Stacks can explore paths and make decisions in DFS or backtracking algorithms.
You can find depth-first search and backtracking in maze-solving and puzzle games, AI logic, and search engines.
Output:
Start: stack=[‘A’], visited=set()
Popped: A
Visited: {‘A’}, stack: [‘B’, ‘C’]
Popped: C
Visited: {‘A’, ‘C’}, stack: [‘B’, ‘E’, ‘F’]
Popped: F
Visited: {‘A’, ‘C’, ‘F’}, stack: [‘B’, ‘E’]
Popped: E
Visited: {‘A’, ‘C’, ‘F’, ‘E’}, stack: [‘B’]
Popped: B
Visited: {‘E’, ‘C’, ‘F’, ‘B’, ‘A’}, stack: [‘D’]
Popped: D
Visited: {‘E’, ‘C’, ‘F’, ‘B’, ‘A’, ‘D’}, stack: []
{‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’}
Performance and Complexity Considerations
Part of picking the right stack implementation means understanding its performance and memory characteristics.
Time Complexity
The core stack operations like push, pop, and peek are all O(1) regardless of whether you’re usikng a native list, collections.deque, or queue.LifoQueue. They all take roughly the same amount of time regardless of stack size.
This doesn’t mean they all offer the exact same performance capabilities. collections.deque and queue.LifoQueue offer more reliable performance under heavy load or in multi-threaded scenarios.
Memory Overhead and Garbage Collection
Memory usage varies more noticeably between different implementations.
collections.deque is optimized for memory management. It efficiently handles additions and removals without significant overhead.
queue.LifoQueue was designed for thread safety and comes with additional locking mechanisms. This introduces slight memory overhead per element when compared to collections.deque or a native list. The trade-off is worth it for multi-threaded applications.
Native lists can sometimes cause spikes in memory use when stacks grow and shrink frequently. This happens because they over-allocate memory to optimize push and pop operations, occasionally holding memory they don’t need.
Handling Large Data Volumes Efficiently
collections.deque is the most memory- and speed-efficient option for large or persistent stacks. It avoids the memory churn that comes with list resizing.
Testing and Benchmarking Your Stack
With everything stated above, here are some tips on how to test and benchmark stacks you build.
Microbenchmarking With timeit
timeit measures the speed of your stack operations. It’s useful when comparing different implementations or optimizing performance in high-frequency operations.
timeit is a great solution when fine-tuning code for performance-critical situations. Think game loops, data processing, and high-traffic APIs.
Basic syntax
Example
Output will vary based on your system.
Unit Testing With pytest
pytest catches bugs. It’s a good idea to use pytest before pushing code. It’s especially useful when working with custom stack logic or handling edge cases. Think applications that need data integrity like banking and e-commerce.
Basic syntax
Example
stack.py – Custom stack
Test_stack.py – the test file
Run pytest in the terminal with the command $ pytest -v
Output will vary based on your system.
Common Pitfalls and Debugging Tips
As much as I personally can’t stand this part, it’s a natural part of the coding process…
Empty Stack Pops and Index Errors
If you try to pop from an empty stack, Python will raise an IndexError. Always check if the stack has items before popping.
Mutable Default Arguments in Class Methods
Avoid using [] (or other mutable types) as a default argument in a method or constructor. It can cause shared state across different instances of your class.
Conclusion
Stacks are popular to use in Python applications because they’re easy to build, use, and offer a lot of functionality. That said, even if they’re less complicated than some of Python’s other data structures, it’s important to understand which tool to use for which circumstance. This guide is more than enough to get started. Happy coding!
