Pilas y colas: LIFO frente a FIFO

Al finalizar este tema

Podrás explicar los principios de las pilas y las colas, y conocerás sus respectivos usos.

Pila (Stack): apilar platos

Una pila (Stack) es una estructura en la que solo se insertan y eliminan elementos por la parte superior.

┌─────┐
  push → │  30 │ ← pop (saca primero lo que se insertó más recientemente)
         ├─────┤
         │  20 │
         ├─────┤
         │  10 │
         └─────┘

Es como apilar platos en un restaurante: el último plato que se apila es el primero que se retira. Esto se conoce como LIFO (Last In, First Out), o "el último en entrar es el primero en salir".

stack = []

# push — apilar encima
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)        # [10, 20, 30]

# pop — extraer desde arriba
top = stack.pop()
print(top)          # 30 (el último insertado)
print(stack)        # [10, 20]

# peek — verificar la parte superior sin extraer
print(stack[-1])    # 20

Usos de la pila

Cola: hacer fila

Una cola es una estructura de datos en la que los elementos se insertan por un extremo y se extraen por el otro.

enqueue →  ┌────┬────┬────┐  → dequeue
             │ 10 │ 20 │ 30 │
             └────┴────┴────┘
             frente (front)    atrás (rear)

Es como la fila en la caja de un supermercado. Quien llega primero es atendido primero. Esto se conoce como FIFO (First In, First Out), o principio de "primero en entrar, primero en salir".

from collections import deque

queue = deque()

# enqueue — insertar al final
queue.append(10)
queue.append(20)
queue.append(30)
print(queue)         # deque([10, 20, 30])

# dequeue — extraer desde el frente
front = queue.popleft()
print(front)         # 10 (el primero insertado)
print(queue)         # deque([20, 30])

También se puede implementar una cola con list de Python, pero list.pop(0) es lento porque requiere desplazar todos los elementos hacia adelante. deque tiene operaciones en ambos extremos con una complejidad de O(1).

Casos de uso de las colas

Comparación: pila frente a cola

Ejemplo práctico: validación de paréntesis (uso de pila)

def is_valid_brackets(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()

    return len(stack) == 0

print(is_valid_brackets("({[]})"))   # True
print(is_valid_brackets("([)]"))     # False
print(is_valid_brackets("(("))       # False

Al encontrar un paréntesis de apertura, se añade a la pila; al encontrar un paréntesis de cierre, se extrae de la pila para verificar si hay una coincidencia. La característica LIFO (último en entrar, primero en salir) de la pila se corresponde exactamente con la regla de "cerrar primero el paréntesis que se abrió más recientemente".