Pilas

¿Qué es una pila?

Una pila es una estructura de datos lineal que sigue el principio Last In, First Out (LIFO). Piensa en una pila de platos: solo puedes agregar o quitar desde arriba. El último plato que colocas es el primero que sacarás.

Las pilas son fundamentales en ciencias de la computación y se usan ampliamente en algoritmos, gestión de memoria y evaluación de expresiones.

Operaciones de la pila

Implementación de pila usando 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

Implementación de pila usando lista enlazada

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;
  }
}

Problemas comunes con pilas

1. Paréntesis válidos

Comprueba si una cadena tiene paréntesis correctamente balanceados.

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. Invertir una cadena

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. Evaluar expresión postfija

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. Siguiente elemento mayor

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. Pila mínima (mínimo en 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. Convertir infija a postfija

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*

Aplicaciones reales de las pilas