Depende de lo que desee hacer con él y de si está dispuesto a tratar la matriz como un tipo de datos abstractos, en lugar de un tipo nativo “directo”. Podemos definir una estructura de datos que conserve el acceso aleatorio en tiempo constante y la adición y eliminación amortizadas en tiempo constante tanto a “frente” como a “atrás”: la cola de doble extremo, implementada como una matriz dinámica. Consulte Cola doble: Wikipedia (aunque ese artículo gasta demasiado tiempo en la implementación puramente funcional a expensas de la implementación basada en matriz).
Aquí está la idea básica: en lugar de tratar una secuencia de bytes como una matriz lineal, trátela como un búfer circular. Esto significa que necesita punteros al inicio y al final de los valores almacenados reales. Para insertar al final, aumente el puntero final en uno (ajustando si es necesario). Para insertar al principio, disminuya el puntero inicial en uno (nuevamente, ajustando). La eliminación desde el principio y el final son lo opuesto.
0010101xxxxxxxxxxxxxxxxxxxx10101111111
^ fin ^ comienzo
- ¿Hay alguna lista de problemas de árbol AVL similares a los problemas de árbol binario de Stanford?
- ¿Cuáles son los algoritmos importantes que todo desarrollador de software graduado debe saber?
- ¿Cuál es la complejidad de este algoritmo de conteo de bits?
- ¿Es cierto que si me vuelvo competente en estructuras de datos y algoritmos, puedo aprender cualquier lenguaje de programación y habilidades técnicas muy rápido?
- Los números ny (n + 2) son dos números que difieren en 2. ¿Cuál es el valor medio de estos dos números?
// Insertar “1” en los resultados finales en:
00101011xxxxxxxxxxxxxxxxxxx10101111111
^ fin ^ comienzo
// Eliminar de los resultados iniciales en:
00101011xxxxxxxxxxxxxxxxxxxx0101111111
^ fin ^ comienzo
Cuando begin = end, la cola está llena y necesitamos asignar un búfer circular más grande. Si duplicamos el tamaño cada vez que produce tiempo constante amortizado para inserciones (al igual que append-at-end en una implementación de matriz lineal como std :: vector)
Con esta estructura de datos, podemos realizar una rotación de un solo bit mediante la combinación de una eliminación de un extremo y una inserción en el otro. También podemos atravesar el búfer circular para copiar todos los datos en tiempo O (n), lo mismo que una matriz lineal, o especializar la implementación para realizar operaciones bit a bit con otra deque en tiempo O (n) también.
std :: deque es parte del estándar C ++ pero puede implementarse de una manera algo diferente donde el búfer se divide en trozos de tamaño fijo, para evitar la copia.
