SyntaxPilot
Courses/Python/Lesson 34
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python · Lesson 34 of 40

DSA 1: arrays, stacks, queues

queued

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:

  1. An opener ( [ { is pushed: it waits.
  2. A closer must match the opener on top. If the stack is empty or the top doesn't match: not balanced.
  3. 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:

  1. join(name) gives the customer the next token number and adds them to a deque.
  2. serve() pops the front customer and prints them.
  3. Every join and serve is pushed onto an actions stack.
  4. undo() pops the last action and reverses it (an undone serve goes back to the front with appendleft).
  5. A screen shows the last 3 served, with deque(maxlen=3).
  6. 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

  1. 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.
  2. How would you implement a stack in Python? With a list: append to push, pop() to pop, [-1] to peek. All O(1).
  3. Why shouldn't you use a list as a queue? pop(0) and insert(0, x) are O(n) because every item shifts. Use collections.deque, which is O(1) at both ends.
  4. 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.
  5. 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).
  6. 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).
  7. 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: append to 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.deque with append and popleft, 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 dict and set O(1).