Stack Implementation and Applications
Implement a stack with push/pop/peek, then solve valid-parentheses, min-stack, and evaluate reverse-polish notation.
Stack Implementation and Applications is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Stack Data Structure
A stack is a last-in, first-out (LIFO) data structure. The last element pushed is the first element popped. Think of a stack of plates: you can only add or remove from the top. Core operations are push (add to top), pop (remove from top), and peek (read top without removing). All three are O(1) on a well-implemented stack.
In Python, a list serves as a perfect stack: append is push, pop() is pop, and [-1] is peek.
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack) # [10, 20, 30]
# Peek
print('Top:', stack[-1]) # 30
# Pop
print('Popped:', stack.pop()) # 30
print('After pop:', stack) # [10, 20]Stack Class with Push, Pop, Peek, isEmpty
Wrapping the list in a class provides a cleaner interface and prevents accidental use of non-stack operations like insert or indexing at positions other than the top. This is the implementation interviewers expect when asked to 'implement a stack from scratch'.
class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty stack')
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek()) # 3
print(s.pop()) # 3
print(len(s)) # 2Valid Parentheses (LeetCode 20)
LeetCode 20 'Valid Parentheses': determine if a string of brackets is balanced. For every opening bracket, push it. For every closing bracket, check that the stack's top is the matching opener; if not, or if the stack is empty, return False. If the stack is empty at the end, the string is valid. This is the canonical first application of a stack in coding interviews.
def isValid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != matching[ch]:
return False
stack.pop()
return len(stack) == 0
print(isValid('()[]{}')) # True
print(isValid('([)]')) # False
print(isValid('{[]}')) # True
print(isValid(']')) # FalseMin Stack (LeetCode 155)
LeetCode 155 'Min Stack': design a stack that supports push, pop, peek, and getMin all in O(1). The trick: maintain a second stack that tracks the minimum at every point. When pushing, also push to the min stack if the new value is <= the current minimum (or if the min stack is empty). When popping, also pop from the min stack if the popped value equals the current minimum.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top()) # 0
print(ms.getMin()) # -2Evaluate Reverse Polish Notation
LeetCode 150 'Evaluate Reverse Polish Notation' (postfix): operands are pushed; on encountering an operator, pop two operands, apply the operator, and push the result. The order matters for subtraction and division: the first popped is the right operand, the second is the left.
def evalRPN(tokens):
stack = []
ops = set(['+', '-', '*', '/'])
for tok in tokens:
if tok not in ops:
stack.append(int(tok))
else:
b = stack.pop() # right operand
a = stack.pop() # left operand
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else: # division truncated toward zero
stack.append(int(a / b))
return stack[0]
print(evalRPN(['2','1','+','3','*'])) # 9
print(evalRPN(['4','13','5','/','+'])) # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+'])) # 22Decode String (LeetCode 394)
LeetCode 394 'Decode String': given an encoded string like 3[a2[c]], expand it to accaccacc. Use two stacks: one for repeat counts, one for accumulated strings. On encountering a digit, build the full number. On [, push the current string and count. On ], pop and repeat the current segment. On a letter, append to the current string.
def decodeString(s):
count_stack = []
str_stack = []
current_str = ''
current_num = 0
for ch in s:
if ch.isdigit():
current_num = current_num * 10 + int(ch)
elif ch == '[':
count_stack.append(current_num)
str_stack.append(current_str)
current_str = ''
current_num = 0
elif ch == ']':
repeats = count_stack.pop()
current_str = str_stack.pop() + current_str * repeats
else:
current_str += ch
return current_str
print(decodeString('3[a]2[bc]')) # 'aaabcbc'
print(decodeString('3[a2[c]]')) # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'Daily Temperatures (Monotonic Stack Preview)
LeetCode 739 'Daily Temperatures': for each day, find how many days until a warmer temperature. A brute force is O(n²). With a stack: iterate through temperatures; for each day, pop all stack entries (day indices) whose temperature is less than today's. The answer for those popped days is (today - popped_day). Push the current day. Remaining stack entries never found a warmer day — their answer is 0.
def dailyTemperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]Stack for DFS Traversal
The call stack in recursive DFS can be replaced with an explicit stack, making the algorithm iterative. Push the root; while the stack is non-empty, pop a node, process it, and push its children (right before left for left-to-right processing). This iterative DFS is identical in behavior to recursive DFS but avoids Python's recursion limit for deep trees.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is processed first
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Time and Space Complexity
All stack operations (push, pop, peek, isEmpty) are O(1) amortised. Building a stack of n elements is O(n). Space is O(n) in the worst case when all elements are stored. For problems that use a monotonic stack, each element is pushed and popped at most once, giving an overall O(n) time across all iterations — not O(n²) as a naive outer-loop reading might suggest.
# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total
def count_ops(n):
pushes = pops = 0
stack = []
for i in range(n):
while stack and stack[-1] < i: # simulated decreasing condition
stack.pop()
pops += 1
stack.append(i)
pushes += 1
return pushes, pops
p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}') # <= 2000Largest Rectangle in Histogram (Preview)
LeetCode 84 'Largest Rectangle in Histogram' is the hardest classic stack problem. For each bar, the rectangle it can anchor extends left until a shorter bar is found and right until a shorter bar is found. A monotonic stack tracks indices of bars in increasing height order. When a shorter bar is seen, pop and compute the rectangle with the popped bar's height. The stack gives left and right boundaries in O(1) per pop.
def largestRectangleArea(heights):
stack = [] # indices, increasing heights
result = 0
heights = heights + [0] # sentinel forces all pops
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2,1,5,6,2,3])) # 10
print(largestRectangleArea([2,4])) # 4Interview Strategy for Stack Problems
Stack problems often disguise themselves as 'process from inside out' or 'find the next greater/smaller element'. Signals that a stack might help: you need the most recently seen element, you are matching pairs (brackets, tags), or you want O(n) on a problem that naively needs O(n²) nested loops. Monotonic stacks in particular turn 'for every element find the closest larger/smaller' from O(n²) to O(n).
In an interview, state your stack invariant clearly: 'I will maintain a stack of indices in decreasing height order.'
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Python lists implement O(1) push/pop/peek making them ideal stacks, valid parentheses and min-stack are the two canonical stack interview problems, and monotonic stacks solve next-greater-element problems in O(n) by pushing and popping each element at most once. Next up we build queues with Python's deque and solve sliding-window maximum.
Frequently asked questions
Is the “Stack Implementation and Applications” lesson free?
Yes — the full text of “Stack Implementation and Applications” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Stack Implementation and Applications”?
Implement a stack with push/pop/peek, then solve valid-parentheses, min-stack, and evaluate reverse-polish notation. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Stack Implementation and Applications” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Stack Implementation and Applications
- Queue Implementation and Deque
- Monotonic Stack Pattern
- Stack and Queue Mutual Simulation