Pilas (Stacks): LIFO y la estructura detrás de la recursión

Cuando usas Ctrl+Z para deshacer, cuando el navegador te deja volver a la página anterior, cuando evalúas una expresión matemática con paréntesis anidados, o cuando una función se llama a sí misma —como vimos en la serie anterior—, detrás hay una pila. Es una de las estructuras de datos más simples y más omnipresentes de la programación.

Este es el tercer artículo de Por dentro de las estructuras. Una pila se puede implementar sobre un array o sobre una lista enlazada, y la comparamos con la cola en el siguiente artículo.

Explicación conceptual

Una pila es una colección que sigue la disciplina LIFO (Last In, First Out): el último elemento que se insertó es el primero en salir. Piensa en una pila de platos en una cocina: solo puedes agregar o quitar desde arriba.

Las operaciones clásicas son:

• push(x): agregar un elemento al tope.

• pop(): quitar y devolver el elemento del tope.

• peek() (o top()): ver el elemento del tope sin quitarlo.

• isEmpty(): saber si está vacía.

• size(): cuántos elementos tiene.

No hay acceso al medio. No hay búsqueda por índice. Es un contrato muy restringido, y precisamente esa restricción es lo que la hace útil: cuando tu problema encaja con LIFO, la pila te ahorra código.

Ejemplo gráfico

La imagen destacada muestra una pila vertical de rectángulos, con el tope marcado y una flecha señalando las operaciones push / pop. Todo entra y sale solo por ese extremo.

Implementación en PHP

PHP ofrece varias formas. La más simple: usar un array y las funciones nativas array_push y array_pop.

// Pila con array nativo
$pila = [];
array_push($pila, 10);
array_push($pila, 20);
array_push($pila, 30);
// $pila = [10, 20, 30]

$top = array_pop($pila); // 30
// $pila = [10, 20]

Más limpio con una clase propia:

class Pila {
    private array $datos = [];

    public function push(mixed $v): void {
        $this->datos[] = $v;
    }

    public function pop(): mixed {
        if (empty($this->datos)) {
            throw new RuntimeException("Pila vacía");
        }
        return array_pop($this->datos);
    }

    public function peek(): mixed {
        if (empty($this->datos)) return null;
        return end($this->datos);
    }

    public function isEmpty(): bool {
        return empty($this->datos);
    }

    public function size(): int {
        return count($this->datos);
    }
}

Y también PHP trae SplStack en la SPL:

$pila = new SplStack();
$pila->push(10);
$pila->push(20);
$top = $pila->top(); // 20 (sin quitar)
$pila->pop();

Implementación en Java

Java tiene java.util.Stack, pero está considerado legacy. La recomendación oficial es usar ArrayDeque como pila, porque es más rápido y su API es consistente.

// Usando ArrayDeque (recomendado)
Deque<Integer> pila = new ArrayDeque<>();
pila.push(10);
pila.push(20);
pila.push(30);
int top = pila.pop(); // 30
int visible = pila.peek(); // 20

La clase legacy:

// No recomendado, pero existe
Stack<Integer> pila = new Stack<>();
pila.push(10);
pila.pop();

Implementación manual con array redimensionable:

public class Pila<T> {
    private Object[] datos;
    private int tope = 0;

    public Pila() { datos = new Object[16]; }

    public void push(T v) {
        if (tope == datos.length) {
            datos = Arrays.copyOf(datos, datos.length * 2);
        }
        datos[tope++] = v;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (tope == 0) throw new EmptyStackException();
        T v = (T) datos[--tope];
        datos[tope] = null; // importante para GC
        return v;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (tope == 0) throw new EmptyStackException();
        return (T) datos[tope - 1];
    }

    public boolean isEmpty() { return tope == 0; }
    public int size() { return tope; }
}

O con lista enlazada (cada nodo es un elemento de la pila):

public class PilaEnlazada<T> {
    private static class Nodo<T> {
        T valor;
        Nodo<T> siguiente;
        Nodo(T v, Nodo<T> s) { valor = v; siguiente = s; }
    }

    private Nodo<T> tope = null;
    private int size = 0;

    public void push(T v) {
        tope = new Nodo<>(v, tope);
        size++;
    }

    public T pop() {
        if (tope == null) throw new NoSuchElementException();
        T v = tope.valor;
        tope = tope.siguiente;
        size--;
        return v;
    }

    public T peek() {
        if (tope == null) throw new NoSuchElementException();
        return tope.valor;
    }

    public boolean isEmpty() { return tope == null; }
    public int size() { return size; }
}

Operaciones básicas

Inserción (push)

Agregar al tope. Con array: O(1) amortizado (hay que redimensionar ocasionalmente). Con lista enlazada: O(1) estricto.

Búsqueda

Las pilas no están diseñadas para búsqueda. Si quieres encontrar un elemento, tienes que hacer pop hasta encontrarlo y luego push de los que sacaste, lo que es O(n) y destruye la invariante. Si tu caso requiere búsqueda, la pila no es la estructura correcta.

Eliminación (pop)

Quitar del tope. O(1) en ambas implementaciones.

Complejidad (Big-O)

OperaciónPila sobre arrayPila sobre lista enlazadapushO(1) amortizadoO(1)popO(1)O(1)peekO(1)O(1)búsquedaO(n) destruyendono aplicaespacioO(n)O(n) + overhead de punteros

Ventajas y desventajas

Ventajas:

• Operaciones O(1) consistentes.

