Stacks & Queues

Two ways to line things up

A stack is LIFO — last in, first out. Think of an undo history: the last action you did is the first you undo. In Python a plain list is a stack: append to push, pop() to pop off the end. Both are O(1).

A queue is FIFO — first in, first out. Think of a job queue: the first job enqueued is the first one worked. That means adding at one end and removing from the other.