Pilas y colas
Seguí leyendo
Enterate del próximo post
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Un mail cuando publico algo nuevo. Sin spam y te podés dar de baja cuando quieras.
Una lista permite leer y cambiar cualquier posición en cualquier momento: la tercera, la primera, la última, sin ningún orden fijo para acceder a ellas. Hay problemas, sin embargo, en los que no hace falta esa libertad, porque el orden de entrada y salida es justamente la regla que hay que respetar. Una pila de platos recién lavados solo se puede tocar por arriba: el plato que se dejó último es el primero que vuelve a usarse, y no hay forma de sacar el de abajo sin levantar antes todos los que quedaron encima. La fila de un banco funciona al revés: quien llegó primero es el primero en ser atendido, sin importar cuánto crezca la fila por el otro extremo mientras espera.
Esas dos reglas de acceso tienen nombre propio. Una pila es una colección en la que solo se puede agregar y quitar valores por un mismo extremo, llamado el tope. El último valor agregado es siempre el primero en salir, una regla conocida como LIFO ("el último en entrar es el primero en salir"). Una cola es una colección en la que se agrega por un extremo y se quita por el otro. El primer valor agregado es siempre el primero en salir, una regla conocida como FIFO ("el primero en entrar es el primero en salir").
Ninguna de las dos necesita una notación nueva para escribirse: una pila y una cola son listas -los mismos corchetes ya vistos, [] para la vacía- a las que se les permite un conjunto mucho más chico de operaciones. La diferencia entre las tres no está en cómo se escriben, sino en qué se les permite hacer.
Sobre una pila:
apilar valor en pila.desapilar pila.el tope de pila.la cantidad de elementos de pila (la misma operación ya usada con listas).Sobre una cola:
encolar valor en cola.desencolar cola.el primero de cola.la cantidad de elementos de cola.Restringir el acceso no es una limitación: es una garantía. Un algoritmo que solo apila y desapila no puede, ni por error, leer un valor del medio fuera de orden; uno que solo encola y desencola no puede saltear a nadie en la fila. Esa garantía es justamente lo que hace que una pila resuelva bien un historial de navegación o deshacer la última acción, y que una cola resuelva bien una fila de espera o una impresora que atiende los trabajos en el orden exacto en que llegaron.
El primer ejemplo guarda el historial de páginas visitadas en una pila, para poder volver a la anterior:
algoritmo pagina_anterior(historial):
desapilar historial
devolver el tope de historialCon historial en ["inicio", "productos", "producto-42"]: desapilar quita "producto-42", la última página visitada, y deja historial en ["inicio", "productos"]. El tope pasa a ser "productos", la página anterior a la que se estaba viendo. Volver atrás una vez más -con el mismo algoritmo, sin ningún cambio- dejaría el tope en "inicio".
El segundo ejemplo atiende el siguiente turno de una fila de espera, con una cola:
algoritmo siguiente_turno(espera):
devolver desencolar esperaCon espera en ["Turno 15", "Turno 16", "Turno 17"]: desencolar quita y devuelve "Turno 15", el primero que se sumó a la fila, y deja espera en ["Turno 16", "Turno 17"]. No importa que "Turno 17" haya llegado después: la cola siempre libera por el extremo donde entró el primero, nunca por el otro.
Dada una lista de números, escribir un algoritmo que devuelva una lista nueva con los mismos números en el orden invertido, usando exclusivamente una pila.
Pista: apilar todos los valores de la lista original, en el orden en que aparecen, y después desapilarlos uno por uno hasta vaciarla. El orden en que salen de una pila ya es, por sí solo, el opuesto al orden en que entraron.
algoritmo invertir_orden(entrada):
asignar una lista vacía a pila
repetir contador desde 1 hasta la cantidad de elementos de entrada:
apilar el elemento en la posición contador de entrada en pila
asignar una lista vacía a salida
mientras la cantidad de elementos de pila es mayor a 0:
asignar desapilar pila a valor
agregar valor al final de salida
devolver salidaCon entrada en [4, 9, 15, 2, 7]: el primer bucle apila los cinco valores en ese mismo orden, así que pila queda en [4, 9, 15, 2, 7] con el 7 arriba de todo, el último en entrar. El segundo bucle la vacía desapilando de a uno: sale primero el 7, después el 2, el 15, el 9 y por último el 4, y cada uno se agrega al final de salida en ese orden. El resultado es [7, 2, 15, 9, 4], exactamente entrada invertida, sin haber leído ni escrito ninguna posición de la lista original más que para recorrerla de punta a punta.
Una veterinaria atiende sin turno previo: los animales que llegan esperan en una fila, y se atiende primero al que llegó primero. Al mismo tiempo, en el mostrador se necesita poder consultar rápido cuál fue el último animal atendido, sin revisar toda la planilla del día.
Pista: la fila de espera pide una estructura que siempre libere por donde entró el primero. Saber quién fue el último atendido pide una estructura que siempre libere por donde entró el más reciente. Son dos preguntas distintas sobre los mismos datos, y ninguna de las dos estructuras podría responder sola a las dos.
algoritmo atender_siguiente(espera, historial):
asignar desencolar espera a siguiente
apilar siguiente en historial
devolver siguienteCon espera en ["Rocky", "Mia", "Toby"] e historial en una lista vacía: la primera llamada desencola "Rocky", el primero que llegó, y lo apila en historial, que pasa a ["Rocky"]; espera queda en ["Mia", "Toby"]. La segunda llamada desencola "Mia" -la fila sigue liberando por el mismo extremo, sin importar que "Toby" esté esperando desde antes que ella- y la apila en historial, que pasa a ["Rocky", "Mia"]. El tope de historial ahora es "Mia", el último atendido, aunque "Rocky" haya sido el primero: la cola contesta quién sigue en el orden de llegada, y la pila contesta quién fue el más reciente, y ninguna de las dos preguntas se puede responder con la otra estructura.
Una lista permite acceder a cualquier posición en cualquier momento. Una pila y una cola renuncian a esa libertad a propósito: la primera libera siempre por donde entró el último valor, la segunda siempre por donde entró el primero. Esa restricción no es una limitación, es una garantía sobre el orden exacto en que los datos van a salir.
El próximo post cierra el bloque con un repaso: situaciones donde hace falta reconocer, sin que ningún título lo diga, cuál de las cinco estructuras ya vistas -lista, diccionario, conjunto, pila o cola- conviene usar para el problema que toca resolver.