Pila y cola explicadas: LIFO vs FIFO con ejemplos en Python

Qué problema resuelven las pilas y las colas

Muchos programas necesitan recordar elementos y procesarlos después en un orden fijo. Una pila te da primero el elemento más reciente, lo que encaja con el trabajo anidado: llamadas a funciones, historial de deshacer, emparejar paréntesis y búsqueda en profundidad. Una cola te da primero el elemento más antiguo, lo que encaja con una espera justa: trabajos de impresión, planificadores de tareas, colas de mensajes y búsqueda en anchura.

Ambas son tipos de datos abstractos: se definen por sus operaciones, no por cómo se almacenan. Puedes construir cualquiera de las dos sobre un arreglo o una lista enlazada.

Operaciones y nombres

Ejemplo resuelto: push y pop paso a paso

Mete 1, 2 y 3 en ambas estructuras y luego quita dos elementos.

Implementación en Python

Una list de Python ya es una buena pila: append y pop() operan sobre el final de la lista en O(1) amortizado. Para una cola, no uses list.pop(0), porque desplaza todos los elementos restantes y cuesta O(n). Usa collections.deque, que es O(1) en ambos extremos.

from collections import deque
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop(), stack[-1])   # 3 2
queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft(), queue[0])  # a b
print(len(stack), len(queue))     # 2 2

Si quieres métodos con nombre y errores claros, envuelve las estructuras integradas en una clase pequeña:

from collections import deque
class Queue:
    def __init__(self):
        self._items = deque()
    def enqueue(self, item):
        self._items.append(item)
    def dequeue(self):
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()
    def __len__(self):
        return len(self._items)
q = Queue()
q.enqueue("job1")
q.enqueue("job2")
print(q.dequeue(), len(q))  # job1 1

Problema clásico de pilas: paréntesis balanceados

Para comprobar que cada paréntesis se cierra en el orden correcto, apila cada símbolo de apertura. Cuando veas uno de cierre, la cima de la pila debe ser su pareja de apertura.

def is_balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(is_balanced("f(a[1], {b: 2})"))  # True
print(is_balanced("(]"))               # False
print(is_balanced("(("))               # False

La misma idea sirve para evaluar expresiones en notación polaca inversa, convertir una recursión en un bucle y dirigir la búsqueda en profundidad: sustituye la pila de llamadas por tu propia lista.

Problema clásico de colas: búsqueda en anchura

La búsqueda en anchura (BFS) recorre un grafo nivel por nivel. Una cola lo logra: los nodos descubiertos primero se procesan primero.

from collections import deque
def bfs_order(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs_order(graph, "A"))  # ['A', 'B', 'C', 'D']

Complejidad temporal y espacial

Amortizado significa que un append ocasional redimensiona el arreglo subyacente y cuesta O(n), pero promediado sobre muchas operaciones cada una es O(1).

Variantes y errores comunes

• Deque (cola de doble extremo): añade y quita por ambos extremos. collections.deque lo es y puede actuar como pila y como cola.
• Cola de prioridad: saca primero el elemento menor (o mayor), no el más antiguo. Usa heapq; consulta la página del montículo binario.
• Búfer circular: una cola de tamaño fijo guardada en un arreglo con índices que dan la vuelta. deque(maxlen=n) descarta el elemento más antiguo cuando se llena.
• Colas seguras para hilos: queue.Queue para hilos y asyncio.Queue para corrutinas se bloquean mientras esperan elementos.
• Una cola construida con dos pilas: apila en la pila de entrada y, cuando la de salida está vacía, pasa todo a ella. Cada elemento se mueve una sola vez, así que las operaciones son O(1) amortizado.