¿Qué estructura ofrece append y pop en O(1) por ambos extremos?
Opciones
- list
- collections.deque (Opción correcta)
- tuple
- heapq
Respuesta
collections.deque
Por qué
Una lista de Python es un array: insertar o quitar al PRINCIPIO desplaza todos los demás elementos, lo que es O(n).
collections.deque (double-ended queue, cola de doble extremo) está hecha para añadir y quitar rápido por ambos extremos: O(1).
Úsala para colas (primero en entrar, primero en salir) y sliding windows.
Recuerda
¿Necesitas una cola en Python? Usa collections.deque.