Structure des données Deque

Dans ce didacticiel, vous apprendrez ce qu'est une file d'attente double (deque). En outre, vous trouverez des exemples fonctionnels de différentes opérations sur un deque en C, C ++, Java et Python.

Deque ou Double Ended Queue est un type de file d'attente dans lequel l'insertion et la suppression d'éléments peuvent être effectuées à partir de l'avant ou de l'arrière. Ainsi, il ne suit pas la règle FIFO (First In First Out).

Représentation de Deque

Types de Deque

  • Entrée restreinte Deque
    Dans ce deque, l'entrée est restreinte à une seule extrémité mais permet la suppression aux deux extrémités.
  • Sortie restreinte Deque
    Dans ce deque, la sortie est restreinte à une seule extrémité mais permet l'insertion aux deux extrémités.

Opérations sur un Deque

Vous trouverez ci-dessous l'implémentation du tableau circulaire de deque. Dans un tableau circulaire, si le tableau est plein, nous partons du début.

Mais dans une implémentation de tableau linéaire, si le tableau est plein, plus aucun élément ne peut être inséré. Dans chacune des opérations ci-dessous, si le tableau est plein, un "message de débordement" est émis.

Avant d'effectuer les opérations suivantes, ces étapes sont suivies.

  1. Prenez un tableau (deque) de taille n.
  2. Définissez deux pointeurs à la première position et définissez front = -1et rear = 0.
Initialiser un tableau et des pointeurs pour deque

1. Insérez à l'avant

Cette opération ajoute un élément à l'avant.

  1. Vérifiez la position de l'avant. Vérifiez la position de l'avant
  2. Si front < 1, réinitialisez front = n-1(dernier index). Passer de l'avant à la fin
  3. Sinon, diminuez le front de 1.
  4. Ajoutez la nouvelle clé 5 dans array(front). Insérez l'élément à l'avant

2. Insérez à l'arrière

Cette opération ajoute un élément à l'arrière.

  1. Vérifiez si la baie est pleine. Vérifiez si deque est plein
  2. Si le deque est plein, réinitialisez rear = 0.
  3. Sinon, augmentez l'arrière de 1. Augmentez l'arrière
  4. Ajoutez la nouvelle clé 5 dans array(rear). Insérez l'élément à l'arrière

3. Supprimer de l'avant

L'opération supprime un élément de l'avant.

  1. Vérifiez si le deque est vide. Vérifiez si deque est vide
  2. Si le deque est vide (c'est-à-dire front = -1), la suppression ne peut pas être effectuée ( condition de dépassement inférieur ).
  3. Si le deque n'a qu'un seul élément (ie front = rear), définissez front = -1et rear = -1.
  4. Sinon, si l'avant est à la fin (c.-à-d. front = n - 1), Placez-le à l'avant front = 0.
  5. Sinon, front = front + 1. Augmenter l'avant

4. Supprimer de l'arrière

Cette opération supprime un élément de l'arrière.

  1. Vérifiez si le deque est vide. Vérifiez si deque est vide
  2. Si le deque est vide (c'est-à-dire front = -1), la suppression ne peut pas être effectuée ( condition de dépassement inférieur ).
  3. Si le deque n'a qu'un seul élément (c'est-à-dire front = rear), définissez front = -1et rear = -1, sinon suivez les étapes ci-dessous.
  4. Si l'arrière est à l'avant (c'est-à-dire rear = 0), placez-vous à l'avant rear = n - 1.
  5. Sinon, rear = rear - 1. Diminuer l'arrière

5. Cochez Vide

Cette opération vérifie si le deque est vide. Si front = -1, le deque est vide.

6. Vérifier le plein

Cette opération vérifie si le deque est plein. Si front = 0et rear = n - 1OU front = rear + 1, le deque est plein.

Implémentation Deque en Python, Java, C et 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; )

Complexité temporelle

La complexité temporelle de toutes les opérations ci-dessus est constante, c'est-à-dire O(1).

Applications de la structure de données Deque

  1. Dans les opérations d'annulation sur le logiciel.
  2. Pour stocker l'historique dans les navigateurs.
  3. Pour implémenter à la fois des piles et des files d'attente.

Articles intéressants...