Stacks and Queues

Order of Service

Some of the most useful structures are deliberately restricted — they allow adding and removing only at particular ends, and that restriction is exactly what makes them useful.

A stack is a last-in, first-out (LIFO) structure. You push an element onto the top and pop the top element off; peek looks at the top without removing it. The last thing pushed is the first popped — like a stack of plates. Stacks appear everywhere: the call stack that tracks function calls, undo/redo histories, matching brackets, and evaluating expressions.

A queue is a first-in, first-out (FIFO) structure. You enqueue at the back and dequeue from the front; the first element added is the first removed — like a line of people. Queues model any "serve in arrival order" scenario: print jobs, task scheduling, and breadth-first graph traversal.

Both are ADTs and can be implemented with either an array or a linked list; when well implemented, push/pop and enqueue/dequeue are all $O(1)$. A common variant is the deque (double-ended queue), which allows adding and removing at both ends, generalizing both a stack and a queue.

Common pitfall: mixing up LIFO and FIFO — pushing to a stack and expecting to remove the oldest item, or treating a queue like a stack. A stack always returns the most recently added element; a queue always returns the oldest. Match the structure to whether you need "newest first" or "oldest first."