Stack - The Last-In, First-Out Data Structure

A Stack is one of computing’s most elegant abstractions: a collection where you can only add or remove from one end — the top. The last item pushed on is the first item popped off. This LIFO (Last-In, First-Out) discipline seems restrictive, yet it perfectly models a surprising number of real-world problems — including how your programming language executes function calls.

A Brief History

The stack as a formal data structure was introduced by Friedrich L. Bauer and Klaus Samelson in 1957 in their work on the Bauer-Samelson algorithm for arithmetic expression evaluation. They coined the term “Kellerspeicher” (cellar store), later translated to stack. The concept was simultaneously and independently developed by Charles Leonard Hamblin in Australia around the same time. Their work directly influenced the design of hardware architectures — virtually every modern CPU has a hardware stack for managing function calls and local variables. The concept is so fundamental that it’s baked into silicon.

How It Works

A stack exposes just two primary operations:

• Push: Add an element to the top — $O(1)$
• Pop: Remove and return the top element — $O(1)$
• Peek (or Top): View the top element without removing it — $O(1)$
• isEmpty: Check whether the stack is empty — $O(1)$

All core operations run in $O(1)$. This is the stack’s superpower — constant-time access to the most recently added element, always.

A stack can be implemented on top of:

• An array — simple, cache-friendly, slightly limited by fixed capacity (though dynamic arrays resize automatically)
• A linked list — naturally dynamic, with $O(1)$ push/pop at the head

Space Complexity

A stack holding $n$ elements uses $O(n)$ space — one slot per element, no overhead beyond the backing structure.

Advantages and Disadvantages

Advantages:

• $O(1)$ push and pop — constant time for all core operations
• Simple, well-understood interface
• Perfectly models LIFO access patterns
• Low overhead — just a backing array or linked list plus a pointer/index

Disadvantages:

• No random access — you can only see the top
• Accessing an arbitrary element requires popping everything above it first: $O(n)$
• Stack overflow — unbounded recursive use of the call stack can exhaust memory (this is literally where the term comes from)

When to Use a Stack

Stacks are the right data structure for any LIFO access pattern:

• Function call management — every time you call a function, its frame is pushed. When it returns, it’s popped. This is why recursive algorithms naturally map to stacks — you can always convert recursion to an explicit stack
• Undo/redo — each action is pushed; pressing undo pops the last action
• Expression evaluation and parsing — evaluating 3 + (4 × 2) uses a stack to handle operator precedence; compilers use stacks to match brackets
• Browser history — the back button is a pop; visiting a new page is a push
• DFS traversal — Depth-First Search is naturally stack-based (use an explicit stack to avoid recursion limits in JavaScript)
• Balanced parentheses check — a classic interview problem: push open brackets, pop and verify on close brackets
• Monotone stack — a specialized stack technique for “next greater element” and histogram problems

In JavaScript, Array doubles as a stack out of the box — push() adds to the end, pop() removes from the end, both in $O(1)$ (amortized for push with dynamic resizing). No custom implementation needed for most use cases.

In conclusion, the stack’s value comes from its constraint. By enforcing LIFO order, it perfectly captures the “most recent thing first” access pattern that appears constantly in computing — from CPU architecture to algorithm design. When you reach for a stack, the structure itself communicates intent: you’re managing ordered context where the latest matters most.