Chapter 15: Stacks & Queues
DSA Stacks & Queues – Let’s learn these two very important linear data structures like I’m sitting next to you, explaining slowly and clearly with lots of real-life examples, memory visuals, code, common operations, interview patterns, and honest comparison.
1. What is a Stack?
A Stack is a linear data structure that follows LIFO (Last In, First Out) principle.
That means:
- The last element added is the first one to be removed
- It’s exactly like a stack of plates in your kitchen
Real-life examples of Stack
| Real-life situation | Stack operation |
|---|---|
| Browser Back button | Last page visited is on top |
| Undo (Ctrl + Z) in any editor | Last action done is undone first |
| Call stack in programming | Last function called returns first |
| Pile of books on a table | You take/remove from the top |
| Restaurant plate stacking | Wash the top plate first |
| Recursion | Deepest call finishes first |
| Expression evaluation (postfix) | Operands wait for operators |
Core Operations of Stack (very important)
| Operation | Name | Time Complexity | What it does |
|---|---|---|---|
| Push | Insert | O(1) | Add element to the top |
| Pop | Remove | O(1) | Remove & return top element |
| Peek / Top | View | O(1) | See top element without removing |
| isEmpty | Check | O(1) | Check if stack is empty |
| Size | Length | O(1) | Number of elements |
Stack Implementation – Two most common ways
1. Using Array (most common 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 |
class Stack: def __init__(self): self.items = [] # using Python list as stack def push(self, item): self.items.append(item) # add to end def pop(self): if not self.is_empty(): return self.items.pop() # remove from end return None def peek(self): if not self.is_empty(): return self.items[-1] return None def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items) def print_stack(self): print("Stack (top at right):", self.items) # Usage s = Stack() s.push(10) s.push(20) s.push(30) s.print_stack() # [10, 20, 30] print("Popped:", s.pop()) # 30 s.print_stack() # [10, 20] print("Top:", s.peek()) # 20 |
Why array is popular for stack:
- Very fast (all operations O(1) amortized)
- Cache-friendly
- Easy to implement
- Most companies accept this implementation
2. Using Linked List (sometimes asked)
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 |
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 self.top = new_node def pop(self): if self.top is None: return None data = self.top.data self.top = self.top.next return data def peek(self): if self.top: return self.top.data return None def is_empty(self): return self.top is None |
Advantage of linked list stack: No size limit (array has to resize sometimes)
Disadvantage: Slightly slower due to pointer chasing
2. What is a Queue?
A Queue is a linear data structure that follows FIFO (First In, First Out) principle.
Like a normal queue/line in real life:
- First person who came is served first
- New person joins at the back (rear)
- Person leaves from the front
Real-life examples of Queue
| Real-life situation | Queue operation |
|---|---|
| People waiting at ticket counter | First person gets ticket first |
| Printer job queue | First document printed first |
| CPU process scheduling (FCFS) | First process gets CPU first |
| Breadth-First Search (BFS) | Level by level exploration |
| Customer support call center | First caller is answered first |
| Buffer in streaming/video playback | Oldest data played first |
Core Operations of Queue
| Operation | Name | Time Complexity (array) | Time Complexity (linked list) |
|---|---|---|---|
| Enqueue | Add | O(1) amortized | O(1) |
| Dequeue | Remove | O(n) (bad) / O(1) with circular | O(1) |
| Front / Peek | View front | O(1) | O(1) |
| isEmpty | Check | O(1) | O(1) |
| Size | Length | O(1) | O(1) |
Queue Implementation – Most common ways
1. Using Array + Circular Queue (best for 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 48 49 50 51 |
class Queue: def __init__(self, capacity): self.capacity = capacity self.queue = [None] * capacity self.front = 0 self.rear = -1 self.size = 0 def enqueue(self, item): if self.size == self.capacity: print("Queue is full") return self.rear = (self.rear + 1) % self.capacity self.queue[self.rear] = item self.size += 1 def dequeue(self): if self.is_empty(): print("Queue is empty") return None item = self.queue[self.front] self.front = (self.front + 1) % self.capacity self.size -= 1 return item def get_front(self): if self.is_empty(): return None return self.queue[self.front] def is_empty(self): return self.size == 0 def print_queue(self): if self.is_empty(): print("Queue empty") return i = self.front print("Queue (front to rear): ", end="") for _ in range(self.size): print(self.queue[i], end=" ") i = (i + 1) % self.capacity print() |
Important: Normal array queue has O(n) dequeue (shift elements) → We use circular queue to make both enqueue & dequeue O(1)
2. Using Python list (simple but not efficient for large use)
Python
|
0 1 2 3 4 5 6 7 8 9 |
q = [] q.append(10) # enqueue q.append(20) print(q.pop(0)) # dequeue → O(n) because shifts all elements |
Not recommended for serious use — use collections.deque instead
3. Best in Python – collections.deque (double-ended queue)
Python
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 |
from collections import deque q = deque() q.append(10) # enqueue rear q.append(20) q.appendleft(5) # enqueue front print(q.popleft()) # dequeue front → O(1) print(q.pop()) # dequeue rear → O(1) |
This is the most efficient queue implementation in Python.
Quick Comparison – Stack vs Queue
| Feature | Stack | Queue |
|---|---|---|
| Principle | LIFO | FIFO |
| Real-life example | Pile of plates | Ticket line |
| Main operations | push, pop, peek | enqueue, dequeue, front |
| Insert position | Top | Rear |
| Remove position | Top | Front |
| Implementation | Array / Linked List | Circular Array / Linked List / deque |
| Most famous algorithm | DFS, recursion, undo | BFS, level order traversal |
| Cache performance | Excellent (array) | Good (circular array) |
Very Common Interview Patterns
Stack patterns
- Valid Parentheses / balanced brackets
- Next Greater Element
- Largest Rectangle in Histogram
- Stock Span Problem
- Min Stack / design stack with O(1) min
- Evaluate Reverse Polish Notation
Queue patterns
- Level Order Traversal (Binary Tree)
- BFS (Graph / Tree)
- Sliding Window Maximum
- Generate Binary Numbers from 1 to n
- Rotten Oranges / Flood Fill
- Implement Stack using Queue (and vice versa)
Would you like to go deeper into any particular topic next?
Popular choices:
- Implement Stack using Queue (classic interview question)
- Implement Queue using Stack
- Next Greater Element (very common stack problem)
- Level order traversal of binary tree (queue)
- Valid Parentheses (stack)
- Circular Queue dry run with memory diagram
Just tell me which one you want — I’ll explain it in the same detailed, human-teacher style! 😄
