Day 4 — Stacks & Queues

Today is about two of the most quietly important data structures in computer science: stacks and queues. They don’t get the glamour of trees or graphs, but they hide inside everything from your browser’s back button to the way operating systems schedule processes.

The big idea: both are just lists with a rule about which end you’re allowed to touch.

What’s a Stack?

A stack is a list where you can only add or remove from one end — the top. Last in, first out (LIFO).

Think of a stack of plates:

You can only put a plate on the top of the pile.
You can only take a plate from the top of the pile.
The plate at the bottom has been there the longest and will be the last one removed.

The two core operations are:

push(x) — put x on the top
pop() — remove and return the top item

That’s it. There’s also peek() (look at the top without removing) and isEmpty(), but those are conveniences, not new ideas.

The “stack” you’ve heard about — the call stack that crashes when you have infinite recursion — is literally this data structure. Each function call pushes a frame; each return pops one.

What’s a Queue?

A queue is a list where you add at one end and remove from the other end. First in, first out (FIFO).

Think of a line at a coffee shop:

New customers join at the back (enqueue).
The barista serves the customer at the front (dequeue).
The customer who’s been waiting longest gets served first. (As it should be.)

The two core operations are:

enqueue(x) — add x to the back
dequeue() — remove and return the front item

Stack vs Queue — the one-line difference

	Add at	Remove at	Order	Real-life analogue
Stack	top	top	LIFO	Pile of plates, browser history
Queue	back	front	FIFO	Line at a checkout, print spooler

Why we care

Both look like “just a list with a restriction.” That’s the whole point. The restriction is what makes them useful — it forces a particular order on the data, and a huge number of problems become trivial once you spot that the right order is LIFO or FIFO.

A few places they show up:

Stacks — function calls, undo/redo, expression evaluation, balanced parentheses, depth-first search, browser back button.
Queues — task scheduling, breadth-first search, message buffers, print jobs, request handling in web servers.

What we’ll cover today

How to implement a stack two different ways (array-backed and linked-list-backed) and which to pick when.
The classic stack problems: valid parentheses, next greater element, evaluating expressions.
The same for queues, plus the surprisingly common deque (double-ended queue) and circular queue.
The complexity story for every operation.

Head over to Stacks in the sidebar to start with LIFO.

Overview Introduction