DSData Structures & Algorithms · Lesson 4 of 9

Stacks, Queues & Linked Lists

Three structures about controlling the ORDER things come out: stacks (last in, first out), queues (first in, first out), and the linked list that often implements 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 function call pushes a frame; every return pops it; a recursion that never stops overflows it. Stacks also power undo history, the back button, and matching brackets in every editor and compiler.

Python

# 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 list as a queue — pop(0) shifts everything, O(n). Use collections.deque, which gives O(1) at both ends.

Python

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 pointer to the next node — no contiguous block. Insert or remove anywhere you hold a pointer: O(1), just rewire two links, no shifting. The price is the array's superpower reversed: no jumping to index 500 — you must walk there, O(n). Arrays trade cheap access for expensive insertion; linked lists trade the opposite.

Python

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
◆ Note
In practice you'll rarely hand-roll a linked list — dynamic arrays win most real workloads because contiguous memory is cache-friendly (see the Computer Architecture track). But the node-and-pointer idea is the building block for trees and graphs, which you'll use constantly.