連結リストとスタック

Push "A" → [A]
Push "B" → [A, B]
Push "C" → [A, B, C]
Pop      → [A, B]  (removed "C")
Pop      → [A]     (removed "B")

Two operations define a stack:

• Push: Add an item to the top.
• Pop: Remove the item from the top.

Both are O(1) - instant, regardless of stack size.

Stacks in the Real World

• Undo/Redo: Every text editor maintains a stack of actions. Press Ctrl+Z and the most recent action is popped off and reversed.
• Browser back button: Your browsing history is a stack. Each new page is pushed; clicking "back" pops the current page.
• Call stacks: When your code calls a function, that function is pushed onto the call stack. When it finishes, it's popped off. This is how programmes keep track of where they are.

Stacks in AI

• Expression evaluation: AI compilers and interpreters use stacks to evaluate mathematical expressions in neural network computation graphs.
• Backtracking algorithms: When an AI explores possible solutions (like solving a maze), it uses a stack to remember where it's been so it can backtrack.
• Depth-first search: Traversing trees and graphs depth-first naturally uses a stack - we'll explore this in the next lesson.

Queues - First In, First Out (FIFO)

A queue works like a queue at a shop: the first person to join is the first person served. Items are added at the back and removed from the front.

Enqueue "A" → [A]
Enqueue "B" → [A, B]
Enqueue "C" → [A, B, C]
Dequeue     → [B, C]  (removed "A")
Dequeue     → [C]     (removed "B")

Two operations define a queue:

• Enqueue: Add an item to the back.
• Dequeue: Remove the item from the front.

Queues in the Real World

• Print queues: Documents are printed in the order they're submitted.
• Task scheduling: Operating systems use queues to manage which processes run next.
• Message queues: Web applications use queues (like RabbitMQ or Kafka) to handle thousands of requests without dropping any.

Queues in AI

• Breadth-first search (BFS): Exploring a graph level by level uses a queue - we'll see this in the trees and graphs lesson.
• Training data pipelines: Training data is loaded into queues so the GPU always has the next batch ready, preventing idle time.
• Request handling: When thousands of users query an AI API simultaneously, requests enter a queue and are processed in order.

Real AI Use: Sequence Processing and Memory Management

Sequence Processing

Language models process text as sequences. Under the hood, frameworks like PyTorch and TensorFlow use linked-list-like structures to build computation graphs - chains of operations where each step points to the next.

Memory Management in ML Frameworks

When training a neural network, memory is constantly allocated and freed as tensors (multi-dimensional arrays) are created and destroyed. Memory allocators often use linked lists of free memory blocks, finding suitable spaces for new tensors.

Key Takeaways

• Linked lists excel at dynamic data with frequent insertions and deletions, but sacrifice direct index access.
• Stacks (LIFO) power undo systems, backtracking, and depth-first traversal.
• Queues (FIFO) ensure fair ordering in task scheduling, BFS, and request handling.
• These structures often work behind the scenes in AI frameworks, managing memory and processing sequences.
• Choosing between arrays and linked structures depends on your access patterns - random access favours arrays, dynamic modification favours linked lists.