Estructura de datos Deque

En este tutorial, aprenderá qué es una cola de dos extremos (deque). Además, encontrará ejemplos prácticos de diferentes operaciones en una deque en C, C ++, Java y Python.

Deque o Double Ended Queue es un tipo de cola en la que la inserción y eliminación de elementos se puede realizar desde la parte delantera o trasera. Por lo tanto, no sigue la regla FIFO (primero en entrar, primero en salir).

Representación de Deque

Tipos de Deque

  • Entrada restringida Deque
    En este deque, la entrada está restringida en un solo extremo pero permite la eliminación en ambos extremos.
  • Salida restringida Deque
    En este deque, la salida está restringida en un solo extremo pero permite la inserción en ambos extremos.

Operaciones en un Deque

A continuación se muestra la implementación de matriz circular de deque. En una matriz circular, si la matriz está llena, comenzamos desde el principio.

Pero en una implementación de matriz lineal, si la matriz está llena, no se pueden insertar más elementos. En cada una de las operaciones siguientes, si la matriz está llena, se lanza un "mensaje de desbordamiento".

Antes de realizar las siguientes operaciones, se siguen estos pasos.

  1. Tome una matriz (deque) de tamaño n.
  2. Coloque dos punteros en la primera posición y establezca front = -1y rear = 0.
Inicializar una matriz y punteros para deque

1. Insertar en la parte delantera

Esta operación agrega un elemento al frente.

  1. Compruebe la posición del frente. Compruebe la posición del frente
  2. Si front < 1, reinicializar front = n-1(último índice). Cambiar de frente al final
  3. De lo contrario, disminuya el frente en 1.
  4. Agregue la nueva clave 5 en array(front). Inserte el elemento en el frente

2. Insertar en la parte trasera

Esta operación agrega un elemento a la parte trasera.

  1. Compruebe si la matriz está llena. Comprueba si el deque está lleno
  2. Si el deque está lleno, reinicialice rear = 0.
  3. De lo contrario, aumente la parte trasera en 1. Aumente la parte trasera
  4. Agregue la nueva clave 5 en array(rear). Inserte el elemento en la parte trasera

3. Eliminar del frente

La operación elimina un elemento del frente.

  1. Compruebe si el deque está vacío. Compruebe si deque está vacío
  2. Si el deque está vacío (es decir front = -1), no se puede realizar la eliminación ( condición de subdesbordamiento ).
  3. Si el deque tiene solo un elemento (es decir front = rear), configure front = -1y rear = -1.
  4. De lo contrario, si el frente está al final (es decir front = n - 1,), establezca ir al frente front = 0.
  5. Si no, front = front + 1. Aumentar el frente

4. Eliminar de la parte trasera

Esta operación elimina un elemento de la parte trasera.

  1. Compruebe si el deque está vacío. Compruebe si deque está vacío
  2. Si el deque está vacío (es decir front = -1), no se puede realizar la eliminación ( condición de subdesbordamiento ).
  3. Si el deque tiene solo un elemento (es decir front = rear), configure front = -1y rear = -1, de lo contrario siga los pasos a continuación.
  4. Si la parte trasera está en la parte delantera (es decir rear = 0), coloque la opción para ir al frente rear = n - 1.
  5. Si no, rear = rear - 1. Disminuir la parte trasera

5. Marque Vacío

Esta operación comprueba si el deque está vacío. Si front = -1, el deque está vacío.

6. Marque Completo

Esta operación comprueba si el deque está lleno. Si front = 0y rear = n - 1OR front = rear + 1, el deque está lleno.

Implementación de Deque en Python, Java, C y C ++

