Pilas (stacks)

Qué cubre este capítulo

Un stack es la primera estructura de este libro que se define por lo que no te deja hacer. Es una colección donde solo puedes tocar un extremo — agregas por arriba, sacas por arriba, y no puedes alcanzar nada de lo que está debajo. Suena a limitación, y lo es, a propósito: la restricción tiene exactamente la forma de todo problema que se tiene que deshacer en orden inverso. Este capítulo construye un stack encima del array dinámico del capítulo pasado, y luego lo usa para el problema para el que los stacks prácticamente se inventaron — verificar que los paréntesis y corchetes estén balanceados.

Un poco de historia

El stack es una de las estructuras de control más viejas de la computación. Alan Turing describió el mecanismo en 1946 para manejar los retornos de subrutinas — sus palabras para push y pop eran "bury" y "unbury" (enterrar y desenterrar), que es una imagen mental mejor que los nombres modernos. La estructura fue formalizada y patentada como principio en 1957 por Friedrich Bauer y Klaus Samelson, que la llamaron el Kellerprinzip (el "principio del sótano") y la usaron para evaluar expresiones aritméticas con paréntesis anidados — el problema exacto de la animación de este capítulo. Su evaluación de expresiones basada en stack sigue siendo la forma en que compiladores y calculadoras parsean matemáticas hoy.

La intuición

Piensa en una pila de platos. Agregas un plato encima; tomas un plato de encima; nunca jalas uno de en medio. El último plato que pusiste es el primero que levantas — último en entrar, primero en salir.

Esa única regla es lo que hace útil al stack. Cada vez que estás a la mitad de una cosa y tienes que pausarla por algo más urgente, terminando lo más nuevo primero y regresando después a lo viejo, estás describiendo un stack. Una función que llama a otra función, que llama a otra — cada una tiene que terminar y retornar antes de que la que la llamó continúe. Paréntesis que abren y que cada uno tiene que cerrarse antes que los que lo rodean. Un historial de undo donde Ctrl-Z revierte primero tu acción más reciente. Todos son stacks, los haya nombrado alguien o no.

Complejidad: cómo escala

Un stack es barato porque cada operación ocurre en un solo extremo conocido. Construido sobre un array dinámico, push es un append y pop es un quitar-del-final — ambos $O(1)$ (amortizado para push, por el resize ocasional del array que vimos en el capítulo pasado). Peek es una sola lectura, $O(1)$. Nunca hay búsqueda ni desplazamiento de elementos. El espacio es $O(n)$ para n elementos.

Aquí no hay recurrencia que desenrollar — lo interesante es que el costo no crece. La gráfica de abajo corre una secuencia larga de operaciones push/pop y la cronometra; la línea es recta, lo que significa que el costo por operación es plano sin importar qué tan profundo se ponga el stack:

Para qué sirve, para qué no

Un stack es la herramienta correcta siempre que tu patrón de acceso sea "lo más reciente primero" y nunca necesites pasar más allá del tope. Como cada operación es un toque garantizado de $O(1)$ en un extremo, es de lo más rápido que puede ser una estructura de datos, y la disciplina LIFO hace que el código que lo usa sea fácil de razonar — siempre sabes exactamente qué elemento sale a continuación.

Lo que no es, es un contenedor general. No puedes pedir el elemento más viejo, ni el tercero desde arriba, ni buscar en él, sin violar la restricción misma que lo hace un stack. Si te descubres queriendo esas cosas, ya se te quedó chico el stack y quieres otra estructura — una queue para lo más viejo primero, un array para indexar. Y las dos operaciones que pueden fallar — hacer pop o peek de un stack vacío — van a fallar, así que el código que usa un stack tiene que verificar.

Los datos, o las entradas

Dos tipos de entrada mueven este capítulo. El face-off le da al stack una secuencia larga, generada aleatoriamente, de operaciones push y pop válidas — válidas en el sentido de que nunca hace pop por debajo de vacío — para poder cronometrarlo a escala. La animación usa una sola cadena corta de brackets, ([{}]), porque ahí el punto no es la velocidad, es ver el stack crecer y encogerse mientras el escaneo empareja cada par.

Constrúyelo, una función a la vez

Push agrega al tope, que sobre un array dinámico como almacenamiento es simplemente un append:

