Recorrido narrado
Los costos del deque circular
| Operación | Costo |
|---|---|
agregar_frente, agregar_final |
O(1) amortizado; O(n) cuando crece |
quitar_frente, quitar_final |
O(1) |
| leer la posición i | O(1): datos[(inicio + i) mod capacidad] |
| insertar en medio | O(min(i, n − i)): desplaza hacia el extremo más cercano |
Insertar en medio puede desplazar los elementos hacia el lado más corto: si insertas cerca del frente, mueves los del frente hacia atrás. Por eso es mejor que un array en ese caso.
función crecer(d): nuevo ← bloque de capacidad 2 × d.capacidad para k desde 0 hasta d.longitud − 1: nuevo[k] ← d.datos[(d.inicio + k) mod d.capacidad] d.datos ← nuevo; d.inicio ← 0; d.capacidad ← 2 × d.capacidadSu fila en la tabla de costos
Esta es la fila del deque hecho con un buffer circular, en las mismas columnas que la tabla de secuencias de la ruta.
| Representación | leer(i) |
insertar o borrar al inicio | insertar al final | borrar al final | insertar o borrar en i |
|---|---|---|---|---|---|
| buffer circular (deque) | O(1) | O(1) amortizado | O(1) amortizado | O(1) | O(min(i, n − i)) |
Lee el recorrido de esta página. Al pasar al siguiente momento, este cuenta como leído.