Stacks

What is a Stack?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Think of it like a stack of plates - you can only add or remove plates from the top. The last plate you place on the stack is the first one you'll remove.

Stacks are one of the most fundamental data structures in computer science and are used extensively in algorithms, memory management, and expression evaluation.

Stack Operations

Stack Implementation Using Array

class Stack {
  constructor() {
    this.items = [];
  }

  // Push element onto stack - O(1)
  push(element) {
    this.items.push(element);
  }

  // Pop element from stack - O(1)
  pop() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty');
    }
    return this.items.pop();
  }

  // Peek at top element - O(1)
  peek() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty');
    }
    return this.items[this.items.length - 1];
  }

  // Check if stack is empty - O(1)
  isEmpty() {
    return this.items.length === 0;
  }

  // Get stack size - O(1)
  size() {
    return this.items.length;
  }

  // Clear the stack - O(1)
  clear() {
    this.items = [];
  }

  // Print stack contents
  print() {
    console.log(this.items.join(' ← '));
  }
}

// Usage
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.print();  // 1 ← 2 ← 3

console.log(stack.peek());  // 3
console.log(stack.pop());   // 3
stack.print();  // 1 ← 2

Stack Implementation Using Linked List

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  // Push element - O(1)
  push(data) {
    const newNode = new Node(data);
    newNode.next = this.top;
    this.top = newNode;
    this.length++;
  }

  // Pop element - O(1)
  pop() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty');
    }
    const poppedData = this.top.data;
    this.top = this.top.next;
    this.length--;
    return poppedData;
  }

  // Peek at top - O(1)
  peek() {
    if (this.isEmpty()) {
      throw new Error('Stack is empty');
    }
    return this.top.data;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }
}

Common Stack Problems

1. Valid Parentheses

Check if string has valid bracket matching.

function isValidParentheses(s) {
  const stack = [];
  const pairs = {
    '(': ')',
    '[': ']',
    '{': '}'
  };
  
  for (let char of s) {
    // If opening bracket, push to stack
    if (pairs[char]) {
      stack.push(char);
    } 
    // If closing bracket
    else {
      // Stack must not be empty and top must match
      const top = stack.pop();
      if (!top || pairs[top] !== char) {
        return false;
      }
    }
  }
  
  // Stack should be empty for valid string
  return stack.length === 0;
}

console.log(isValidParentheses('()[]{}'));    // true
console.log(isValidParentheses('([)]'));      // false
console.log(isValidParentheses('{[()]}'));    // true

2. Reverse a String

function reverseString(str) {
  const stack = [];
  
  // Push all characters onto stack
  for (let char of str) {
    stack.push(char);
  }
  
  // Pop all characters to build reversed string
  let reversed = '';
  while (stack.length > 0) {
    reversed += stack.pop();
  }
  
  return reversed;
}

console.log(reverseString('hello'));  // 'olleh'

3. Evaluate Postfix Expression

function evaluatePostfix(expression) {
  const stack = [];
  const tokens = expression.split(' ');
  
  for (let token of tokens) {
    // If number, push to stack
    if (!isNaN(token)) {
      stack.push(Number(token));
    } 
    // If operator, pop two operands and apply
    else {
      const b = stack.pop();
      const a = stack.pop();
      
      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(a / b); break;
      }
    }
  }
  
  return stack.pop();
}

console.log(evaluatePostfix('2 3 1 * + 9 -'));  // -4
// Explanation: ((2 + (3 * 1)) - 9) = -4

4. Next Greater Element

function nextGreaterElements(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = [];
  
  for (let i = 0; i < arr.length; i++) {
    // Pop elements smaller than current
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      const index = stack.pop();
      result[index] = arr[i];
    }
    stack.push(i);
  }
  
  return result;
}

console.log(nextGreaterElements([4, 5, 2, 10]));  // [5, 10, 10, -1]
console.log(nextGreaterElements([2, 1, 3, 4]));   // [3, 3, 4, -1]

5. Min Stack (Get Minimum in O(1))

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];  // Track minimums
  }

  push(val) {
    this.stack.push(val);
    
    // Update min stack
    if (this.minStack.length === 0 || val <= this.getMin()) {
      this.minStack.push(val);
    }
  }

  pop() {
    const val = this.stack.pop();
    
    // If popped value is min, remove from min stack
    if (val === this.getMin()) {
      this.minStack.pop();
    }
    
    return val;
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

const minStack = new MinStack();
minStack.push(3);
minStack.push(5);
console.log(minStack.getMin());  // 3
minStack.push(2);
console.log(minStack.getMin());  // 2
minStack.pop();
console.log(minStack.getMin());  // 3

6. Convert Infix to Postfix

function infixToPostfix(expression) {
  const precedence = { '+': 1, '-': 1, '*': 2, '/': 2, '^': 3 };
  const stack = [];
  let result = '';
  
  for (let char of expression) {
    // If operand, add to result
    if (/[a-zA-Z0-9]/.test(char)) {
      result += char;
    }
    // If '(', push to stack
    else if (char === '(') {
      stack.push(char);
    }
    // If ')', pop until '('
    else if (char === ')') {
      while (stack.length > 0 && stack[stack.length - 1] !== '(') {
        result += stack.pop();
      }
      stack.pop();  // Remove '('
    }
    // If operator
    else {
      while (
        stack.length > 0 &&
        stack[stack.length - 1] !== '(' &&
        precedence[stack[stack.length - 1]] >= precedence[char]
      ) {
        result += stack.pop();
      }
      stack.push(char);
    }
  }
  
  // Pop remaining operators
  while (stack.length > 0) {
    result += stack.pop();
  }
  
  return result;
}

console.log(infixToPostfix('a+b*c'));      // abc*+
console.log(infixToPostfix('(a+b)*c'));    // ab+c*

Real-World Applications of Stacks