Stacks, Queues and Hash Tables

In this chapter

We'll learn three structures you already use every day without knowing it — the stack (a pile of plates), the queue (the line at a counter) and the hash table (a coat check) — and the key-value idea behind most of the software you use.

14–16 min

The Problem in Real Life

John puts a pile of paper plates on Anna's desk, then pins the festival waitlist next to it, and finally drops a coat-check ticket from last night's concert on top.

"Three objects," he says. "Three of the most important data structures in software. Once you see them, you'll see them everywhere — including in the fix for your seat map."

You've used these all your life. You just never gave them names.

John

One Structure for Everything vs. the Right Tool for Each Job

Order matters

Sometimes the newest item should come first; sometimes the oldest. The structure decides.

Instant lookups

Some structures can find an item by its name instantly, no matter how many items there are.

The seat map's real problem

Checking "is this seat sold?" by walking through 15,000 IDs is slow. There's a structure built for exactly this question.

Each of these structures is defined by one simple rule about how things go in and come out.

Stack — a pile of plates: you put a clean plate on top of the pile, and you take the top plate off. You never pull one from the bottom. The last plate in is the first one out — called LIFO (Last In, First Out). Adding is called push, removing is called pop.
Where stacks hide: your browser's Back button is a stack — every page you visit is pushed on top, and Back pops the most recent one. Undo (Ctrl+Z) is a stack of your recent changes. And every program has a call stack: when one function calls another, it's pushed on top; when it returns, it's popped off. You'll see the call stack properly in Act 10.
Queue — the line at a ticket counter: the first person to join the line is the first person served. New people join at the back. That's FIFO (First In, First Out). Adding is called enqueue, removing is called dequeue.
Where queues hide: the festival waitlist is a queue — when a ticket comes back, the person who joined first gets the offer. A printer handles jobs in the order they arrive. And in Act 14, BlueTicket will put all its SMS confirmations into a queue so a sudden rush doesn't overload anything.
Hash table — a coat check: at a concert, you hand over your coat and get ticket number 247. When you come back, the attendant doesn't search every coat — they go straight to hook 247. A hash table works like this. You give it a key (like a seat ID), and it instantly finds the value stored with it (like that seat's details).
How the hash table finds things so fast: it uses a hash function — a small calculation that turns any key into a hook number. The key "C14" might become hook 3,812. To store it, put it on hook 3,812. To find it later, run the same calculation and go straight there. No searching. That's why looking something up in a hash table takes about the same time with 10 items or 10 million.

Table — Stack vs. queue vs. hash table

Structure	Everyday version	Rule	Used for
Stack	A pile of plates	Last in, first out (LIFO)	Back button, undo, call stack
Queue	Line at a ticket counter	First in, first out (FIFO)	Waitlists, print jobs, message queues
Hash table	Coat check	Key → straight to the value	Fast lookup by ID, name or code

Table — A coat check, step by step

Step	Coat check	Hash table
Store	Hand in coat, get ticket 247	hash("C14") = 3812 → store seat C14 at 3812
Find	Show ticket 247, attendant goes to hook 247	hash("C14") = 3812 → read slot 3812
Speed	Same with 10 coats or 2,000	Same with 10 keys or 10 million

Table — Key-value data all around you

Thing	Key	Value
Dictionary	A word	Its meaning
Phone contacts	A name	A phone number
Seat lookup	Seat ID "C14"	Row C, seat 14, price, state
App settings	"currency"	"USD"

Three rules for in and out

Stack — pile of plates

add on top, take from top: last in, first out

Queue — line at a counter

join at the back, served from the front: first in, first out

Hash table — coat check

key → hash function → hook number → value, instantly

The three structures in JavaScript

// Stack: push and pop at the end
const history = [];
history.push("/events");
history.push("/events/festival");
history.pop();                 // "/events/festival" — the most recent one

// Queue: add at the end, take from the front
const waitlist = [];
waitlist.push("Zoë");
waitlist.push("Liam");
waitlist.shift();              // "Zoë" — the first one who joined

// Hash table: key → value, with Map (or Set for "does it exist?")
const seats = new Map();
seats.set("C14", { row: "C", number: 14, state: "SOLD" });
seats.get("C14");              // instant

const soldIds = new Set(["C14", "C15", "D2"]);
soldIds.has("C14");            // true — instant

shift() on a very large array is slow, so real systems use a proper queue for big workloads — but the idea is the same.

Key-value data — the idea behind almost everything: a hash table stores key-value pairs: a key you look up by, and the value that goes with it. A dictionary (word → meaning), a phone's contacts (name → number), a website's settings (setting name → value) are all key-value data. In JavaScript you use an object or a Map for key-value pairs, and a Set when you only care whether a key exists. In Python it's a dict. Many databases are built entirely on this idea (Act 13).

The fix appears: Anna looks at her seat-map code again. For each of the 20,000 seats, it asks "is this seat ID in the sold list?" — and answers by walking through an array of 15,000 sold IDs. That's the messy drawer from chapter 1. The question "does this key exist?" is exactly what a hash table is for. If the sold IDs are put into a Set first, each check becomes a coat-check lookup: instant. She writes it down. John grins. "Hold that thought — in the last chapter we'll measure exactly how much faster."

Key Takeaway

A stack is a pile of plates (last in, first out) — used for Back buttons, undo and the call stack. A queue is a line at a counter (first in, first out) — used for waitlists and job queues. A hash table is a coat check — a hash function turns a key straight into a location, so lookups by key are almost instant, no matter how much data there is.

Why This Matters

These three structures run a huge part of the software world: every browser's Back button, every app's undo, every job queue, every cache and almost every fast lookup. When something needs to happen "in order" or "by name, instantly," one of them is usually the answer — including the seat-map fix Anna is about to make.

Some data isn't a line or a pile at all. A stadium has sections, which have rows, which have seats. And venues are connected to cities by roads and train lines. That kind of data branches and connects — and it needs different shapes.