Deque en la biblioteca de plantillas estándar (STL) de C++
Las colas de dos extremos son contenedores de secuencias con la función de expansión y contracción en ambos extremos.
Son similares a los vectores pero admiten la inserción y eliminación del primer elemento en O(1). A diferencia de los vectores, no se garantiza la asignación de almacenamiento contiguo.
Las colas de doble terminación son básicamente una implementación de la cola de doble terminación de la estructura de datos. Una estructura de datos de cola permite la inserción solo al final y la eliminación desde el frente. Esto es como una cola en la vida real, en la que las personas se eliminan del frente y se agregan en la parte posterior. Las colas de dos extremos son un caso especial de colas donde las operaciones de inserción y eliminación son posibles en ambos extremos.
Las funciones de deque son las mismas que las de un vector , con la adición de operaciones push y pop tanto para el anverso como para el reverso.
Vector en C++ STL
Los vectores son lo mismo que las arrays dinámicas con la capacidad de cambiar su tamaño automáticamente cuando se inserta o elimina un elemento, y el contenedor maneja automáticamente su almacenamiento. Los elementos vectoriales se colocan en almacenamiento contiguo para que se pueda acceder a ellos y recorrerlos mediante iteradores. En los vectores, los datos se insertan al final. Insertar al final toma un tiempo diferencial, ya que a veces puede ser necesario extender la array. Eliminar el último elemento lleva solo un tiempo constante porque no se cambia el tamaño. Insertar y borrar al principio o en el medio es lineal en el tiempo.
Diferencia entre Deque y Vector:
| Vector | Deque |
|---|---|
| Proporciona métodos de inserción y eliminación en el medio y al final | Proporciona métodos de inserción y eliminación en el medio, final, principio |
| Mal rendimiento para la inserción y eliminación en el frente | Buen rendimiento para la inserción y eliminación en la parte delantera |
| Almacena elementos de forma contigua | Contiene listas de fragmentos de memoria donde los elementos se almacenan de forma contigua. |
| Buen rendimiento para la adición y eliminación de elementos al final. | Buen rendimiento para la adición y eliminación de elementos al final. |
| Se almacena en el archivo de encabezado <vector> en C++ | Se almacena en el archivo de encabezado <deque> en C++ |
| Su complejidad temporal de inserción es O(N) | Su complejidad temporal de inserción es O(1) |
| Su complejidad temporal de borrado es O(N) | Su complejidad temporal de borrado es O(N) |
¿Cuándo deberíamos elegir Deque sobre Vector?
Debemos elegir Deque cuando nuestras operaciones sean de adición y eliminación de elementos al principio y al final (Double-ended queue ADT).