Stacks — LIFO Data Structure Guide
In this tutorial, you'll learn about Stacks. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle — the last element added is the first one removed. Think of a stack of plates: you add plates to the top and remove from the top.
What You'll Learn
You will learn stack operations (push, pop, peek), array-based and linked-list-based implementations, and real-world problems like parentheses matching, expression evaluation, and undo systems.
Why It Matters
Stacks power the call stack in every programming language, enable undo/redo in editors, and are essential for depth-first search and Backtracking algorithms.
Real-World Use
The JavaScript engine in Doda Browser uses a call stack to track function execution. When a function calls another function, a new frame is pushed. When a function returns, its frame is popped. Stack overflow occurs when the stack exceeds its limit — typically from infinite Recursion.
Stack Operations
All stack operations are O(1):
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
return self.items.pop()
def peek(self):
if self.is_empty():
raise IndexError("peek from empty stack")
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Peek:", stack.peek())
print("Pop:", stack.pop())
print("Pop:", stack.pop())
print("Size:", stack.size())
print("Is empty:", stack.is_empty())
Expected output:
Peek: 30
Pop: 30
Pop: 20
Size: 1
Is empty: False
class Stack {
constructor() { this.items = []; }
push(item) { this.items.push(item); }
pop() {
if (this.isEmpty()) throw new Error("pop from empty stack");
return this.items.pop();
}
peek() {
if (this.isEmpty()) throw new Error("peek from empty stack");
return this.items[this.items.length - 1];
}
isEmpty() { return this.items.length === 0; }
size() { return this.items.length; }
}
let stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log("Peek:", stack.peek());
console.log("Pop:", stack.pop());
console.log("Pop:", stack.pop());
console.log("Size:", stack.size());
Expected output:
Peek: 30
Pop: 30
Pop: 20
Size: 1
Linked List Stack Implementation
Using a Linked List avoids resizing overhead:
class StackNode:
def __init__(self, data):
self.data = data
self.next = None
class LinkedListStack:
def __init__(self):
self.top = None
self.length = 0
def push(self, data):
node = StackNode(data)
node.next = self.top
self.top = node
self.length += 1
def pop(self):
if self.is_empty():
raise IndexError("pop from empty stack")
data = self.top.data
self.top = self.top.next
self.length -= 1
return data
def peek(self):
if self.is_empty():
raise IndexError("peek from empty stack")
return self.top.data
def is_empty(self):
return self.top is None
def size(self):
return self.length
Stack Flow Diagram
graph TD
subgraph Push 30
A1[Top -> 30] --> B1[20] --> C1[10]
end
subgraph Pop
A2[Top -> 20] --> B2[10]
end
style A1 fill:#4a90d9,stroke:#333,color:#fff
style A2 fill:#e67e22,stroke:#333,color:#fff
Classic Stack Problems
Parentheses Matching
def is_balanced(expr):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for ch in expr:
if ch in '({[':
stack.append(ch)
elif ch in ')}]':
if not stack or stack.pop() != pairs[ch]:
return False
return len(stack) == 0
print(is_balanced("({[]})"))
print(is_balanced("({[})"))
print(is_balanced("((()))"))
Expected output:
True
False
True
function isBalanced(expr) {
let stack = [];
const pairs = {')': '(', '}': '{', ']': '['};
for (let ch of expr) {
if ('({['.includes(ch)) {
stack.push(ch);
} else if (')}]'.includes(ch)) {
if (!stack.length || stack.pop() !== pairs[ch]) return false;
}
}
return stack.length === 0;
}
console.log(isBalanced("({[]})"));
console.log(isBalanced("({[})"));
Expected output:
true
false
Infix to Postfix Conversion
def infix_to_postfix(expr):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
stack = []
result = []
for ch in expr:
if ch.isalnum():
result.append(ch)
elif ch == '(':
stack.append(ch)
elif ch == ')':
while stack and stack[-1] != '(':
result.append(stack.pop())
stack.pop()
else:
while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence.get(ch, 0):
result.append(stack.pop())
stack.append(ch)
while stack:
result.append(stack.pop())
return ''.join(result)
print(infix_to_postfix("A+B*C"))
print(infix_to_postfix("(A+B)*C"))
Expected output:
ABC*+
AB+C*
Common Pitfalls
1. Empty Stack Operations
Always check is_empty() before pop() or peek(). An empty stack raises an error.
2. Stack Overflow in Recursion
Deep Recursion consumes stack frames. Python's default Recursion limit is ~1000. Use sys.setrecursionlimit() or convert to iteration.
3. Confusing Stack and Heap
The stack stores function call frames and local variables; the heap stores dynamically allocated objects. They are completely different memory regions.
4. Forgetting to Update Length
When implementing with a Linked List, always increment/decrement a length counter. Missing this breaks size().
5. Not Handling Memory in Low-Level Languages
In C/C++, stack-allocated variables are automatically freed, but heap-allocated objects within a stack must be manually managed.
Practice Questions
1. Implement a queue using two stacks.
2. Design a stack that supports getMin() in O(1) time.
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):
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def get_min(self):
return self.min_stack[-1]
3. Evaluate a postfix (Reverse Polish Notation) expression.
def eval_rpn(tokens):
stack = []
for t in tokens:
if t in '+-*/':
b, a = stack.pop(), stack.pop()
stack.append(str(int(eval(f"{a}{t}{b}"))))
else:
stack.append(t)
return int(stack[0])
print(eval_rpn(["2", "1", "+", "3", "*"]))
Expected output: 9
4. Challenge: Implement a browser forward/back navigation system using two stacks.
5. Real-world task: Durga Antivirus Pro uses a stack to trace the call chain during malware analysis. Write a function that takes a sequence of function calls and returns the call stack trace when an error is encountered.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro