Listas como pilas y colas en Python: stack con list, FIFO eficiente con deque

Una lista de Python puede actuar como pila (stack) y como cola (queue), pero no con la misma eficiencia. Conocer la diferencia entre O(1) y O(n) te ahorra problemas de rendimiento cuando el volumen de datos crece.

Pila LIFO con list: append y pop en O(1)

Una pila sigue el principio LIFO (Last In, First Out): el último en entrar es el primero en salir. Con una lista de Python basta con usar append() para apilar y pop() sin argumentos para desapilar. Ambas operaciones son O(1) porque actúan sobre el extremo derecho de la lista.

# Historial de navegación (pila)
historial = []

historial.append("https://python.org")
historial.append("https://docs.python.org")
historial.append("https://pypi.org")

pagina_actual = historial.pop()
print(pagina_actual)          # https://pypi.org
print(historial)              # ['https://python.org', 'https://docs.python.org']

Por qué pop(0) es lento en colas FIFO

Una cola sigue el principio FIFO (First In, First Out): el primero en entrar es el primero en salir. Usando append() para encolar y pop(0) para desencolar parece intuitivo, pero pop(0) es O(n): Python tiene que desplazar todos los elementos restantes un puesto a la izquierda cada vez.

# Cola con list — funciona pero es lenta con muchos elementos
cola = []
cola.append("mensaje_1")
cola.append("mensaje_2")
cola.append("mensaje_3")

primero = cola.pop(0)  # O(n) — LENTO con listas grandes
print(primero)         # mensaje_1

collections.deque: la solución eficiente

collections.deque (double-ended queue) es una estructura diseñada para insertar y eliminar por ambos extremos en O(1). Usa append() para añadir al final y popleft() para extraer del principio.

from collections import deque

# Cola de mensajes FIFO eficiente
cola = deque()
cola.append("tarea_1")
cola.append("tarea_2")
cola.append("tarea_3")

tarea = cola.popleft()  # O(1) siempre
print(tarea)             # tarea_1
print(cola)              # deque(['tarea_2', 'tarea_3'])

Buffer de logs con maxlen

deque acepta un parámetro maxlen que limita su tamaño automáticamente. Cuando está lleno y añades un elemento por la derecha, descarta automáticamente el más antiguo por la izquierda. Ideal para buffers de tamaño fijo.

from collections import deque

# Guardar solo los últimos 3 logs
buffer_logs = deque(maxlen=3)

buffer_logs.append("INFO: inicio")
buffer_logs.append("INFO: procesando")
buffer_logs.append("WARN: lento")
buffer_logs.append("ERROR: timeout")  # descarta "INFO: inicio"

print(buffer_logs)
# deque(['INFO: procesando', 'WARN: lento', 'ERROR: timeout'], maxlen=3)

Editor con deshacer (undo) usando pila

El patrón pila es el mecanismo natural para implementar la función deshacer de un editor:

class EditorSimple:
    def __init__(self):
        self.contenido = ""
        self._historial = []

    def escribir(self, texto):
        self._historial.append(self.contenido)
        self.contenido += texto
        print(f"Contenido: '{self.contenido}'")

    def deshacer(self):
        if self._historial:
            self.contenido = self._historial.pop()
            print(f"Deshecho. Contenido: '{self.contenido}'")
        else:
            print("Nada que deshacer")

editor = EditorSimple()
editor.escribir("Hola")
editor.escribir(", mundo")
editor.deshacer()    # Contenido: 'Hola'
editor.deshacer()    # Contenido: ''
editor.deshacer()    # Nada que deshacer

La regla práctica: usa list como pila (push/pop por el extremo derecho) y collections.deque como cola (append + popleft). Si tu código usa pop(0) con frecuencia, es el momento de cambiar a deque.