Stacks
A stack is one of the most fundamental data structures in computer science. It follows the Last-In, First-Out (LIFO) principle — the last element added to the stack is the first one removed. Think of it as a vertical pile where you can only interact with the top.
The LIFO Principle
The easiest way to understand LIFO is through everyday analogies:
Stack of plates — You place a new plate on top and always take from the top. You cannot grab a plate from the middle without removing those above it first.
Browser back button — Every page you visit gets pushed onto a stack. Pressing Back pops the current page off, revealing the previous one.
Undo / Redo in a text editor — Each action is pushed onto an undo stack. Pressing Ctrl+Z pops the last action and reverses it; the redo stack holds what was undone.
Function call stack — When a function calls another function, the new frame is pushed. When it returns, that frame is popped and execution resumes in the caller.
Visual Diagram: Push and Pop
The two core operations of a stack are push (add to top) and pop (remove from top).
Initial PUSH 10 PUSH 20 POP 20 ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ │ │ │ │ 20 │ ← │ │ │ │ → │ 10 │ → │ 10 │ │ 10 │ │ │ │ │ │ │ │ │ └──────┘ └──────┘ └──────┘ └──────┘ (empty) Top: 10 Top: 20 Top: 10 PUSH: place element on top O(1) POP: remove element from top O(1) PEEK: read top without removal O(1)
Array-Based Stack (JavaScript)
The simplest implementation wraps a plain array and exposes only the stack operations.
Because JavaScript arrays provide O(1) amortised push and pop at the end of the
array, every stack operation is O(1).
class Stack {
constructor() {
this._data = []; // internal storage
this._size = 0; // track length explicitly
}
// Add an element to the top of the stack — O(1)
push(value) {
this._data[this._size] = value;
this._size++;
}
// Remove and return the top element — O(1)
// Returns undefined if the stack is empty
pop() {
if (this.isEmpty()) return undefined;
const top = this._data[this._size - 1];
this._data.length = this._size - 1; // shrink backing array
this._size--;
return top;
}
// Return the top element WITHOUT removing it — O(1)
peek() {
if (this.isEmpty()) return undefined;
return this._data[this._size - 1];
}
// Check whether the stack has no elements — O(1)
isEmpty() {
return this._size === 0;
}
// Number of elements currently in the stack — O(1)
size() {
return this._size;
}
// Print the stack from bottom to top
print() {
if (this.isEmpty()) {
console.log('(empty stack)');
return;
}
console.log('Top → ' + [...this._data].reverse().join(' | '));
}
}
// --- Usage ---
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.print(); // Top → 30 | 20 | 10
console.log(stack.peek()); // 30 (stack unchanged)
console.log(stack.pop()); // 30 (removed)
console.log(stack.pop()); // 20 (removed)
console.log(stack.size()); // 1
stack.print(); // Top → 10push() and pop() methods, so array.push(x) and array.pop() work as a quick-and-dirty stack. Wrapping them in a class gives you a controlled interface, prevents accidental index-based access, and makes your intent explicit to other developers.Linked-List-Based Stack (JavaScript)
An alternative is to build the stack on top of a singly linked list. Each node holds a value and a pointer to the node below it. Push and pop only manipulate the head node, so both operations remain O(1) with no amortised cost and no array resizing involved.
// A single node in the linked list
class Node {
constructor(value) {
this.value = value;
this.next = null; // points to the node below in the stack
}
}
class LinkedStack {
constructor() {
this._top = null; // head of the linked list (top of stack)
this._size = 0;
}
// Push: create a new node and point it at the current top — O(1)
push(value) {
const node = new Node(value);
node.next = this._top; // new node sits on top of the old top
this._top = node;
this._size++;
}
// Pop: detach and return the top node's value — O(1)
pop() {
if (this.isEmpty()) return undefined;
const value = this._top.value;
this._top = this._top.next; // move top pointer one level down
this._size--;
return value;
}
// Peek: read value of the top node without removing — O(1)
peek() {
if (this.isEmpty()) return undefined;
return this._top.value;
}
isEmpty() {
return this._top === null;
}
size() {
return this._size;
}
// Print from top to bottom by walking the linked list
print() {
if (this.isEmpty()) {
console.log('(empty stack)');
return;
}
const elements = [];
let current = this._top;
while (current !== null) {
elements.push(current.value);
current = current.next;
}
console.log('Top → ' + elements.join(' | '));
}
}
// --- Usage ---
const ls = new LinkedStack();
ls.push('a');
ls.push('b');
ls.push('c');
ls.print(); // Top → c | b | a
console.log(ls.peek()); // c
console.log(ls.pop()); // c
ls.print(); // Top → b | a
console.log(ls.size()); // 2Array vs Linked List — Comparison
Property | Array Stack | Linked List Stack |
|---|---|---|
Push / Pop time | O(1) amortised | O(1) guaranteed |
Peek time | O(1) | O(1) |
Memory per element | Value only | Value + next pointer (overhead) |
Memory allocation | Contiguous block (may resize) | Heap-allocated per node |
Cache performance | Excellent (spatial locality) | Poor (nodes scattered in memory) |
Max size known in advance? | Can pre-allocate with fixed array | Grows dynamically, no pre-allocation needed |
Overhead | Negligible | Extra pointer per node |
Best used when | Performance-critical; size roughly known | Unbounded growth; avoiding resize pauses |
Common Use Cases
1. Function Call Stack
Every time a function is called, the runtime pushes a stack frame containing the function's local variables and return address. When the function returns, the frame is popped. This is why unbounded recursion causes a stack overflow — the call stack runs out of space.
// Recursion uses the hidden call stack implicitly.
// Converting to an explicit stack avoids stack-overflow on deep input.
function factorialRecursive(n) {
if (n <= 1) return 1;
return n * factorialRecursive(n - 1); // each call is a push
} // each return is a pop
// Iterative version using an explicit stack
function factorialIterative(n) {
const stack = new Stack();
for (let i = n; i > 1; i--) stack.push(i);
let result = 1;
while (!stack.isEmpty()) result *= stack.pop();
return result;
}
console.log(factorialRecursive(5)); // 120
console.log(factorialIterative(5)); // 1202. Undo / Redo
Text editors and design tools maintain two stacks: an undo stack and a redo stack. Performing an action pushes a snapshot onto the undo stack (and clears redo). Pressing Undo pops from undo and pushes to redo. Pressing Redo does the reverse.
class TextEditor {
constructor() {
this._text = '';
this._undo = new Stack();
this._redo = new Stack();
}
type(text) {
this._undo.push(this._text); // save current state
this._redo = new Stack(); // clear redo history on new action
this._text += text;
}
undo() {
if (this._undo.isEmpty()) return;
this._redo.push(this._text);
this._text = this._undo.pop();
}
redo() {
if (this._redo.isEmpty()) return;
this._undo.push(this._text);
this._text = this._redo.pop();
}
read() { return this._text; }
}
const editor = new TextEditor();
editor.type('Hello');
editor.type(', World');
console.log(editor.read()); // Hello, World
editor.undo();
console.log(editor.read()); // Hello
editor.redo();
console.log(editor.read()); // Hello, World3. Balanced Parentheses / Expression Evaluation
Checking whether brackets are balanced is a classic stack problem. Push every opening bracket; when you see a closing bracket, pop and verify it matches. If the stack is empty at the end, the expression is balanced.
function isBalanced(expression) {
const stack = new Stack();
const pairs = { ')': '(', ']': '[', '}': '{' };
for (const ch of expression) {
if ('([{'.includes(ch)) {
stack.push(ch);
} else if (')]}'.includes(ch)) {
if (stack.isEmpty() || stack.pop() !== pairs[ch]) return false;
}
}
return stack.isEmpty();
}
console.log(isBalanced('({[]})')); // true
console.log(isBalanced('({[}])')); // false
console.log(isBalanced('((())')); // false4. Depth-First Search (DFS)
Graph and tree DFS can be implemented iteratively with an explicit stack, mimicking what the recursion would do implicitly via the call stack.
// Iterative DFS on an adjacency list graph
function dfs(graph, start) {
const visited = new Set();
const stack = new Stack();
const order = [];
stack.push(start);
while (!stack.isEmpty()) {
const node = stack.pop();
if (visited.has(node)) continue;
visited.add(node);
order.push(node);
// Push neighbours in reverse so the leftmost is processed first
for (const neighbour of [...(graph[node] || [])].reverse()) {
if (!visited.has(neighbour)) stack.push(neighbour);
}
}
return order;
}
const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [], E: [], F: [],
};
console.log(dfs(graph, 'A')); // ['A', 'B', 'D', 'E', 'C', 'F']5. Backtracking Algorithms
Backtracking problems (maze solving, N-Queens, Sudoku) are naturally expressed with a stack. Push candidate states onto the stack; if a state leads to a dead end, pop it and try the next candidate.
// Find a path through a maze represented as a grid.
// 0 = open, 1 = wall. Returns array of [row, col] steps or null.
function solveMaze(grid, start, end) {
const stack = new Stack();
const visited = new Set();
const key = ([r, c]) => `${r},${c}`;
stack.push({ pos: start, path: [start] });
while (!stack.isEmpty()) {
const { pos, path } = stack.pop();
const [r, c] = pos;
if (key(pos) === key(end)) return path;
if (visited.has(key(pos))) continue;
visited.add(key(pos));
for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
const nr = r + dr, nc = c + dc;
if (
nr >= 0 && nr < grid.length &&
nc >= 0 && nc < grid[0].length &&
grid[nr][nc] === 0 &&
!visited.has(`${nr},${nc}`)
) {
stack.push({ pos: [nr, nc], path: [...path, [nr, nc]] });
}
}
}
return null; // no path found
}Time and Space Complexity
Operation | Array Stack | Linked List Stack | Notes |
|---|---|---|---|
push() | O(1) amortised | O(1) | Array may resize occasionally; linked list never does |
pop() | O(1) | O(1) | Both are true constant time removal |
peek() | O(1) | O(1) | Read without mutation |
isEmpty() | O(1) | O(1) | Single comparison |
size() | O(1) | O(1) | Maintained as a counter |
Space (n elements) | O(n) | O(n) | Linked list has constant pointer overhead per node |
Key Takeaways
LIFO is the defining characteristic — the most recently pushed item is always the next to be popped.
Both array-based and linked-list-based implementations provide O(1) push, pop, and peek.
Prefer array-based stacks for raw performance (better cache behaviour). Prefer linked-list-based when the stack can grow without bound and you want to avoid array-resize pauses.
JavaScript's native array already acts as a stack via
push()andpop()— wrapping it in a class is an architectural choice, not a performance requirement.Stacks underpin some of the most important algorithms: DFS, balanced-bracket checking, expression evaluation, and all backtracking strategies.
The call stack maintained by every JavaScript engine is itself a stack — deep recursion without a base case will exhaust it and throw a RangeError.