def push(self, value):
    """O(1) amortized: add to the top (the end of the backing array)."""
    self._items.append(value)

Pop quita y regresa el tope, y se niega a correr sobre un stack vacío — no hay nada que devolver:

def pop(self):
    """O(1): remove and return the top. Errors on an empty stack — there's
    nothing to take."""
    if not self._items:
        raise IndexError("pop from empty stack")
    return self._items.pop()

Peek es la misma mirada al tope pero sin tomarlo, para cuando necesitas inspeccionar antes de decidir:

def peek(self):
    """O(1): read the top without removing it."""
    if not self._items:
        raise IndexError("peek at empty stack")
    return self._items[-1]

Con esas tres, el verificador de brackets se escribe solo. Haz push de cada bracket que abre; ante un bracket que cierra, el tope del stack tiene que ser su pareja, así que hazle pop. Si el tope es el bracket equivocado, o el stack está vacío cuando llega un cierre, la cadena está desbalanceada. Está balanceada solo si cada cierre encontró pareja y el stack quedó vacío al final:

_PARTNER = {")": "(", "]": "[", "}": "{"}

def is_balanced(text, probe=None):
    """Are the brackets in `text` correctly nested and matched?

    The canonical stack problem. Push every opening bracket; on a closing
    bracket the top of the stack must be its partner, so pop it. The string is
    balanced iff every close finds its match and the stack is empty at the end —
    an unmatched open left on the stack means something never closed. Each step
    is appended to `probe` (when given) so the scan can be animated.
    """
    stack = Stack()
    for ch in text:
        if ch in "([{":
            stack.push(ch)
            action = f"'{ch}' opens — push it"
        elif ch in ")]}":
            if stack.is_empty() or stack.peek() != _PARTNER[ch]:
                if probe is not None:
                    probe.append({"stack": stack.snapshot(), "action": f"'{ch}' has no match — not balanced"})
                return False
            stack.pop()
            action = f"'{ch}' closes the top — pop it"
        else:
            action = f"'{ch}' is not a bracket — skip"
        if probe is not None:
            probe.append({"stack": stack.snapshot(), "action": action})
    return stack.is_empty()

Míralo trabajar

Aquí está el verificador corriendo sobre ([{}]). La fila de arriba es la cadena de entrada con un cursor; la fila de abajo es el stack. Avanza paso a paso: cada bracket que abre recibe un push (el stack crece), y cada bracket que cierra hace pop del que abre correspondiente en el tope (el stack se encoge). La celda verde es el tope del stack — el que un bracket de cierre tiene que emparejar. Para el último carácter el stack está vacío, que es justo lo que significa "balanceado". Tomó seis pasos y el stack nunca pasó de tres de profundidad:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña from-scratch es nuestro Stack más el verificador de brackets. La pestaña de librería es lo que escribirías en la vida real: una list de Python ya es un stack (append es push, pop() es pop), y collections.deque es lo mismo cuando quieres hacer la intención explícita.

"""A stack — last in, first out — built on a dynamic array, plus the classic
application that shows why stacks exist: matching nested brackets.

A stack only lets you touch one end. That restriction is the point: it's exactly
the right shape for anything that has to unwind in reverse order — undo history,
a function-call chain, the open brackets waiting to be closed.
"""


class Stack:
    def __init__(self):
        self._items = []          # a Python list used as the backing array

    # region: push
    def push(self, value):
        """O(1) amortized: add to the top (the end of the backing array)."""
        self._items.append(value)
    # endregion

    # region: pop
    def pop(self):
        """O(1): remove and return the top. Errors on an empty stack — there's
        nothing to take."""
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()
    # endregion

    # region: peek
    def peek(self):
        """O(1): read the top without removing it."""
        if not self._items:
            raise IndexError("peek at empty stack")
        return self._items[-1]
    # endregion

    def is_empty(self):
        return not self._items

    def __len__(self):
        return len(self._items)

    def snapshot(self):
        """Bottom-to-top copy of the contents — used to record the animation."""
        return list(self._items)


# region: balanced
_PARTNER = {")": "(", "]": "[", "}": "{"}

