Stack Data Structure LIFO, push, pop

LIFO Invariant

A stack is a last-in, first-out collection. push adds to the top, pop removes the top, and peek reads it without removal. A correct stack defines empty behavior, capacity growth, and the ownership of stored values.

Only the top element is directly added or removed. After pushing x, peek returns x until it is popped. The implementation may use a dynamic array or linked nodes, but callers should depend on stack behavior rather than storage details.

Operations and Complexity

push, pop, peek, and isEmpty are O(1) for a linked stack. A dynamic-array push is amortized O(1) and occasionally O(n) during resize. Array storage has good locality; linked storage allocates per element and has pointer overhead.

Where Stacks Fit

Use stacks for nested parsing, undo history, depth-first search, expression evaluation, browser-style back navigation, and replacing recursion when depth must be explicit. A call stack also stores return state, which explains why uncontrolled recursion can overflow.

Underflow, Limits, and Tests

Popping an empty stack must return an explicit failure, throw according to the language API, or be prevented by a checked precondition. Fixed-capacity stacks also define overflow. Test empty, one element, repeated values, growth, complete draining, and push-after-drain.

Array-Backed Stack

class Stack {
        #items = [];
        push(value) { this.#items.push(value); }
        pop() {
          if (this.#items.length === 0) throw new Error('stack underflow');
          return this.#items.pop();
        }
        peek() {
          if (this.#items.length === 0) return undefined;
          return this.#items[this.#items.length - 1];
        }
        get size() { return this.#items.length; }
      }

Validate Nested Delimiters

A stack remembers the most recent unmatched opening delimiter.

Validate Nested Delimiters

function balanced(text) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const char of text) {
    if ('([{'.includes(char)) stack.push(char);
    if (pairs[char] && stack.pop() !== pairs[char]) return false;
  }
  return stack.length === 0;
}
console.log(balanced('{a:[1,2]}'), balanced('([)]'));

Output

true false

The final empty-stack check catches unmatched opening delimiters.

Before you move on