Stack Basics | LIFO Data Structure | Stack

Overview

A stack is a Last-In, First-Out (LIFO) data structure: the last element added is the first one removed. Think of a stack of plates: you add and remove from the top only. This constraint makes stacks ideal for reversing order, matching pairs (e.g. brackets), undo/backtrack, and parsing (expression evaluation, recursion simulation).

Core operations:

push(x) — add x on top; O(1).
pop() — remove and return the top element; O(1).
peek() / top() — return the top element without removing; O(1).
isEmpty() — return true if no elements; O(1).
size() — optional; O(1) if you maintain a counter.

Implementation: Use an array (with push/pop at the end) or a singly linked list (add/remove at the head). Both give O(1) per operation.

When to Use a Stack

Matching pairs — Valid parentheses, valid brackets, HTML tags. Push opening symbols; on closing, pop and check match.
Reversing — Push all, then pop all to get reverse order (e.g. reverse a string, "next greater" when scanning backward).
Nested structure — Parsing nested expressions (e.g. 3[a2[c]]), recursion call stack, DFS.
Monotonic stack — Maintain "next greater" or "next smaller" efficiently; see Monotonic Stack.
Undo / backtrack — Push state before a choice; pop to backtrack.

How It Works (Array-Based)

Use a dynamic array and a logical "top" (e.g. the last index). Push: append and increment; pop: remove last and return. In JavaScript/TypeScript, the array itself is the stack: stack.push(x), stack.pop(), stack[stack.length - 1] for peek.

const stack: number[] = [];
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack[stack.length - 1]); // 2 (peek)
console.log(stack.pop()); // 2

Example 1: Reverse a List Using a Stack

Problem: Reverse the order of elements using only a stack.

Push all elements onto the stack, then pop all into a new list. The new list is the reverse.

function reverseWithStack<T>(arr: T[]): T[] {
  const stack: T[] = [];
  for (const x of arr) stack.push(x);
  const result: T[] = [];
  while (stack.length > 0) result.push(stack.pop()!);
  return result;
}

Time: O(n), Space: O(n).

Example 2: Check Balanced Brackets (Teaser)

Use a stack to match opening and closing brackets. Push opening brackets; on a closing bracket, pop and check that it matches. If the stack is empty when you need to pop, or non-empty at the end, the string is invalid. See Valid Parentheses for the full pattern.

Example 3: Stack with Linked List

Problem: Implement a stack using a singly linked list (no array).

Store only the head; the top of the stack is the head. Push: create a new node, set its next to the current head, set head to the new node. Pop: if head is null return null; else save head.val, set head = head.next, return the saved value.

class ListNode { val: number; next: ListNode | null; constructor(v: number) { this.val = v; this.next = null; } }
class Stack {
  private head: ListNode | null = null;
  push(x: number): void {
    const node = new ListNode(x);
    node.next = this.head;
    this.head = node;
  }
  pop(): number | null {
    if (this.head === null) return null;
    const val = this.head.val;
    this.head = this.head.next;
    return val;
  }
  peek(): number | null { return this.head?.val ?? null; }
  isEmpty(): boolean { return this.head === null; }
}

All operations O(1).

Edge Cases

Empty stack pop/peek — Return null, -1, or throw; document the contract.
Capacity — Array-based stack may need to grow (dynamic array handles this); linked-list stack has no fixed capacity.

Common Mistakes

Using the wrong end — Stack is LIFO; always push and pop from the same end (e.g. back of array).
Peek then pop — Peek does not remove; pop removes and returns. Don't confuse the two.
Assuming order — Stack does not support random access; only the top is visible.

Time and Space Complexity

push, pop, peek, isEmpty: O(1).
Space: O(n) for n elements stored.

Summary

Stack = LIFO. Operations: push, pop, peek; all O(1) with array or linked list.
Use for matching pairs, reversing, nested parsing, and as the basis for Valid Parentheses, Min Stack, and Monotonic Stack patterns.

Stack Basics (LIFO, Operations)