A stack is a linear data structure where inserted elements are kept in insertion order and only the last one to be added is removed, this is also known as LIFO (last in first out) behavior.
A traditional Stack supports three operations:
- Insertion or push
- Peek or top
- Deletion or pop
Execution times for both operations can vary slightly depending on the implementation, all three can be executed in constant times O(1) with the right data structure.
Examples
Consider the following list of numbers, let's assume the last element in the list is the last one to be inserted:
stack = [1, 7, 5, 6, 5, 12, 4]
The following operations will produce the following results and the list will behave like a stack:
stack = [1, 7, 5, 6, 5, 12, 4]
stack.pop() # Pop is a deletion operation and number 4 has been removed from the stack
print(stack[-1]) # 12 - This gives us the element at the top of the stack which is a peek operation
print(stack) # [1, 7, 5, 6, 5, 12]
stack.append(30) # Append is an insertion operation and adds an element at the end of the list
#Number 30 has been added
print(stack) # [1, 7, 5, 6, 5, 12, 30]
Let's analyze another example:
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack) # [1, 2, 3]
print(stack.pop()) # 3
print(stack.pop()) # 2
print(stack.pop()) # 1
print(stack) # []
As you can see, printing the values that are removed from the stack will give us the list of elements in reverse order. This gives stacks some interesting applications we'll analyze later.
How to use stacks in Python
In the previous examples we used lists to represent stacks, however there are more ways to implement stacks that we should analyze:
Using lists
This is the approach we used in the examples. We just create a list and perform insert operations by appending elements to the end of the list.
stack = [3, 2, 5, 6]
print(stack.pop()) # 6
print(stack) # [3, 2, 5]
This approach works well and many people use it, let's check how each operation performs using lists:
- Insert: O(1) Amortized
- Peek: O(1)
- Delete: O(1)
The reason why the complexity of insert is O(1) amortized is because in the implementation of list, a new list is created if the list grows as big as the size of its internal array. However developers came up with a smart way to reduce the amount of times this has to be done, by doubling or greatly increasing the size of the new internal array. This means that an O(n) operation will be performed very few times turning the complexity of the insert operation by O(1) amortized.
If you want to understand why amortized O(1) works at a deeper level, read how dynamic arrays handle memory allocation, it's a topic worth its own article.
Using deques
This is my preferred approach as deques use linked lists underneath, which is the optimal way to implement stacks for time performance.
from collections import deque
stack = deque()
# Push items
stack.append(1)
stack.append(2)
stack.append(3)
# Pop item (last in, first out)
top = stack.pop() # returns 3
print(top) # 3
# Peek at top without removing
top = stack[-1] # returns 2
print(top) # 2
print(stack) # deque([1, 2])
Another example
from collections import deque
my_list = [3, 4, 5, 2]
stack = deque(my_list)
while stack:
print(stack.pop()) # Prints 2, 5, 4, 3
This is the performance of stack operations using deque in Python:
- Insert: O(1)
- Peek: O(1)
- Delete: O(1)
The difference of using a list and a deque is going to be insignificant in most cases, however there might be some special applications and corner cases where using a deque might be needed. I can imagine there are LeetCode problems where using a deque (linked list) can make the difference between passing and not passing.
Creating your own Stack class
Most of the times it's unnecessary to create your own class to utilize stacks. You can do it if you want to solve some shortcomings that lists and deques have. For example deques and lists allow you to peek elements in the middle of the stack, add or delete elements in any position, in other words you can perform operations that a stack doesn't support. You can solve this by creating your own Stack class where you have more control over the operations that are allowed.
Example:
from collections import deque
class Stack:
def __init__(self):
self._stack = deque()
def push(self, item):
self._stack.append(item)
def pop(self):
if not self._stack:
raise IndexError("Pop from empty stack")
return self._stack.pop()
def peek(self):
if not self._stack:
raise IndexError("Peek from empty stack")
return self._stack[-1]
def __repr__(self):
return f"Stack({list(self._stack)})"
# Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack) # Stack([1, 2, 3])
print(stack.peek()) # 3
print(stack.pop()) # 3
print(stack.pop()) # 2
print(stack.pop()) # 1
print(stack.pop()) # IndexError: Pop from empty stack
As this class uses a deque to represent the stack, its performance will be the same as the performance of a deque.
Applications
Stacks show up in real codebases and DSA problems. Here are some applications:
- Parentheses matching
- Tree traversals
- DFS
- Memento undo/redo
Parentheses matching
This is one of the simplest problems that can be solved using stacks. In summary what the algorithm does is to keep track of opening parentheses in a stack and as soon as you find a closing parenthesis you compare it to the one on top of the stack. Any inconsistencies mean that the parentheses are not valid.
Sample code solution for this problem: https://leetcode.com/problems/valid-parentheses/
from collections import deque
class Solution:
def isValid(self, s: str) -> bool:
closing_to_open = {')': '(', '}': '{', ']': '['}
stack = deque()
for c in s:
if c in closing_to_open:
if not stack or stack.pop() != closing_to_open[c]:
return False
else:
stack.append(c)
return len(stack) == 0
This same idea can also be used to match HTML opening and closing tags, JSON objects, XML tags etc. Matching parentheses is the simplest version of this problem but there are some variations to it.
Tree traversals
Traversing trees and graphs can be done in multiple ways, you can do it recursively or iteratively. Iterative traversals are usually more efficient but you'll need data structures like stacks or queues to traverse them. Traversing a tree or any kind of graph using stacks will result in a DFS type of traversal.
We can use stacks to perform some of the main binary tree traversals:
- Pre-order
- In-order
- Post-order
The following code shows how to perform an inorder traversal of a binary tree using stacks:
from collections import deque
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
inorder = []
stack = deque()
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
inorder.append(node.val)
node = node.right
return inorder
This is a solution to the following problem: https://leetcode.com/problems/binary-tree-inorder-traversal/
DFS on graphs
We just saw how to perform a DFS on a tree, the same traversal can be performed on graphs. Have a look at the following problem: https://leetcode.com/problems/number-of-islands/
We are given a graph and we need to find how many connected components the graph has. This problem can be solved by performing a DFS or BFS search:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
for i in range(len(grid)):
grid[i] = ["0"] + grid[i] + ["0"]
waterRow = ["0"] * len(grid[0])
grid = [waterRow] + grid
grid.append(waterRow)
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
visited = set()
islands = 0
for i in range(1, len(grid) - 1):
for j in range(1, len(grid[i]) - 1):
if grid[i][j] == "1" and (i, j) not in visited:
islands += 1
stack = collections.deque()
stack.append((i, j))
visited.add((i, j))
while stack:
pos = stack.pop()
for m in moves:
newPos = (pos[0] + m[0], pos[1] + m[1])
if grid[newPos[0]][newPos[1]] == "1" and newPos not in visited:
visited.add(newPos)
stack.append(newPos)
return islands
Note: There's something funny about this solution and it is that I initially solved it using BFS with queue instead of using DFS. To turn it into DFS, all I had to do was to use a stack instead of a queue and the solution will still work. There are many problems that can be solved with both BFS or DFS without making any difference. I recommend you check articles about BFS and queues if you want to learn more about it.
Undo and redo functions
This is one of the most interesting applications of stacks. You can implement undo and redo functions using the Memento design pattern but I'll show a simplified example of it using stacks. A classic Memento implementation will use stacks too.
The following example shows the code of a TextEditor class that implements redo and undo functions using stacks:
from collections import deque
class TextEditor:
def __init__(self):
self.content = ""
self._history = deque()
self._future = deque()
def type(self, text):
self._history.append(self.content)
self._future.clear()
self.content += text
def undo(self):
if not self._history: return
self._future.append(self.content)
self.content = self._history.pop()
def redo(self):
if not self._future: return
self._history.append(self.content)
self.content = self._future.pop()
editor = TextEditor()
editor.type("Hello")
print(editor.content) # Hello
editor.type(" world")
print(editor.content) # Hello world
editor.undo()
print(editor.content) # Hello
editor.redo()
print(editor.content) # Hello world
Conclusion
The stack is a fundamental linear data structure that has many useful applications. Knowing the situations where stacks are needed to solve problems is going to bring a lot of value for you as a developer, especially in DSA problems. If you want to continue studying data structures and algorithms I'd recommend you study its FIFO counterpart the queue, trees and graph algorithms like DFS and BFS.
If you have any questions or want to discuss anything please leave a comment in the comment section.
Top comments (0)