En este artículo, analizaremos la cola de doble extremo o deque. Primero deberíamos ver una breve descripción de la cola.
¿Qué es una cola?
Una cola es una estructura de datos en la que lo que llegue primero saldrá primero y sigue la política FIFO (primero en entrar, primero en salir). La inserción en la cola se realiza desde un extremo conocido como extremo posterior o el cola, mientras que la eliminación se realiza desde otro extremo conocido como Interfaz o el cabeza de la cola.
java doble a cadena
El ejemplo del mundo real de una cola es la cola de entradas fuera de una sala de cine, donde la persona que entra primero en la cola obtiene la entrada primero, y la persona que entra el último en la cola obtiene la entrada al final.
¿Qué es una Deque (o cola de doble extremo)?
El deque significa cola de doble terminación. Deque es una estructura de datos lineal donde las operaciones de inserción y eliminación se realizan desde ambos extremos. Podemos decir que deque es una versión generalizada de la cola.
Aunque la inserción y eliminación en una deque se puede realizar en ambos extremos, no sigue la regla FIFO. La representacion de un deque se da de la siguiente manera:
tipos de deque
Hay dos tipos de deque:
- Cola restringida de entrada
- Cola restringida de salida
Cola restringida de entrada
En la cola restringida de entrada, la operación de inserción se puede realizar en un solo extremo, mientras que la eliminación se puede realizar desde ambos extremos.
Cola restringida de salida
En la cola restringida de salida, la operación de eliminación se puede realizar en un solo extremo, mientras que la inserción se puede realizar desde ambos extremos.
Operaciones realizadas en deque
Existen las siguientes operaciones que se pueden aplicar en un deque:
- Inserción en el frente
- Inserción en la parte trasera
- Eliminación al frente
- Eliminación en la parte trasera
También podemos realizar operaciones de vista previa en la deque junto con las operaciones enumeradas anteriormente. A través de la operación de vista previa, podemos obtener los elementos delanteros y traseros del deque. Entonces, además de las operaciones anteriores, las siguientes operaciones también son compatibles con deque:
mysql crear usuario
- Obtenga el elemento frontal del deque.
- Consigue el artículo trasero del deque.
- Comprueba si el deque está lleno o no.
- Comprueba si el deque está vacío o no.
Ahora, comprendamos la operación realizada en deque usando un ejemplo.
Inserción en la parte delantera.
En esta operación, el elemento se inserta desde el extremo frontal de la cola. Antes de implementar la operación, primero debemos verificar si la cola está llena o no. Si la cola no está llena, entonces el elemento se puede insertar desde el frente siguiendo las siguientes condiciones:
- Si la cola está vacía, tanto la parte trasera como la delantera se inicializan con 0. Ahora, ambas apuntarán al primer elemento.
- De lo contrario, verifique la posición del frente si el frente es menor que 1 (frente<1), then reinitialize it by front = n - 1, es decir, el último índice de la matriz.
Inserción en la parte trasera.
En esta operación, el elemento se inserta desde el extremo posterior de la cola. Antes de implementar la operación, primero debemos verificar nuevamente si la cola está llena o no. Si la cola no está llena, entonces el elemento se puede insertar desde la parte posterior siguiendo las siguientes condiciones:
- Si la cola está vacía, tanto la parte trasera como la delantera se inicializan con 0. Ahora, ambas apuntarán al primer elemento.
- De lo contrario, incremente la parte trasera en 1. Si la parte trasera tiene el último índice (o tamaño - 1), entonces, en lugar de aumentarlo en 1, tenemos que hacerlo igual a 0.
Eliminación en el front-end
En esta operación, el elemento se elimina del principio de la cola. Antes de implementar la operación, primero debemos verificar si la cola está vacía o no.
código c abs
Si la cola está vacía, es decir, front = -1, es la condición de desbordamiento insuficiente y no podemos realizar la eliminación. Si la cola no está llena, entonces el elemento se puede insertar desde el frente siguiendo las siguientes condiciones:
Si el deque tiene un solo elemento, establezca trasero = -1 y frente = -1.
De lo contrario, si el frente está al final (eso significa frente = tamaño - 1), establezca frente = 0.
declaración del caso verilog
De lo contrario, incremente el frente en 1 (es decir, frente = frente + 1).
Eliminación en la parte trasera.
En esta operación, el elemento se elimina del final de la cola. Antes de implementar la operación, primero debemos verificar si la cola está vacía o no.
Si la cola está vacía, es decir, front = -1, es la condición de desbordamiento insuficiente y no podemos realizar la eliminación.
Si el deque tiene un solo elemento, establezca trasero = -1 y frente = -1.
Si trasero = 0 (la parte trasera está al frente), entonces establezca la parte trasera = n - 1.
De lo contrario, disminuya la parte trasera en 1 (o trasera = trasera -1).
cheque vacío
Esta operación se realiza para comprobar si el deque está vacío o no. Si front = -1, significa que el deque está vacío.
comprobar completo
Esta operación se realiza para comprobar si el deque está lleno o no. Si front = rear + 1, o front = 0 y rear = n - 1 significa que el deque está lleno.
La complejidad temporal de todas las operaciones anteriores del deque es O(1), es decir, constante.
Aplicaciones de deque
- Deque se puede utilizar como pila y cola, ya que admite ambas operaciones.
- Deque se puede usar como un verificador palíndromo, lo que significa que si leemos la cadena desde ambos extremos, la cadena sería la misma.
Implementación de deque
Ahora, veamos la implementación de deque en el lenguaje de programación C.
Linux que comando
#include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf('
Elements in a deque are: '); while(i!=r) { printf('%d ',deque[i]); i=(i+1)%size; } printf('%d',deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at front is: %d', deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at rear is %d', deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf('
The deleted element is %d', deque[f]); f=0; } else { printf('
The deleted element is %d', deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[r]); f=-1; r=-1; } else if(r==0) { printf('
The deleted element is %d', deque[r]); r=size-1; } else { printf('
The deleted element is %d', deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; } Producción:
Entonces, eso es todo sobre el artículo. Espero que el artículo le resulte útil e informativo.