Chapter 16: DSA Stacks
DSA Stacks – Let’s understand this topic properly, like I’m sitting next to you with a notebook, explaining slowly, clearly, with real-life examples, memory visuals, code, common mistakes, interview patterns, and honest answers about when and why stacks are actually used.
What is a Stack?
A Stack is a linear data structure that follows LIFO (Last In, First Out) principle.
Very simple meaning:
The last element you put in is the first element you can take out.
It behaves exactly like a stack of plates in your kitchen:
- You can only add a new plate on top
- You can only remove a plate from the top
- You cannot take a plate from the middle or bottom without removing everything above it first
This very strict access rule is what makes stack different from arrays and linked lists.
Real-life examples of Stack (very important to build intuition)
| Situation | How it works like a stack | Operation mapping |
|---|---|---|
| Browser Back button | Last page you visited is the first one you go back to | Push = visit new page, Pop = press back |
| Undo in Word / Paint / any editor | Last action you did is undone first | Push = every action, Pop = Ctrl+Z |
| Call stack in programming | Last function called finishes first | Push = function call, Pop = return |
| Pile of dinner plates in canteen | You take the topmost plate first | Pop = take plate, Push = wash & put back |
| History in photo editing apps | Last edit is reverted first | Push = every edit, Pop = undo |
| Expression evaluation (postfix) | Numbers wait until operator comes | Push = numbers, Pop = operands for calculation |
| Recursion | Deepest recursive call finishes first | Push = recursive call, Pop = return |
Core Operations of Stack (must know perfectly)
| Operation | Description | Time Complexity | Common Name |
|---|---|---|---|
| Push | Add element to the top | O(1) | push() |
| Pop | Remove & return element from top | O(1) | pop() |
| Peek / Top | Look at the top element (without removing) | O(1) | peek() / top() |
| isEmpty | Check if stack has no elements | O(1) | isEmpty() |
| Size | Number of elements currently in stack | O(1) | size() / length |
These five operations are the heart of stack — almost every stack problem uses only these.
Stack Implementation – Two most common ways
1. Using Array (most common & most recommended in interviews)
Python
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
class Stack: def __init__(self): self.items = [] # Python list as stack def push(self, value): self.items.append(value) # add to end = top def pop(self): if self.is_empty(): return "Stack is empty!" return self.items.pop() # remove from end = top def peek(self): if self.is_empty(): return "Stack is empty!" return self.items[-1] # look at last element def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items) def display(self): if self.is_empty(): print("Stack is empty") else: print("Stack (bottom → top):", self.items) # Example usage s = Stack() s.push(10) s.push(20) s.push(30) s.push(40) s.display() # Stack (bottom → top): [10, 20, 30, 40] print("Popped:", s.pop()) # 40 print("Top now:", s.peek()) # 30 s.display() # [10, 20, 30] |
Important notes about array implementation:
- In Python, list is dynamic array → push & pop at end are amortized O(1)
- In C++/Java → you may need to handle resizing manually
- Very cache-friendly (sequential memory access)
- Most companies accept this version in interviews
2. Using Linked List (sometimes asked to show pointer understanding)
Python
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Node: def __init__(self, data): self.data = data self.next = None class LinkedListStack: def __init__(self): self.top = None def push(self, data): new_node = Node(data) new_node.next = self.top # new node points to old top self.top = new_node # new node becomes top def pop(self): if self.top is None: return "Stack Underflow" data = self.top.data self.top = self.top.next return data def peek(self): if self.top: return self.top.data return "Stack is empty" def is_empty(self): return self.top is None def display(self): if self.is_empty(): print("Stack is empty") return current = self.top print("Stack (top → bottom): ", end="") while current: print(current.data, end=" → ") current = current.next print("null") |
Memory view of linked list stack:
text
|
0 1 2 3 4 5 6 |
top → [40 | →] → [30 | →] → [20 | →] → [10 | →] → null |
Very Common Interview Questions on Stack
| Level | Question examples (very frequently asked) |
|---|---|
| Easy | Implement stack using array / linked list |
| Easy | Check if stack is empty / get size |
| Medium | Valid Parentheses (balanced brackets) |
| Medium | Next Greater Element / Next Smaller Element |
| Medium | Reverse a string using stack |
| Medium | Min Stack (get minimum in O(1) time) |
| Medium | Evaluate Reverse Polish Notation (postfix expression) |
| Hard | Largest Rectangle in Histogram |
| Hard | Trapping Rain Water |
| Hard | Stock Span Problem |
| Hard | Implement queue using two stacks |
Stack vs Other Data Structures – Quick Comparison
| Feature | Stack | Queue | Array / List |
|---|---|---|---|
| Order rule | LIFO | FIFO | No rule |
| Access point | Only top | front & rear | Any index |
| Real-life analogy | Pile of plates | Ticket queue | Row of boxes |
| Most famous algorithm | DFS, recursion, undo | BFS, level order | Binary search, sorting |
| Typical implementation | Array / Linked List | Circular array / deque | Fixed / dynamic array |
Summary – Stack in one line each
- Follows LIFO (Last In First Out) rule
- Main operations: push, pop, peek, isEmpty
- Very fast — all core operations O(1)
- Used everywhere: undo/redo, back button, function calls, expression evaluation, DFS
- Most common implementation: array-based (simple & fast)
- One of the first data structures you should master deeply
- Basis for many medium & hard interview problems
Now that you have a solid understanding of stacks…
Which topic would you like to explore next in the same detailed style?
Very natural next steps:
- Valid Parentheses (classic stack problem with dry run)
- Next Greater Element (very common pattern)
- Min Stack (design question with O(1) min)
- Implement Queue using Stack (famous interview twist)
- Stack using two queues (reverse question)
- Applications of stack in detail (expression evaluation, DFS, etc.)
Just tell me which one you want — I’ll teach it step-by-step like we’re doing a live session! 😄