def is_balanced(text, probe=None):
    """Are the brackets in `text` correctly nested and matched?

    The canonical stack problem. Push every opening bracket; on a closing
    bracket the top of the stack must be its partner, so pop it. The string is
    balanced iff every close finds its match and the stack is empty at the end —
    an unmatched open left on the stack means something never closed. Each step
    is appended to `probe` (when given) so the scan can be animated.
    """
    stack = Stack()
    for ch in text:
        if ch in "([{":
            stack.push(ch)
            action = f"'{ch}' opens — push it"
        elif ch in ")]}":
            if stack.is_empty() or stack.peek() != _PARTNER[ch]:
                if probe is not None:
                    probe.append({"stack": stack.snapshot(), "action": f"'{ch}' has no match — not balanced"})
                return False
            stack.pop()
            action = f"'{ch}' closes the top — pop it"
        else:
            action = f"'{ch}' is not a bracket — skip"
        if probe is not None:
            probe.append({"stack": stack.snapshot(), "action": action})
    return stack.is_empty()
# endregion

"""A Python list is already a stack: `append` is push, `pop()` is pop, both O(1)
amortized at the end. When you want to make the intent explicit, `collections.deque`
is the other common choice — same O(1) at the end, and it can't be indexed into by
accident the way a list can.

So the face-off is our Stack against the two structures every Python programmer
actually reaches for, driven by the same sequence of push/pop operations.
"""
from collections import deque


# region: list_stack
def run_ops_list(ops):
    """Drive ('push', x) / ('pop',) operations on a plain list used as a stack."""
    stack = []
    popped = []
    for op in ops:
        if op[0] == "push":
            stack.append(op[1])
        else:
            popped.append(stack.pop())
    return popped
# endregion


# region: deque_stack
def run_ops_deque(ops):
    """Same operations on a deque — append/pop work on the right end."""
    stack = deque()
    popped = []
    for op in ops:
        if op[0] == "push":
            stack.append(op[1])
        else:
            popped.append(stack.pop())
    return popped
# endregion

Desde cero vs librería

Misma estructura, mismas operaciones O(1), así que el face-off es puramente sobre la constante. La gráfica corre la secuencia idéntica de push/pop a través de nuestro Stack, una list y un deque:

Las tres líneas son rectas — cada implementación es O(1) por operación, así que el total es lineal en el número de operaciones. A 400000 operaciones nuestro Stack tomó cerca de 14.4 ms contra los 8.3 ms de la list, más o menos 1.7 veces más lento. Es una brecha pequeña, y esa es toda la historia: nuestro Stack es un wrapper delgado de Python cuyo push llama a list.append por debajo, así que solo puede quedar un factor constante detrás de la list cruda — la llamada extra al método. Por eso nadie escribe una clase Stack en Python: la list integrada ya es uno. La razón para construirlo es ver que "stack" es un conjunto de promesas sobre el orden de acceso, no un nuevo tipo de almacenamiento.

Dónde te lo vas a encontrar de verdad

Los stacks están por todos lados una vez que conoces la forma. Cada funcionalidad de undo/redo son dos stacks. Cada compilador y calculadora usa uno para evaluar expresiones y emparejar brackets — el código exacto de arriba, a escala. El botón de atrás de tu navegador es un stack de páginas. La búsqueda en profundidad (DFS), en los capítulos de grafos, es la búsqueda en anchura con la queue cambiada por un stack. Y el call stack corre cada programa que has escrito en tu vida. Cuando veas "lo más reciente primero", o "deshacer en reversa", o "anidamiento balanceado", agarra un stack.

Conclusiones

Un stack es una colección restringida a un extremo: push, pop y peek, todos $O(1)$, todos LIFO. Esa restricción no es una debilidad — es una garantía, y la garantía es exactamente lo que necesitan los problemas de "atiende lo más nuevo primero, luego deshaz el camino". Constrúyelo sobre un array dinámico y hereda el append O(1) amortizado; en Python la list ya te da todo eso.

Ten presente la forma, porque los próximos dos capítulos son su imagen en el espejo. Una queue es la misma idea con el orden opuesto — primero en entrar, primero en salir, para cuando necesitas el elemento más viejo a continuación — y un stack más una queue cubren la mayor parte del trabajo de "procesar cosas en un orden específico" que vas a hacer en tu vida. Después de eso, el stack regresa como el motor detrás de la recursión y la búsqueda en profundidad.