double ended queue c with examples
Un tutorial detallado sobre Deque o cola de dos extremos en C ++. El tutorial explica qué es Deque, operaciones básicas, implementación y aplicaciones de C ++ y Java:
Cola de dos extremos o simplemente llamada 'Deque' es una versión generalizada de Queue.
La diferencia entre Queue y Deque es que no sigue el enfoque FIFO (First In, First Out). La segunda característica de Deque es que podemos insertar y quitar elementos de los extremos delantero o trasero.
=> Lea la serie de formación Easy C ++
Lo que vas a aprender:
- Clasificación de cola de doble final
- Operaciones táctiles básicas
- e ilustración
- e implementación
- Aplicaciones
- Conclusión
- Lectura recomendada
Clasificación de cola de doble final
Deque se puede clasificar de la siguiente manera:
Entrada de toque restringido; En la entrada restringida, la eliminación se puede realizar desde ambos extremos, pero la inserción solo se puede realizar en la parte posterior de la cola.
Deque de salida restringida: En la cola de salida restringida, la inserción se puede realizar desde ambos extremos, pero la eliminación se realiza solo en un extremo, es decir, en el extremo frontal de la cola.
También podemos implementar pilas y colas usando deque.
Operaciones táctiles básicas
Las siguientes son las operaciones básicas que se pueden realizar en deque.
- insertar frente: Inserte o agregue un artículo al frente de la etiqueta.
- insertLast: Inserte o agregue un artículo en la parte posterior de la etiqueta.
- deleteFront: Elimine o elimine el elemento del principio de la cola.
- eliminar último: Elimine o elimine el elemento de la parte posterior de la cola.
- getFront: Recupera el artículo del frente en la deque.
- obtener ultimo: Recupera el último elemento de la cola.
- esta vacio: Comprueba si el deque está vacío.
- está lleno: Comprueba si el deque está lleno.
e ilustración
Una deque vacía se representa de la siguiente manera:
cuáles son los diferentes tipos de pruebas
A continuación, insertamos el elemento 1 en la parte delantera.
Ahora, insertamos el elemento 3 en la parte trasera.
A continuación, agregamos el elemento 5 al frente y cuando lo incrementamos, el frente apunta a 4.
Luego, insertamos los elementos 7 en la parte trasera y 9 en la parte delantera. El deque se verá como se muestra a continuación.
A continuación, eliminemos un elemento del frente.
Así, vemos que cuando los elementos se insertan en el frente, la posición del frente disminuye mientras que se incrementa cuando se elimina un elemento. Para la parte trasera, la posición se incrementa para la inserción y se reduce para la extracción. .
el mejor software para clonar disco duro a ssd
e implementación
Implementación táctil 100 ++
Podemos implementar una deque en C ++ usando matrices así como una lista enlazada. Aparte de esto, la Standard Template Library (STL) tiene una clase “deque” que implementa todas las funciones para esta estructura de datos.
La implementación de matriz del deque se da a continuación. Como es una cola de dos extremos, hemos utilizado matrices circulares para la implementación.
|_+_|Producción:
Inserte el elemento 1 en el extremo trasero
insertar el elemento 3 en el extremo trasero
elemento trasero de la deque 3
Después de deleterear, rear = 1
insertar el elemento 5 en la parte delantera
elemento frontal de la deque 5
Después de deletefront, front = 1
Recuento de implementación de Java
La interfaz deque en Java, 'java.util.Deque' se deriva de la interfaz 'java.util.Queue'. Deque se puede utilizar como cola (primero en entrar, primero en salir) o como pila (último en entrar, primero en salir). Estas implementaciones funcionan más rápido que la lista vinculada.
A continuación se muestra la jerarquía de la interfaz Deque en Java.
Necesitamos recordar algunos puntos sobre la interfaz Deque en Java:
- La implementación no es segura para subprocesos ya que no hay sincronización externa.
- Deque no admite la concurrencia de varios subprocesos.
- Las implementaciones de Deque mediante matrices no permiten el uso de elementos NULL.
- Se permite que las matrices crezcan según los requisitos, siendo la capacidad sin restricciones y el soporte de matriz redimensionable las dos características más importantes.
A continuación se muestran los diversos métodos admitidos por la interfaz Deque:
pros y contras de linux vs windows
| No. | Método | Descripción |
|---|---|---|
| 7 | iterador () | Devuelve un iterador para la deque. |
| 1 | agregar (elemento) | Agrega un elemento a la cola. |
| 2 | addFirst (elemento) | Agrega un elemento a la cabeza / frente. |
| 3 | addLast (elemento) | Agrega un elemento a la cola / trasera. |
| 4 | oferta (elemento) | Agrega un elemento a la cola; devuelve un valor booleano para indicar si la inserción se realizó correctamente. |
| 5 | offerFirst (elemento) | Agrega un elemento a la cabeza; devuelve un valor booleano para indicar si la inserción se realizó correctamente. |
| 6 | offerLast (elemento) | Agrega un elemento a la cola; devuelve un valor booleano para indicar si la inserción se realizó correctamente. |
| 8 | descendingIterator() | Devuelve un iterador que tiene el orden inverso para este deque. |
| 9 | empujar (elemento) | Agrega un elemento al encabezado del deque. |
| 10 | pop (elemento) | Elimina un elemento de la cabecera del deque y lo devuelve. |
| 11 | removeFirst () | Elimina el elemento en la cabeza de la deque. |
| 12 | removeLast () | Elimina el elemento en la cola del deque. |
| 13 | encuesta() | Recupera y elimina el primer elemento del deque (representado por la cabeza del deque); devuelve NULL si el deque está vacío. |
| 14 | pollFirst () | Recupera y elimina el primer elemento de este deque; devuelve nulo si este deque está vacío. |
| 15 | pollLast () | Recupera y elimina el último elemento de este deque; devuelve nulo si este deque está vacío. |
| 16 | ojeada() | Recupera la cabecera (primer elemento de la deque) de la cola representada por esta deque; devuelve nulo si este deque está vacío. Nota: Esta operación no elimina el elemento. |
| 17 | peekFirst () | Recupera el primer elemento de este deque; devuelve nulo si este deque está vacío. Nota: Esta operación no elimina el elemento. |
| 18 | peekLast () | Recupera el último elemento de este deque o devuelve un valor nulo si este deque está vacío. Nota: Esta operación no elimina el elemento. |
La siguiente implementación de Java demuestra las diversas operaciones discutidas anteriormente.
|_+_|Producción:
Y el (11, 7, 3, 1, 5, 9, 13)
Iterador estándar
11 7 3 1 5 9 13
Iterador inverso
13 9 5 1 3 7 11
Vistazo 11
Después del vistazo: (11, 7, 3, 1, 5, 9, 13)
Pop 11
Después de pop: (7, 3, 1, 5, 9, 13)
¿Contiene el elemento 3 ?: verdadero
Deque después de eliminar el primer y último elemento: (3, 1, 5, 9)
En el programa anterior, usamos la interfaz Deque de Java y definimos una deque de elementos enteros. Luego realizamos varias operaciones en este deque y se muestran los resultados de estas operaciones.
Aplicaciones
Deque se puede utilizar en algunas de las siguientes aplicaciones.
# 1) Algoritmo de programación: Un algoritmo de programación, el 'algoritmo de programación A-steal', implementa la programación de tareas para varios procesadores en el sistema multiprocesador. Esta implementación usa deque y el procesador obtiene el primer elemento de deque para su ejecución.
# 2) Deshacer la lista de actividades: En las aplicaciones de software, tenemos muchas acciones. Uno es 'deshacer'. Cuando hemos realizado una acción de deshacer muchas veces, todas estas acciones se almacenan en una lista. Esta lista se mantiene como una deque para que podamos agregar / eliminar entradas fácilmente desde cualquier extremo.
#3) Elimine las entradas después de algún tiempo: Las aplicaciones actualizan las entradas en su lista, como las aplicaciones que enumeran las entradas de valores, etc. Estas aplicaciones eliminan las entradas después de un tiempo y también insertan nuevas entradas. Esto se hace usando un deque.
Conclusión
Deque es una cola de dos extremos que nos permite agregar / eliminar elementos de ambos extremos, es decir, el frente y la parte posterior de la cola. Deque se puede implementar mediante matrices o listas enlazadas. Sin embargo, también tenemos una clase de biblioteca de plantillas estándar (STL) que implementa las diversas operaciones del Deque.
En Java, tenemos una interfaz Deque que se hereda de la interfaz de cola para implementar Deque. Además de las operaciones estándar básicas de Deque, esta interfaz admite varias otras operaciones que se pueden realizar en Deque.
Deque se usa generalmente para aplicaciones que requieren agregar / quitar elementos de ambos extremos. También se utiliza principalmente en la programación de procesadores en sistemas multiprocesador.
=> Consulte la serie completa de capacitación en C ++
Lectura recomendada
- Cola de prioridad en STL
- ¿Qué son las pruebas de comparación (aprender con ejemplos)?
- Tutorial de Python DateTime con ejemplos
- Orden de Shell en C ++ con ejemplos
- Cortar comando en Unix con ejemplos
- Sintaxis del comando Unix Cat, opciones con ejemplos
- Uso del cursor en MongoDB con ejemplos
- Comando Ls en Unix con ejemplos