An introduction to the Last-In-First-Out (LIFO) stack data structure and its common algorithmic patterns.
A stack typically supports the following operations, all of which run in $O(1)$ time:
| Operation | Description | Time Complexity |
|---|---|---|
push(x) | Adds element x to the top of the stack. | $O(1)$ |
pop() | Removes and returns the top element. | $O(1)$ |
peek() | Returns the top element without removing it. | $O(1)$ |
isEmpty() | Checks if the stack is empty. | $O(1)$ |
In Python, a standard list is commonly used as a stack:
stack = []
stack.append(1) # push
stack.append(2)
top = stack[-1] # peek
val = stack.pop() # pop
The most common use case for a stack is when you need to “remember” an opening element until its corresponding closing element is found. This is essential for parsing nested structures.
(, [, {, we push them onto the stack.class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
Sometimes we need a stack to support standard operations plus a special utility, like finding the minimum element in the entire stack at any moment in $O(1)$ time.
min_stack) that stores the minimum value at each “level” of the main stack.class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
A Monotonic Stack is a specialized stack where elements are always sorted (either increasing or decreasing). It is extremely powerful for finding the “next greater element” or “next smaller element” in an array in $O(N)$ time, which often replaces $O(N^2)$ brute force solutions.
We will cover this pattern in depth in a dedicated chapter.
| Situation | Data Structure |
|---|---|
| Need to reverse something | Stack |
| Need to match nested pairs | Stack |
| Need to remember the most recent state | Stack |
| Need to find “Next Greater Element” | Monotonic Stack |
U
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
# Create a copy of prices array to store discounted prices
result = prices.copy()
stack = deque()
for i in range(len(prices)):
# Process items that can be discounted by current price
while stack and prices[stack[-1]] >= prices[i]:
# Apply discount to previous item using current price
result[stack.pop()] -= prices[i]
# Add current index to stack
stack.append(i)
return result
Note: If you are unfamiliar with the workings of monotonic stacks, try out these problems to practice:
| [Python Stacks - Python Tutorial for Absolute Beginners | Mosh](https://youtu.be/NKmasqr_Xkw?si=mXpU5YSSdQjSynaw) |