Lesson 4 of 9

Stacks, Queues & Linked Lists

(last in, first out) and queues (first in, first out) control the order items come back out. You'll also see the linked , which is often used to build them.

A stack is a pile of plates: push onto the top, pop from the top — last in, first out (LIFO). You already depend on one constantly: the call stack. Every call pushes a frame; every return pops it; a that never stops overflows it. Stacks also power undo history, the back button, and matching brackets in every editor and .


# Python list IS a stack: append/pop at the end are O(1).
stack = []
stack.append('a')     # push
stack.append('b')
stack.pop()           # 'b' — last in, first out

# Classic stack problem: are brackets balanced?
def balanced(text):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in text:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

balanced('f(a[0], {x: 1})')   # True
balanced('f(a[0)]')           # False — wrong nesting

A queue is a line at a shop: join at the back, served from the front — first in, first out (FIFO). Print jobs, task schedulers, message queues, and breadth-first search (graphs lesson) all use one. Don't use a Python as a queue — pop(0) shifts everything, O(n). Use collections.deque, which gives O(1) at both ends.


from collections import deque

queue = deque()
queue.append('job1')      # enqueue at back
queue.append('job2')
queue.popleft()           # 'job1' — first in, first out, O(1)

How does deque get O(1) at both ends? Linked lists. A linked list stores each element in its own node with a to the next node — no contiguous block. Insert or remove anywhere you hold a pointer: O(1), just rewire two links, no shifting. The cost is the opposite of the array's strength: no jumping to index 500 — you must walk there, O(n). Arrays trade cheap access for expensive insertion; linked lists trade the opposite.


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Build:  1 -> 2 -> 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# Insert 99 after head: O(1), just rewire — no shifting
new = Node(99)
new.next = head.next
head.next = new           # 1 -> 99 -> 2 -> 3

# Walk the list (this part is O(n)):
node = head
while node:
    print(node.value)
    node = node.next

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.