La pila y la cola

La pila (en inglés, stack) y la cola (queue) son las dos estructuras de datos más simples que existen después de la lista, y se distinguen por una sola regla. En la pila, el último elemento que entra es el primero que sale, como en un montón de platos: el que se pone encima es el que se retira primero. En la cola, el primero que entra es el primero que sale, como en la fila de una panadería. Las siglas inglesas LIFO (last in, first out) y FIFO (first in, first out) resumen las dos reglas, y se usan también fuera de la informática, en la contabilidad de almacenes, para decidir qué unidad se da por vendida cuando salen existencias.

La figura de esta página tiene las dos lado a lado. Cada botón «Meter» añade una ficha numerada y cada «Sacar» retira una: la pila devuelve siempre la última ficha que entró y la cola, la más antigua. Es todo lo que hacen. Ninguna de las dos permite mirar la tercera ficha, ni sacar una del medio, ni buscar un número; a cambio, meter y sacar cuestan lo mismo con tres fichas que con tres millones, porque las dos operaciones solo tocan un extremo.

La pila está en más sitios de los que parece. El botón de deshacer de cualquier programa guarda los cambios en una pila y retira el más reciente; el botón de atrás del navegador hace lo mismo con las páginas visitadas. Un editor de código comprueba que los paréntesis cierran bien metiendo cada paréntesis de apertura en una pila y sacando uno por cada cierre: si al final queda algo dentro, o si hay que sacar de una pila vacía, la expresión está mal. Y, sobre todo, la pila es lo que permite que una función llame a otra. Cada vez que un programa entra en una función, el ordenador apunta en la pila de llamadas (call stack) dónde tiene que volver cuando termine, junto con sus variables locales; la función que entró la última es la que termina primero, y por eso una pila es exactamente la estructura que hace falta. La recursividad es ese mecanismo llevado al límite, y el error que da un programa que se llama a sí mismo sin parar, el desbordamiento de pila (stack overflow), es tan corriente que da nombre al mayor foro de programadores del mundo. Cómo se ve esa pila mientras un programa corre lo enseña Del código al proceso.

La idea apareció varias veces. Alan Turing, en el informe de 1946 en el que proponía el ordenador ACE, describió dos operaciones que llamó «enterrar» y «desenterrar» (bury y unbury) para guardar la dirección de vuelta de una subrutina y recuperarla después, que es la pila de llamadas con otro nombre. Friedrich Bauer y Klaus Samelson, en Múnich, llegaron a ella por otro camino en 1955: traducir una fórmula como 3 + 4 × 5 a instrucciones de máquina exige dejar el «+» esperando hasta que el «×», que tiene prioridad, se resuelva, y lo que espera se guarda en lo que llamaron un sótano (Keller). Patentaron el principio en 1957 y lo publicaron en 1959 y 1960. Edsger Dijkstra lo usó en 1960 para implementar las funciones recursivas del lenguaje ALGOL 60, y desde entonces casi todos los lenguajes de programación funcionan sobre una pila.

La cola tiene menos leyenda y más oficio. Es la estructura de todo lo que debe atenderse por orden de llegada: los trabajos que esperan a la impresora, las teclas pulsadas antes de que el programa las lea, los mensajes entre dos programas que van a ritmos distintos, los paquetes que un router recibe más deprisa de lo que puede reenviar. El sistema operativo reparte el procesador entre programas con colas, y la búsqueda en anchura explora un laberinto con una. La virtud de la cola es la justicia: nadie espera para siempre, porque todo lo que entra acaba saliendo en su turno. Cuando hace falta que salga primero lo más urgente y no lo más antiguo, la cola se convierte en una cola de prioridad, que es lo que hace el montículo binario.

Las dos se construyen sobre cualquier lista. La pila es casi inmediata: un vector y un número que dice cuántas fichas hay; meter escribe en la siguiente posición libre y sacar lee la última ocupada. La cola tiene una trampa, porque sacar el primer elemento de un vector obliga a desplazar todos los demás una posición, y eso cuesta tanto como larga es la cola. La solución clásica es el búfer circular (ring buffer): dos índices, uno para la cabeza y otro para el final, que avanzan por un vector de tamaño fijo y vuelven al principio cuando llegan al borde, de manera que nada se mueve nunca de sitio. Es lo que hay dentro de casi todos los dispositivos que reciben datos a ráfagas. Con una lista enlazada las dos salen con la misma facilidad, a cambio de más memoria por elemento. Donald Knuth reunió pila, cola y la cola de dos extremos (deque) en el primer volumen de The Art of Computer Programming, en 1968, y las trató como variantes de una sola idea, la lista a la que solo se accede por los bordes.

Lo que enseñan las dos es que una limitación puede ser una virtud. Una pila no es una lista a la que le faltan operaciones, sino una lista que promete un orden, y esa promesa es lo que la hace útil: quien usa una pila sabe que lo que saca es lo último que metió sin tener que comprobarlo. Elegir entre una pila y una cola es elegir a qué se atiende primero, si a lo más reciente o a lo más antiguo, y esa decisión, tomada en una línea, cambia el comportamiento entero de un programa.

La lista enlazada – La recursividad – El montículo binario – La búsqueda en anchura y en profundidad – Del código al proceso