🌙
☀️ Dark
The Engineer's Bible | Volume 1: Foundations | Reading Time: ~22 min

Chapter 22: Chains, Stacks & Lines

Learning Objectives

Prerequisites

Arrays (Ch. 6), Pointers/References (Ch. 8), OOP (Ch. 9).

Why Does This Exist?

Arrays have O(N) insert/delete because they require contiguous memory. Linked lists solve this by distributing nodes anywhere in memory, linked by pointers. Stacks and Queues provide strict access patterns (LIFO/FIFO) preventing invalid state modifications.

History

McCarthy's Lisp popularized linked lists. Stacks have roots in early computers like the ENIAC for evaluating expressions and managing subroutine calls.

Mental Model

Linked List: A chain of train cars, where each car connects to the next. Stack: A stack of plates; you add and remove only from the top. Queue: A line at a bank; first in, first out.

Internal Working

Nodes store a value and a next pointer (and sometimes a prev pointer). Memory isn't contiguous. For stacks/queues, they can be backed by arrays or linked lists.

Syntax

python
1class Node:
2    def __init__(self, val):
3        self.val = val
4        self.next = None
5
6class Stack:
7    def __init__(self):
8        self.items = []
9    def push(self, item):
10        self.items.append(item)
11    def pop(self):
12        return self.items.pop()

Visual Explanation

Linked List: [Head] -> [Node|Next] -> [Node|Next] -> None Stack (LIFO): | 3 | <- Top (Pop removes 3) | 2 | | 1 | +-------+ Queue (FIFO): Front [ 1 | 2 | 3 ] Back <- Enqueue here, Dequeue from Front

Tiny Example

python
1s = Stack()
2s.push(10)
3s.push(20)
4print(s.pop())  # Prints 20

Walkthrough

Common Mistakes

Losing the Head Reference

In a linked list, if you reassign the head pointer before saving the next node, you lose the rest of the list forever in memory!

Debugging

Trace pointer updates meticulously on a whiteboard or paper.

Mini Project

Time: 20 min.

Goal: Implement a Stack class with push, pop, peek, is_empty. Use it to reverse a string.

💡 See One Approach (Mini Project)

This is one valid solution — yours may differ.

python
# Stack implementation — reverse a string
class Stack:
    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)  # O(1)

    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self._data.pop()   # O(1)

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek at empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

# Reverse a string using a stack (LIFO = natural reversal)
def reverse_string(s):
    stack = Stack()
    for char in s:
        stack.push(char)

    result = []
    while not stack.is_empty():
        result.append(stack.pop())
    return "".join(result)

test_words = ["hello", "racecar", "engineer", "Python"]
for word in test_words:
    rev = reverse_string(word)
    is_palindrome = word.lower() == rev.lower()
    print(f"  {word:12}  →  {rev:12}  {'🔄 palindrome!' if is_palindrome else ''}")

Bigger Project

Time: 1.5 hr.

Goal: Implement a Queue class. Simulate a printer queue: add 5 jobs, process them FIFO, printing each job's name as it's dequeued.

💡 See One Approach (Bigger Project)

This is one valid solution — yours may differ.

python
# Printer Queue simulation — FIFO
from collections import deque  # deque = O(1) append and popleft
import time

class PrintQueue:
    def __init__(self, name="Office Printer"):
        self.name = name
        self._queue = deque()
        self._processed = 0

    def add_job(self, document, pages, priority="normal"):
        job = {"doc": document, "pages": pages, "priority": priority, "id": len(self._queue) + self._processed + 1}
        if priority == "urgent":
            self._queue.appendleft(job)  # Jump to front
            print(f"  🚨 URGENT job added to FRONT: #{job['id']} {document}")
        else:
            self._queue.append(job)       # Normal: join the back
            print(f"  📄 Job added to queue:        #{job['id']} {document} ({pages}p)")

    def process_next(self):
        if not self._queue:
            print("  Queue is empty.")
            return None
        job = self._queue.popleft()  # FIFO: always process from front
        self._processed += 1
        time.sleep(0.02 * job["pages"])  # Simulate printing time
        print(f"  🖨️  Printed: #{job['id']} {job['doc']:30} ({job['pages']}p) — {len(self._queue)} jobs remaining")
        return job

    def process_all(self):
        print(f"
=== Processing all {len(self._queue)} queued jobs ===")
        while self._queue:
            self.process_next()
        print(f"  ✅ Done. {self._processed} total jobs processed.")

    def status(self):
        print(f"  Queue: {len(self._queue)} jobs | Processed: {self._processed}")

# Simulation
printer = PrintQueue()
print("=== Office Printer Queue ===")
printer.add_job("Q4_Report.pdf",       45)
printer.add_job("Meeting_Agenda.docx",  2)
printer.add_job("Design_Mockups.pdf",  12)
printer.add_job("Tax_Filing.pdf",      80)
printer.add_job("CEO_Presentation.pdf", 5, priority="urgent")  # Jumps to front
printer.add_job("Onboarding_Pack.pdf", 20)
printer.status()
printer.process_all()

Production Usage

The call stack IS a stack. Web browser history uses stacks. OS process scheduling relies heavily on queues.

Best Practices

Interview Questions

🟢 Easy:What is LIFO?

🔍 Reveal Answer
Last-In, First-Out.

🟡 Medium:When would you use a linked list over an array?

🔍 Reveal Answer
When you need frequent O(1) insertions/deletions at the ends or middle (if pointer is known), without resizing overhead.

🔴 Hard:How do you detect a cycle in a linked list?

🔍 Reveal Answer
Floyd's Tortoise and Hare algorithm (two pointers moving at different speeds).

Revision Sheet

✅ I can choose between arrays, linked lists, stacks, and queues based on the access pattern required.

Connections

← Previous (Chapter 7) Chapter 7 Next (Chapter 9) → Chapter 9