• Modelo conceptual simplísimo: se programa y se lee sin esfuerzo cuando el problema encaja.

• Poco consumo de memoria (sobre array).

Desventajas:

• Solo acceso al tope. Si tu problema requiere inspeccionar el medio, la pila te estorba.

• La versión sobre lista enlazada consume memoria extra por los punteros.

Casos de uso reales

• Deshacer/Rehacer en editores de texto. Cada acción del usuario se apila; Ctrl+Z hace pop.

• Historial de navegación: cada página visitada es un push; el botón "atrás" hace pop.

• Evaluación de expresiones matemáticas y conversión entre notaciones (infix, postfix, prefix).

• Balance de paréntesis, corchetes y llaves: un parser recorre el texto, hace push al abrir y pop al cerrar; si al final la pila queda vacía, los delimitadores están balanceados.

• DFS (Depth-First Search) en grafos y árboles (ver artículo DFS de la Serie 3): la versión iterativa usa una pila explícita.

• Call stack de los propios programas: cada función en ejecución es un frame en una pila (ver Stack vs Heap).

• Backtracking en resolución de puzzles (sudoku, laberintos): cuando un camino no funciona, haces pop y pruebas otro.

Ejemplo clásico: verificar paréntesis balanceados

public boolean balanceados(String s) {
    Deque<Character> pila = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            pila.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (pila.isEmpty()) return false;
            char abre = pila.pop();
            if (!coincide(abre, c)) return false;
        }
    }
    return pila.isEmpty();
}

private boolean coincide(char a, char c) {
    return (a == '(' && c == ')') ||
           (a == '[' && c == ']') ||
           (a == '{' && c == '}');
}

Recorrer una vez, usar O(profundidad) de espacio en la pila. Más claro y más rápido que cualquier alternativa.

Cómo se recorre

Técnicamente, una pila no está hecha para recorrerse como un array. Pero si necesitas hacerlo (por ejemplo, para imprimir el contenido sin consumirla), ambas clases de Java y PHP exponen un Iterator:

Deque<Integer> pila = new ArrayDeque<>();
pila.push(1); pila.push(2); pila.push(3);

for (int v : pila) {
    System.out.println(v); // 3, 2, 1 (del tope hacia la base)
}

Nota que el recorrido es del tope hacia la base, no al revés.

Si quieres procesar cada elemento y liberar la pila al mismo tiempo:

while (!pila.isEmpty()) {
    procesar(pila.pop());
}

Cómo se vería en memoria

Si implementas la pila sobre un array, todo vive contiguo en el heap: un único bloque + un índice tope que indica cuántos elementos hay. La localidad de caché es excelente.

Si la implementas sobre lista enlazada, cada nodo es un objeto independiente en el heap, unido al anterior por un puntero. Misma geometría que vimos en el artículo de listas enlazadas.

Curioso: el call stack del programa es la pila de frames de funciones. Cada push y pop están implementados en hardware, con una instrucción del procesador que mueve el stack pointer. Es literalmente la pila más usada de todo tu software.

Errores comunes

1. Pop sobre pila vacía

EmptyStackException (en Stack legacy) o NoSuchElementException (en ArrayDeque.pop()). Siempre verifica isEmpty() antes o usa pollFirst() que devuelve null en vez de tirar excepción.

// Mejor
while (!pila.isEmpty()) {
    procesar(pila.pop());
}

// O con poll-style
Integer v;
while ((v = pila.pollFirst()) != null) {
    procesar(v);
}

2. Confundir Stack con Queue

LIFO (Stack) y FIFO (Queue, que veremos en el siguiente artículo) son opuestos. Usar uno cuando necesitabas el otro produce resultados al revés. Un test mental rápido: "¿el último que entró es el primero que sale?" → Stack. "¿el primero que entró es el primero que sale?" → Queue.

3. Usar la clase legacy Stack en Java

java.util.Stack extiende Vector, que es sincronizada (cada método tiene un lock innecesario en código single-thread). Prefiere ArrayDeque como pila. Su API es push/pop/peek igual que Stack, pero es más rápido y más moderno.

4. No limpiar la referencia al hacer pop (en implementaciones manuales)

Si tu array interno sigue apuntando a objetos que ya "sacaste", el GC no los puede liberar:

// Mal: el array sigue manteniendo la referencia
public T pop() {
    return (T) datos[--tope];
}

// Bien: liberamos la referencia para el GC
public T pop() {
    T v = (T) datos[--tope];
    datos[tope] = null;
    return v;
}

5. Stack overflow por recursión mal acotada

No es un error de esta estructura, sino del call stack del runtime. Como vimos en el artículo de recursión, cada llamada apila un frame, y el stack del runtime es limitado. Si tu problema requiere profundidad mayor que un par de miles, reemplaza la recursión por iteración con una pila explícita en heap.

Resumen

La pila es una colección LIFO con operaciones push, pop y peek, todas en O(1). Se puede implementar sobre array o sobre lista enlazada; en Java, la clase recomendada es ArrayDeque. Se usa donde el patrón "lo último que entró es lo primero que sale" aparece de forma natural: undo, historial, parsing de paréntesis, DFS, backtracking.

Su restricción —no hay acceso al medio— es parte de su valor: cuando el problema encaja, el código sale en pocas líneas y la complejidad es intuitiva.

En el siguiente artículo vemos la contraparte: la cola, con disciplina FIFO, y sus variantes más comunes.