Reinventarlo

El otro diseño: bloques

Hay otra forma de hacer un deque: una lista de bloques de tamaño fijo (por ejemplo, de 512 elementos), con un índice de bloques. Al llenarse un extremo, se añade un bloque nuevo en ese extremo; los existentes no se mueven.

Un deque de bloques de 512 elementos tiene 3 bloques llenos (1536 elementos). Agregas uno por el frente y el bloque delantero está lleno. ¿Cuántos elementos se copian?Ninguno, porque el deque guarda siempre espacio libre delante y no se llenaNinguno: se añade un bloque nuevo delante y los existentes no se mueven512: se copia solo el bloque delantero a uno nuevo más grandeLos 1536: se reserva un bloque mayor y se copia todo, como en un array dinámico