Python Java C C ++ 
 # Deque implementaion in python class Deque: def __init__(self): self.items = () def isEmpty(self): return self.items == () def addRear(self, item): self.items.append(item) def addFront(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) d = Deque() print(d.isEmpty()) d.addRear(8) d.addRear(5) d.addFront(7) d.addFront(10) print(d.size()) print(d.isEmpty()) d.addRear(11) print(d.removeRear()) print(d.removeFront()) d.addFront(55) d.addRear(45) print(d.items)
 // Deque implementation in Java class Deque ( static final int MAX = 100; int arr(); int front; int rear; int size; public Deque(int size) ( arr = new int(MAX); front = -1; rear = 0; this.size = size; ) boolean isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) boolean isEmpty() ( return (front == -1); ) void insertfront(int key) ( if (isFull()) ( System.out.println("Overflow"); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void insertrear(int key) ( if (isFull()) ( System.out.println(" Overflow "); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void deletefront() ( if (isEmpty()) ( System.out.println("Queue Underflow"); return; ) // Deque has only one element if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void deleterear() ( if (isEmpty()) ( System.out.println(" Underflow"); return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int getFront() ( if (isEmpty()) ( System.out.println(" Underflow"); return -1; ) return arr(front); ) int getRear() ( if (isEmpty() || rear < 0) ( System.out.println(" Underflow"); return -1; ) return arr(rear); ) public static void main(String() args) ( Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); ) )
 // Deque implementation in C #include #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() ( int arr(MAX); int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr(i) = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("Elements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("Elements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); n = count(arr); printf("Total number of elements in deque: %d", n); ) void addFront(int *arr, int item, int *pfront, int *prear) ( int i, k, c; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *pfront = *prear = 0; arr(*pfront) = item; return; ) if (*prear != MAX - 1) ( c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) ( arr(k) = arr(k - 1); k--; ) arr(k) = item; *pfront = k; (*prear)++; ) else ( (*pfront)--; arr(*pfront) = item; ) ) void addRear(int *arr, int item, int *pfront, int *prear) ( int i, k; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *prear = *pfront = 0; arr(*prear) = item; return; ) if (*prear == MAX - 1) ( k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) ( k = i; if (k == MAX - 1) arr(k) = 0; else arr(k) = arr(i + 1); ) (*prear)--; (*pfront)--; ) (*prear)++; arr(*prear) = item; ) int delFront(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*pfront); arr(*pfront) = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; ) int delRear(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*prear); arr(*prear) = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; ) void display(int *arr) ( int i; printf(" front: "); for (i = 0; i < MAX; i++) printf(" %d", arr(i)); printf(" :rear"); ) int count(int *arr) ( int c = 0, i; for (i = 0; i < MAX; i++) ( if (arr(i) != 0) c++; ) return c; )
 // Deque implementation in C++ #include using namespace std; #define MAX 10 class Deque ( int arr(MAX); int front; int rear; int size; public: Deque(int size) ( front = -1; rear = 0; this->size = size; ) void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); ); bool Deque::isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) bool Deque::isEmpty() ( return (front == -1); ) void Deque::insertfront(int key) ( if (isFull()) ( cout << "Overflow" << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void Deque ::insertrear(int key) ( if (isFull()) ( cout << " Overflow " << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void Deque ::deletefront() ( if (isEmpty()) ( cout << "Queue Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void Deque::deleterear() ( if (isEmpty()) ( cout << " Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int Deque::getFront() ( if (isEmpty()) ( cout << " Underflow" << endl; return -1; ) return arr(front); ) int Deque::getRear() ( if (isEmpty() || rear < 0) ( cout << " Underflow" << endl; return -1; ) return arr(rear); ) int main() ( Deque dq(4); cout << "insert element at rear end "; dq.insertrear(5); dq.insertrear(11); cout << "rear element: " << dq.getRear() << endl; dq.deleterear(); cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl; cout << "insert element at front end "; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; )

Complejidad del tiempo

La complejidad temporal de todas las operaciones anteriores es constante, es decir O(1).

Aplicaciones de la estructura de datos de Deque

  1. En operaciones de deshacer en software.
  2. Para almacenar el historial en los navegadores.
  3. Para implementar tanto pilas como colas.

Articulos interesantes...