These are the notes for Python episode 34, the first episode of the master section: data structures and algorithms (DSA). Raju's chai-stall billing app needs an Undo button. Remembering "the last item" in one variable fails on the second undo, so you invent the stack. Then you open up a Python list to see the dynamic array inside it, and why some list operations are instant while others are slow. Finally, a fair order line needs first come, first served, so you invent the queue with collections.deque. Every program below ran for real (Python 3.13.18). Timings depend on your computer; compare the patterns, not the exact numbers.
A data structure is a way of arranging data in memory so that the jobs you need (add, remove, find, take the newest, take the oldest) are fast. An algorithm is a step-by-step method that solves a problem using that data.
The problem: an Undo button
Raju taps chai, samosa, toast into a customer's cart. A wrong tap needs Undo, and pressing Undo again should remove the item before that, newest first.
The obvious attempt: remember the last item in one variable.
cart = []
last = None # remember the last thing added
def add(item):
global last
cart.append(item)
last = item
def undo():
global last
if last is None:
print("nothing to undo!")
return
cart.remove(last)
last = None
add("chai"); add("samosa"); add("toast")
undo()
print(cart)
undo()
print(cart)
Output:
['chai', 'samosa']
nothing to undo!
['chai', 'samosa']
The second undo fails. One variable remembers one thing. After the first undo, the program has forgotten what came before toast. To undo every step we need the whole history, and we must always take back the newest step first.
The stack (LIFO)
Real-life picture: the pile of steel plates at a wedding buffet.
| Buffet plates | Stack operation | Python list |
|---|---|---|
| Put a washed plate on top | push | stack.append(x) |
| A guest takes the top plate | pop | stack.pop() |
| Glance at the top plate without taking it | peek | stack[-1] |
| Is the pile empty? | is_empty | not stack |
The rule "last in, first out" is called LIFO. Anything that follows it is a stack. Undo is exactly LIFO: the last action in is the first one undone.
Undo with a stack
cart = []
history = [] # a stack of actions
def add(item):
cart.append(item)
history.append(item) # push: put on top
def undo():
item = history.pop() # pop: take the top
cart.remove(item)
print("undid", item)
add("chai"); add("samosa"); add("toast")
undo(); undo()
print(cart)
undo(); undo()
Output:
undid toast
undid samosa
['chai']
undid chai
Traceback (most recent call last):
File "main.py", line 16, in <module>
undo(); undo()
~~~~^^
File "main.py", line 9, in undo
item = history.pop() # pop: take the top
IndexError: pop from empty list
The undos work newest first. The last one crashes: IndexError: pop from empty list. You can't take a plate from an empty pile, so check before popping: if history: ....
A safe Stack class
class Stack:
def __init__(self):
self.items = []
def push(self, x):
self.items.append(x)
def pop(self):
if self.is_empty():
return None # no crash on empty
return self.items.pop()
def peek(self):
return self.items[-1] if self.items else None
def is_empty(self):
return not self.items
def __len__(self):
return len(self.items)
history = Stack()
for action in ["add chai", "add samosa", "remove chai"]:
history.push(action)
print("top:", history.peek(), "| size:", len(history))
print(history.pop(), "|", history.pop(), "|", history.pop())
print(history.pop(), history.is_empty())
Output:
top: remove chai | size: 3
remove chai | add samosa | add chai
None True
push, pop, peek, is_empty and len are all O(1) (constant time, episode 33): they only touch the end of the list.
Where stacks are used
- Undo / redo in editors and apps.
- The browser's Back button (pages you visited, newest on top).
- Checking brackets in code (below).
- The call stack: every function call waits on a stack until it returns (episode 15, recursion). Too many waiting calls gives
RecursionError. - Depth-first search (episode 36).
Checking brackets with a stack
Code editors and Python itself check that every (, [ and { is closed, in the right order. Read the text left to right:
- An opener
([{is pushed: it waits. - A closer must match the opener on top. If the stack is empty or the top doesn't match: not balanced.
- At the end the stack must be empty (nothing left open).
def is_balanced(text):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in text:
if ch in "([{":
stack.append(ch) # an opener waits
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False # wrong or missing opener
return not stack # nothing left open
for s in ["(a[1] + b) * 2", "([)]", "((x)", "{[()]}"]:
print(f"{s:<16} {is_balanced(s)}")
Output:
(a[1] + b) * 2 True
([)] False
((x) False
{[()]} True
([)] fails because ) arrives while [ is on top. ((x) fails because one ( is left over. One pass over the text: O(n).
Arrays: what's inside a Python list
Our stack is fast because append and pop() at the end are instant. But in episode 33, pop(0) from the front was hundreds of times slower. The reason is the array inside every list.
Real-life picture: hostel rooms in one corridor.
| Hostel corridor | Array idea |
|---|---|
| Rooms side by side, all the same size, numbered 0, 1, 2... | An array: equal-sized slots next to each other in one block of memory |
| Room 7 is 7 doors from the start: walk straight there | Indexing is O(1): address = start + i × slot size |
| A new student must go into room 0: everyone moves one room | insert(0, x) / pop(0) shift every item: O(n) |
| Corridor full? The warden books a bigger floor with spare rooms | A dynamic array grows by copying into a bigger block, with spare room |
A Python list is a dynamic array of references: each slot holds a reference (an arrow) to an object, which is why one list can hold mixed types.
Watching a list grow
import sys
nums = []
last = sys.getsizeof(nums)
print(f"len 0: {last} bytes")
for i in range(20):
nums.append(i)
size = sys.getsizeof(nums)
if size != last:
print(f"len {len(nums):>2}: {size} bytes <- grew")
last = size
Output (Python 3.13, 64-bit):
len 0: 56 bytes
len 1: 88 bytes <- grew
len 5: 120 bytes <- grew
len 9: 184 bytes <- grew
len 17: 248 bytes <- grew
sys.getsizeof(obj) returns the size in bytes of the list object itself (its slots), not of the items. The list grows in jumps: each time it runs out of slots it grabs room for several more, so most appends just drop into a free slot. An occasional append copies everything, but averaged over many appends the cost is still O(1). That is called amortized O(1). The exact numbers depend on your Python version; the jumps are the point.
Front vs end
import timeit
def at_end():
nums = []
for i in range(50_000):
nums.append(i) # add at the end
def at_front():
nums = []
for i in range(50_000):
nums.insert(0, i) # add at the front
print("append: ", round(timeit.timeit(at_end, number=1), 4), "s")
print("insert(0):", round(timeit.timeit(at_front, number=1), 4), "s")
Output (one run):
append: 0.0045 s
insert(0): 0.2292 s
About 50× slower here, and the gap grows with the size: each insert at the front shifts every item already there.
The array module: a typed array
from array import array
marks = array("i", [72, 85, 91]) # "i" = only ints
marks.append(64)
print(marks, marks[1])
marks.append("absent")
Output:
array('i', [72, 85, 91, 64]) 85
Traceback (most recent call last):
File "main.py", line 6, in <module>
marks.append("absent")
~~~~~~~~~~~~^^^^^^^^^^
TypeError: 'str' object cannot be interpreted as an integer
array("i", ...) stores the numbers themselves packed tightly (not references), which saves memory for millions of numbers, but it accepts one type only. The first argument is a type code: "i" int, "d" float (double), "b" small int. For everyday code, use a list. For heavy number crunching, the NumPy library (data course) builds on the same idea.
Big-O of list operations
| Operation | Big-O | Why |
|---|---|---|
lst[i], lst[i] = x, len(lst) |
O(1) | address arithmetic |
lst.append(x), lst.pop() |
O(1) amortized | the end, spare room |
lst.insert(0, x), lst.pop(0) |
O(n) | every item shifts |
lst.insert(i, x), lst.pop(i), lst.remove(x) |
O(n) | items after i shift |
x in lst, lst.index(x) |
O(n) | checks one by one |
lst.sort() |
O(n log n) | episode 37 |
A stack is a list that only uses its end, which is why it's so fast.
The queue (FIFO)
Evening rush: Ravi orders first, then Asha, then Neha. Can our stack serve them?
orders = []
orders.append("Ravi: chai") # came first
orders.append("Asha: coffee")
orders.append("Neha: samosa") # came last
print("serving", orders.pop())
print("serving", orders.pop())
Output:
serving Neha: samosa
serving Asha: coffee
Neha, who came last, is served first. A stack is LIFO, and that's unfair here. orders.pop(0) would serve Ravi first, but it's O(n) per call. We need: add at the back, remove from the front, both fast.
Real-life picture: the railway ticket line.
| Ticket line | Queue operation | collections.deque |
|---|---|---|
| A new person joins at the back | enqueue | q.append(x) |
| The front person gets a ticket and leaves | dequeue | q.popleft() |
| Look at who's next | front | q[0] |
| First in line, first served | FIFO |
FIFO = first in, first out. Anything that follows it is a queue. In Python, use deque (say "deck"), a double-ended queue: fast, O(1), at both ends, because it is built from linked blocks so nothing shifts.
from collections import deque
orders = deque()
orders.append("Ravi: chai") # join at the back
orders.append("Asha: coffee")
orders.append("Neha: samosa")
print("waiting:", list(orders))
while orders:
print("serving", orders.popleft()) # serve the front
print("waiting:", list(orders))
orders.popleft()
Output:
waiting: ['Ravi: chai', 'Asha: coffee', 'Neha: samosa']
serving Ravi: chai
serving Asha: coffee
serving Neha: samosa
waiting: []
Traceback (most recent call last):
File "main.py", line 12, in <module>
orders.popleft()
~~~~~~~~~~~~~~^^
IndexError: pop from an empty deque
while orders: stops when the deque is empty, because an empty deque counts as False. The extra popleft() crashes with IndexError: pop from an empty deque.
A deque also has pop(), appendleft(), extend(), rotate() and indexing at the ends (q[0], q[-1]), so it can work as a stack, a queue, or both. Indexing the middle of a deque is O(n).
Recent items: deque(maxlen=n)
from collections import deque
recent = deque(maxlen=3) # keeps only the last 3
for item in ["chai", "samosa", "toast", "coffee", "vada pav"]:
recent.append(item)
print(list(recent))
recent.appendleft("lassi") # add at the front too
print(recent, recent[0], recent[-1])
Output:
['chai']
['chai', 'samosa']
['chai', 'samosa', 'toast']
['samosa', 'toast', 'coffee']
['toast', 'coffee', 'vada pav']
deque(['lassi', 'toast', 'coffee'], maxlen=3) lassi coffee
When a full deque gets a new item, the item at the other end falls off. Great for "last 3 orders", the last N log lines, or a moving average.
Other queues you'll meet
queue.Queue: a thread-safe queue for threads (episode 31).asyncio.Queue: for async code (episode 32).heapq: a priority queue, where the smallest item comes out first, not the oldest (used in Dijkstra's algorithm).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
history.pop() on an empty list |
IndexError: pop from empty list |
nothing on the stack | if history: history.pop() |
orders.popleft() on an empty deque |
IndexError: pop from an empty deque |
nobody in the line | while orders: ... |
orders.pop() for a waiting line |
the newest customer is served first | a list's pop() is LIFO |
deque + popleft() |
queue.pop(0) on a big list |
slow, O(n) per pop | every item shifts left | collections.deque |
array("i").append("absent") |
TypeError: 'str' object cannot be interpreted as an integer |
a typed array holds one type | use a list for mixed data |
stack[-1] on an empty list |
IndexError: list index out of range |
no top to peek at | stack[-1] if stack else None |
| one variable for undo | second undo does nothing | one variable remembers one thing | a stack of actions |
Stack or queue?
| Ask | Structure | Python | Examples |
|---|---|---|---|
| Newest first? | stack (LIFO) | list: append + pop |
undo, back button, brackets, function calls, DFS |
| Oldest first? | queue (FIFO) | deque: append + popleft |
orders, printer jobs, tasks, BFS |
| Smallest first? | priority queue | heapq |
hospital triage, shortest paths |
Mini project: Raju's token counter with Undo
Requirements:
join(name)gives the customer the next token number and adds them to a deque.serve()pops the front customer and prints them.- Every join and serve is pushed onto an actions stack.
undo()pops the last action and reverses it (an undone serve goes back to the front withappendleft).- A screen shows the last 3 served, with
deque(maxlen=3). - It never crashes on an empty queue or stack.
Solution
from collections import deque
class TokenCounter:
def __init__(self):
self.next_token = 1
self.waiting = deque() # the queue: FIFO
self.actions = [] # the undo stack: LIFO
self.screen = deque(maxlen=3) # last 3 served
def join(self, name):
token = (self.next_token, name)
self.next_token += 1
self.waiting.append(token)
self.actions.append(("join", token))
print(f"token {token[0]} for {name}")
def serve(self):
if not self.waiting:
print("nobody waiting")
return
token = self.waiting.popleft()
self.screen.append(token)
self.actions.append(("serve", token))
print(f"serving token {token[0]} ({token[1]})")
def undo(self):
if not self.actions:
print("nothing to undo")
return
kind, token = self.actions.pop()
if kind == "join":
self.waiting.remove(token) # it was the newest join
self.next_token -= 1
else:
self.waiting.appendleft(token) # back to the front
self.screen.pop()
print(f"undid {kind} of token {token[0]}")
def show(self):
print("waiting:", [t[0] for t in self.waiting], "| screen:", [t[0] for t in self.screen])
c = TokenCounter()
for name in ["Ravi", "Asha", "Neha", "Imran"]:
c.join(name)
c.serve(); c.serve()
c.show()
c.undo() # un-serve Asha
c.show()
c.undo(); c.undo() # un-serve Ravi, un-join Imran
c.show()
Output:
token 1 for Ravi
token 2 for Asha
token 3 for Neha
token 4 for Imran
serving token 1 (Ravi)
serving token 2 (Asha)
waiting: [3, 4] | screen: [1, 2]
undid serve of token 2
waiting: [2, 3, 4] | screen: [1]
undid serve of token 1
undid join of token 4
waiting: [1, 2, 3] | screen: []
Because the actions are undone newest first, an undone join is always still in the queue, and an undone serve is always the newest item on the screen.
Practice
1. Reverse a string with a stack.
Solution
def reverse(text):
stack = list(text)
out = ""
while stack:
out += stack.pop()
return out
print(reverse("chai"))
Output: iahc. (In real code, text[::-1] does it in one step.)
2. Add Redo to the Undo app. Hint: a second stack. A new action clears the redo stack.
Solution
cart, undo_stack, redo_stack = [], [], []
def add(item):
cart.append(item); undo_stack.append(item); redo_stack.clear()
def undo():
if undo_stack:
item = undo_stack.pop(); cart.remove(item); redo_stack.append(item)
def redo():
if redo_stack:
item = redo_stack.pop(); cart.append(item); undo_stack.append(item)
add("chai"); add("samosa"); add("toast")
undo(); undo(); print(cart)
redo(); print(cart)
add("lassi"); redo(); print(cart)
Output:
['chai']
['chai', 'samosa']
['chai', 'samosa', 'lassi']
The last redo() does nothing: adding lassi cleared the redo stack, just like real editors.
3. Simulate a printer queue with three documents.
Solution
from collections import deque
jobs = deque()
for doc in ["bill.pdf", "menu.pdf", "report.pdf"]:
jobs.append(doc)
print("queued", doc, "| waiting:", len(jobs))
while jobs:
print("printing", jobs.popleft())
Output:
queued bill.pdf | waiting: 1
queued menu.pdf | waiting: 2
queued report.pdf | waiting: 3
printing bill.pdf
printing menu.pdf
printing report.pdf
4. Big-O check. What is the Big-O of lst.insert(0, x) inside a loop that runs n times?
Answer
Each insert is O(n) (every item shifts), so n of them is O(n²). With deque.appendleft it's O(n) in total.
Quick quiz
from collections import deque
d = deque([1, 2, 3])
d.append(4)
d.popleft()
d.pop()
print(list(d))
Options: [1, 2], [2, 3], [3, 4], [2, 3, 4]
Answer
[2, 3]. append(4) → [1, 2, 3, 4]; popleft() removes 1 → [2, 3, 4]; pop() removes 4 from the right → [2, 3].
Interview questions
- What is the difference between a stack and a queue? A stack is LIFO (last in, first out): push and pop at the same end. A queue is FIFO (first in, first out): add at the back, remove from the front.
- How would you implement a stack in Python? With a list:
appendto push,pop()to pop,[-1]to peek. All O(1). - Why shouldn't you use a list as a queue?
pop(0)andinsert(0, x)are O(n) because every item shifts. Usecollections.deque, which is O(1) at both ends. - Why is list indexing O(1)? A list is an array: slots are the same size and next to each other, so the address of slot i is start + i × slot size, one calculation.
- What does amortized O(1) mean for
append? Most appends are O(1); occasionally the list copies itself into a bigger block (O(n)), but because it grows by a proportion, the average cost per append stays O(1). - How do you check balanced brackets? Push openers onto a stack; for each closer, the top must be its matching opener; at the end the stack must be empty. O(n).
- How do you implement a queue using two stacks? Push onto an "in" stack; to dequeue, if the "out" stack is empty, pop everything from "in" onto "out", then pop from "out". Each item moves at most twice, so it's amortized O(1).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Data structure | A way to arrange data so the jobs you need are fast | list, stack, queue, dict |
| Algorithm | A step-by-step method that solves a problem | checking brackets |
| DSA | Data Structures and Algorithms | this section of the course |
| Stack | A collection where the last item added is the first removed | a pile of plates; undo history |
| LIFO | Last In, First Out: the stack rule | undo removes the newest action |
| Push | Add an item to the top of a stack | stack.append(x) |
| Pop | Remove and return the top item | stack.pop() |
| Peek | Read the top item without removing it | stack[-1] |
| Call stack | The stack of function calls waiting to return | recursion, RecursionError |
| Array | Equal-sized slots side by side in one block of memory | hostel rooms in one corridor |
| Index | The position number of a slot, starting at 0 | lst[2] is the third item |
| Dynamic array | An array that grows by copying into a bigger block with spare room | a Python list |
| Amortized O(1) | O(1) on average over many operations, even if a few are slow | list.append |
sys.getsizeof |
Returns an object's size in bytes | sys.getsizeof([]) → 56 |
| Typed array | An array that stores one type of value, packed tightly | array("i", [1, 2]) |
| Type code | The letter that tells array what type it holds |
"i" int, "d" float |
| Queue | A collection where the first item added is the first removed | a ticket line; orders |
| FIFO | First In, First Out: the queue rule | serve the oldest order first |
| Enqueue | Add an item to the back of a queue | q.append(x) |
| Dequeue | Remove the item at the front of a queue | q.popleft() |
| deque | Python's double-ended queue, O(1) at both ends | from collections import deque |
| Double-ended queue | A queue you can add to and remove from at both ends | appendleft, pop |
maxlen |
A deque size limit: the oldest item falls off the other end | deque(maxlen=3) |
| Priority queue | A queue where the smallest (highest-priority) item comes out first | heapq |
IndexError |
Raised when you pop or index something that isn't there | pop from empty list |
Summary
- A data structure arranges data so your jobs are fast. Pick it by asking which job matters most.
- A stack is LIFO:
appendto push,pop()to pop,[-1]to peek, all O(1) on a list. It powers undo, the back button, bracket checking and the call stack. Check for empty before popping. - A Python list is a dynamic array of references: index O(1), append/pop at the end amortized O(1), but insert/pop at the front O(n).
- A queue is FIFO. Use
collections.dequewithappendandpopleft, both O(1).deque(maxlen=n)keeps the last n items. - Next episode: linked lists and hashing, a train of nodes that never shifts, and the trick that makes
dictandsetO(1).