Skip to main content

​
Stack

A Last-In-First-Out (LIFO) data structure where elements are added and removed from the same end (the top).

​
Overview

Stacks follow the principle of “last in, first out.” Think of a stack of plates - you can only add or remove plates from the top. This implementation uses a singly linked list internally for O(1) push and pop operations.

​
Implementation

​
Class Definition

import { SinglyLinkedList } from '../lists/singly-linked-list/singly-linked-list';

class Stack<T = number> {
  #stack = new SinglyLinkedList<T>();
  
  // ... methods
}
Reference: stack.ts:1-4
The implementation uses a private singly linked list (#stack) for storage, leveraging its O(1) head insertion and deletion.

​
API Reference

​
push(item: T): void

Adds an item to the top of the stack. 
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
// Stack: [1][2][3] (3 is on top)
Complexity: O(1) Reference: stack.ts:10-12

​
pop(): T | undefined

Removes and returns the top element from the stack. 
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
const top = stack.pop(); // returns 2
// Stack: [1]
Returns: The removed element, or undefined if stack is empty Complexity: O(1) Reference: stack.ts:18-20

​
peek(): T | undefined

Returns the top element without removing it. 
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
const top = stack.peek(); // returns 2
// Stack: [1][2] (unchanged)
Returns: The top element, or undefined if stack is empty Complexity: O(1) Reference: stack.ts:25-27

​
isEmpty(): boolean

Checks if the stack is empty. 
const stack = new Stack<number>();
console.log(stack.isEmpty()); // true
stack.push(1);
console.log(stack.isEmpty()); // false
Complexity: O(1) Reference: stack.ts:32-34

​
size: number

Gets the number of elements in the stack. 
const stack = new Stack<number>();
console.log(stack.size); // 0
stack.push(1);
stack.push(2);
console.log(stack.size); // 2
Complexity: O(1) Reference: stack.ts:36-38

​
toString(): string

Returns a string representation of the stack. 
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.toString()); // "[1][2][3]"
Complexity: O(n) Reference: stack.ts:40-53

​
Problems & Solutions

​
Problem 1: Sort Stack

Sort a stack such that the smallest items are on top, using only one additional stack. 
/**
 * Time complexity: O(n²)
 * Space complexity: O(n)
 */
function sortStack(stack: Stack<number>) {
  const auxStack = new Stack<number>();

  while (!stack.isEmpty()) {
    const temp = stack.pop();

    // Move elements from aux back to main if they're greater
    while (!auxStack.isEmpty() && temp! > auxStack.peek()!) {
      stack.push(auxStack.pop()!);
    }

    auxStack.push(temp!);
  }

  // Transfer back to original stack
  while (!auxStack.isEmpty()) {
    stack.push(auxStack.pop()!);
  }
}

// Example: [4][2][1][3] -> [1][2][3][4]
Reference: stack.problems.test.ts:5-37

​
Problem 2: Base Converter

Convert a decimal number to any base (2-36) using a stack. 
/**
 * Time complexity: O(log n)
 * Space complexity: O(log n)
 */
function baseConverter(num: number, base: number): string {
  const stack = new Stack<number>();
  const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

  while (num > 0) {
    const remainder = Math.floor(num % base);
    stack.push(remainder);
    num = Math.floor(num / base);
  }

  let output = '';
  while (!stack.isEmpty()) {
    output += digits[stack.pop()!];
  }

  return output;
}

// Examples:
// baseConverter(10, 2) -> "1010"
// baseConverter(100345, 16) -> "187F9"
Reference: stack.problems.test.ts:40-68

​
Complexity Summary

OperationTime ComplexitySpace Complexity
pushO(1)O(1)
popO(1)O(1)
peekO(1)O(1)
isEmptyO(1)O(1)
sizeO(1)O(1)
toStringO(n)O(1)

​
Common Use Cases

​
Function Call Stack

// The JavaScript engine uses a stack for function calls
function recursive(n: number) {
  if (n === 0) return;
  recursive(n - 1); // Each call is pushed onto the call stack
}

​
Expression Evaluation

// Evaluate postfix expressions
// Example: "3 4 + 2 *" = (3 + 4) * 2 = 14
function evaluatePostfix(expression: string): number {
  const stack = new Stack<number>();
  const tokens = expression.split(' ');
  
  for (const token of tokens) {
    if (!isNaN(Number(token))) {
      stack.push(Number(token));
    } else {
      const b = stack.pop()!;
      const a = stack.pop()!;
      // Apply operator and push result
    }
  }
  
  return stack.pop()!;
}

​
Parentheses Matching

function isBalanced(str: string): boolean {
  const stack = new Stack<string>();
  const pairs: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{'
  };
  
  for (const char of str) {
    if (['(', '[', '{'].includes(char)) {
      stack.push(char);
    } else if (pairs[char]) {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  
  return stack.isEmpty();
}

​
Undo/Redo Functionality

class TextEditor {
  private history = new Stack<string>();
  private redoStack = new Stack<string>();
  private currentText = '';
  
  type(text: string) {
    this.history.push(this.currentText);
    this.currentText += text;
    this.redoStack = new Stack(); // Clear redo on new action
  }
  
  undo() {
    if (!this.history.isEmpty()) {
      this.redoStack.push(this.currentText);
      this.currentText = this.history.pop()!;
    }
  }
  
  redo() {
    if (!this.redoStack.isEmpty()) {
      this.history.push(this.currentText);
      this.currentText = this.redoStack.pop()!;
    }
  }
}

​
Key Characteristics

Advantages:
  • Simple and intuitive LIFO principle
  • O(1) push and pop operations
  • Memory efficient
  • Natural fit for recursive algorithms
Limitations:
  • No random access to elements
  • Can only access top element
  • Stack overflow with too many elements
  • Not suitable for priority-based access

​
When to Use a Stack

Depth-first search, maze solving, N-Queens problem - stacks naturally support backtracking by maintaining state history.
Infix to postfix conversion, calculator implementations, compiler syntax analysis - stacks help maintain operator precedence.
Reverse strings, arrays, or any sequence - push all elements and pop them back out in reverse order.
Matching brackets, HTML tag validation, tree traversal - stacks track nesting levels.
For scenarios requiring access to both ends, consider using a Queue or Deque instead.

Queue

FIFO alternative to LIFO stack

Singly Linked List

Underlying implementation

Build docs developers (and LLMs) love

Get started for freeTalk to us