📚 Pilas

init

Pruébalo: Apila fichas en la torre; sácalas una a una. Luego, abajo: alimenta cualquier cadena con paréntesis al juego de paréntesis — la pila es el analizador.

Por qué importa

Las pilas están por todas partes: llamadas a funciones, deshacer/rehacer, análisis de expresiones, algoritmos de retroceso (backtracking). Entender las pilas significa entender cómo se ejecutan los programas y cómo resolver problemas que requieren "recordar" y "deshacer".

La idea

Piensa en una pila de platos en una cafetería. Solo puedes añadir o quitar desde arriba. El último plato colocado es el primero en retirarse.

El último en entrar, el primero en salir (LIFO).

Esta simple restricción es increíblemente poderosa:

• Llamadas a funciones: Cuando la función A llama a B, el contexto de B va encima. Cuando B retorna, se desapila y A continúa.
• Deshacer: Cada acción se apila. Deshacer desapila la última acción.
• Emparejar paréntesis: Apila '(', desapila cuando ves ')'. Si está balanceado, la pila queda vacía al final.

Todas las operaciones son O(1) — solo tocas la cima.

Puntos clave

• Apilar (push), desapilar (pop) y mirar la cima (peek) son todas O(1)
• Orden LIFO — el último en entrar, el primero en salir
• Se usa en pilas de llamadas a funciones, evaluación de expresiones, retroceso
• Se puede implementar con un arreglo o una lista enlazada

Profundizando

La pila de llamadas es la razón por la que funcionan las funciones recursivas — las variables locales de cada llamada se apilan y se desapilan al retornar. El desbordamiento de pila (stack overflow) ocurre cuando la recursión se va demasiado profundo. Las pilas también son clave para convertir notación infija a postfija (algoritmo shunting-yard) y para evaluar expresiones postfijas en una sola pasada.

En la práctica

• La pila de llamadas de la CPU. Cada llamada a función que hace tu programa apila un marco de pila (dirección de retorno + locales + registros guardados). El puntero de pila del hardware es un registro en toda CPU moderna. Cuando ves un fallo con un rastreo de pila (stack trace), estás leyendo la pila de arriba abajo.
• Deshacer/rehacer del navegador. Dos pilas: una para acciones pasadas, otra para rehacer. Todo editor (Photoshop, VS Code, Figma) se construye sobre este patrón.
• DFS con pila explícita. La recursión es uso implícito de pila; en grafos profundos mantienes un arreglo de pila explícito para evitar reventar la pila de llamadas. Consulta la lección de grafos — su frontera DFS es una pila.
• Estado de recuperación en robótica. Apilar el estado "seguro" anterior antes de una acción arriesgada, y desapilarlo para volver a él si falla — la base de la recuperación al estilo try/except en los planificadores de movimiento.
• Compiladores. Todo analizador usa una pila: análisis shift/reduce, análisis de expresiones, seguimiento de ámbitos. Tu código se convierte en un AST mediante el reconocimiento, impulsado por pila, de la estructura anidada.

Detalles matemáticos

Complejidad temporal

Push: O(1)

Pop: O(1)

Peek: O(1)

Search: O(n)

Espacio

O(n) para n elementos

Implementación

Operaciones de pila

let mut stack = Vec::new();

stack.push(1);  // Apilar en la cima
stack.push(2);
stack.push(3);  // Pila: [1, 2, 3] (3 es la cima)

let top = stack.pop();  // Devuelve Some(3)
let peek = stack.last(); // Devuelve Some(&2)

Aplicaciones clásicas

• Verificación de paréntesis balanceados
• Pila de llamadas a funciones
• Funcionalidad de deshacer/rehacer
• Evaluación de expresiones
• Recorrido DFS

Práctica

Tres problemas clásicos de pilas — cada uno es una forma distinta de usar la disciplina LIFO:

• Pila con mínimo (Min Stack) — fácil · una pila auxiliar paralela rastrea el mínimo actual para que getMin sea O(1)
• Siguiente elemento mayor — medio · pila monótona de índices "en espera", O(n) amortizado
• Evaluar expresión postfija — medio · la pila como computadora; así es como toda calculadora RPN y toda VM de bytecode de la JVM evalúa expresiones

→ Explora todos los problemas de práctica