Pilas y colas: LIFO y FIFO

Una pila es una estructura de datos en la que el último elemento que entra es el primero que sale; una cola es lo contrario. Con ellas se resuelven problemas muy comunes, como deshacer cambios en un editor o ordenar una cola de impresión.

Cuando pulsas Ctrl+Z, el editor deshace tu última acción, no la primera. Eso es una pila.

Imagina una pila de platos. Pones un plato encima y quitas el de arriba. El de abajo no se toca hasta el final.

Una pila tiene dos operaciones: apilar (push) pone un elemento en la cima y desapilar (pop) quita la cima y la devuelve. El orden es LIFO: last in, first out.

# Una pila de acciones para deshacer en un editor de texto.
undo = []
undo.append("escribir hola")
undo.append("borrar una palabra")
undo.append("poner negrita")
print("Deshacer:", undo.pop())
print("Deshacer:", undo.pop())
print("Quedan:", undo)
# Añade otra acción y comprueba cuál sale primero.

python3 -c "s = []; s.append(1); s.append(2); print(s.pop(), s.pop())"

printf 'a\nb\nc\n' | tac

En la cola de una cafetería, el primero que llegó es el primero al que atienden. Se entra por detrás y se sale por delante.

Las operaciones son encolar (enqueue), que añade al final, y desencolar (dequeue), que quita el primero. El orden es FIFO: first in, first out. Una cola de impresión funciona así.

# Una cola de impresión en una biblioteca.
queue = ["apuntes.pdf", "examen.pdf", "cartel.pdf"]
queue.append("factura.pdf")  # entra por detrás
first = queue.pop(0)  # sale por delante
print("Se imprime:", first)
print("Esperan:", queue)
# Cambia pop(0) por pop() y mira qué documento sale.

python3 -c "from collections import deque; q = deque(); q.append('a'); q.append('b'); print(q.popleft(), q.popleft())"

En la lección anterior viste que quitar el primer elemento de una lista obliga a desplazar todos los demás. Por eso pop(0) es caro en una cola grande.

La clase deque de Python está pensada para sacar de los dos extremos sin desplazar nada. Para colas largas, es la herramienta adecuada.

Un editor de código marca un error si un paréntesis queda sin cerrar. La idea: cada apertura se apila, y cada cierre debe encontrar su apertura en la cima.

Si la cima no encaja, o la pila está vacía, los paréntesis están mal. Si al terminar queda algo en la pila, falta cerrar.

Una calculadora puede evaluar 3 4 + con una pila. Apila el 3 y el 4. Al llegar al +, desapila dos números, los suma y apila el resultado.

Prueba a escribirlo para 5 1 2 + 4 * +. Piensa en cuántos números hay en la pila en cada momento.