Menu

File d'attente à double extrémité (Deque) en C ++ avec des exemples

  • Principal
  • Autre
  • File d'attente à double extrémité (Deque) en C ++ avec des exemples

double ended queue c with examples

Essayez Notre Instrument Pour Éliminer Les Problèmes

Un didacticiel approfondi sur la file d'attente Deque ou double en C ++. Le didacticiel explique ce qu'est Deque, les opérations de base, l'implémentation et les applications C ++ et Java:

La file d'attente à double extrémité ou simplement appelée «Deque» est une version généralisée de Queue.

La différence entre Queue et Deque est qu'il ne suit pas l'approche FIFO (First In, First Out). La deuxième caractéristique de Deque est que nous pouvons insérer et retirer des éléments des extrémités avant ou arrière.

=> Lisez la série de formations Easy C ++

File d

Ce que vous apprendrez:

Classification des files d'attente à double extrémité

Deque peut être classé comme suit:

Entrée tactile restreinte; En entrée restreinte, la suppression peut être effectuée à partir des deux extrémités, mais l'insertion ne peut être effectuée qu'à l'arrière de la file d'attente.

Deque restreint en sortie: Dans la file d'attente à sortie limitée, l'insertion peut être effectuée à partir des deux extrémités, mais la suppression n'est effectuée qu'à une seule extrémité, c'est-à-dire le frontal de la file d'attente.

Nous pouvons également implémenter des piles et des files d'attente à l'aide de deque.

Opérations tactiles de base

Voici les opérations de base qui peuvent être effectuées sur deque.

  • insérer devant: Insérez ou ajoutez un élément à l'avant du deque.
  • insertLast: Insérez ou ajoutez un élément à l'arrière du deque.
  • deleteFront: Supprimez ou supprimez l'élément du début de la file d'attente.
  • supprimer le dernier: Supprimez ou supprimez l'élément de l'arrière de la file d'attente.
  • getFront: Récupère l'élément avant dans le deque.
  • getLast: Récupère le dernier élément de la file d'attente.
  • est vide: Vérifie si le deque est vide.
  • est rempli: Vérifie si le deque est plein.

et illustration

Un deque vide est représenté comme suit:

Retour recomptage

quelle est la différence entre unix et linux

Ensuite, nous insérons l'élément 1 à l'avant.

Insérer l

Maintenant, nous insérons l'élément 3 à l'arrière.

Insérer l

Ensuite, nous ajoutons l'élément 5 à l'avant et, une fois incrémenté, les points avant à 4.

Élément 5 à l

Ensuite, on insère les éléments 7 à l'arrière et 9 à l'avant. Le deque ressemblera à celui ci-dessous.

comment afficher un fichier .dat

éléments 7 à l

Ensuite, supprimons un élément de l'avant.

Retirer l

Ainsi, on voit que lorsque les éléments sont insérés à l'avant, la position avant est décrémentée alors qu'elle est incrémentée lorsqu'un élément est retiré. Pour l'extrémité arrière, la position est incrémentée pour l'insertion et décrémentée pour le retrait .

et mise en œuvre

Implémentation 100 ++ touch

Nous pouvons implémenter un deque en C ++ en utilisant des tableaux ainsi qu'une liste chaînée. En dehors de cela, la bibliothèque de modèles standard (STL) a une classe «deque» qui implémente toutes les fonctions pour cette structure de données.

L'implémentation de tableau du deque a été donnée ci-dessous. Comme il s'agit d'une file d'attente à deux extrémités, nous avons utilisé des tableaux circulaires pour l'implémentation.

#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!! ' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!! ' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!! ' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!! ' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!! ' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!! ' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end '; dq.insertrear(1); cout << 'insert element 3 at rear end '; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end '; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; }

Production:

Insérer l'élément 1 à l'arrière

insérer l'élément 3 à l'arrière

élément arrière de deque 3

Après suppression, arrière = 1

élément d'insertion 5 à l'extrémité avant

élément avant de deque 5

Après deletefront, front = 1

et sortie

Recomptage de l'implémentation Java

L'interface deque en Java, «java.util.Deque» est dérivée de l'interface «java.util.Queue». Deque peut être utilisé comme une file d'attente (premier entré, premier sorti) ou une pile (dernier entré, premier sorti). Ces implémentations fonctionnent plus rapidement que la liste chaînée.

Vous trouverez ci-dessous la hiérarchie de l'interface Deque en Java.

Hiérarchie pour l

Nous devons nous rappeler quelques points sur l'interface Deque en Java:

  • L'implémentation n'est pas thread-safe car il n'y a pas de synchronisation externe.
  • Deque ne prend pas en charge la concurrence par plusieurs threads.
  • L'implémentation de Deque à l'aide de tableaux ne permet pas l'utilisation d'éléments NULL.
  • Les baies peuvent croître selon les exigences, avec une capacité sans restriction et une prise en charge des baies redimensionnables étant les deux fonctionnalités les plus importantes.

Voici les différentes méthodes prises en charge par l'interface Deque:

comment déclarer la liste en java
Non.MéthodeLa description
septitérateur ()Renvoie un itérateur pour le deque.
unajouter (élément)Ajoute un élément à la queue.
deuxaddFirst (élément)Ajoute un élément à la tête / à l'avant.
3addLast (élément)Ajoute un élément à la queue / à l'arrière.
4offre (élément)Ajoute un élément à la queue; renvoie une valeur booléenne pour indiquer si l'insertion a réussi.
5offerFirst (élément)Ajoute un élément à la tête; renvoie une valeur booléenne pour indiquer si l'insertion a réussi.
6offerLast (élément)Ajoute un élément à la queue; renvoie une valeur booléenne pour indiquer si l'insertion a réussi.
8descendingIterator ()Renvoie un itérateur qui a l'ordre inverse pour ce deque.
9pousser (élément)Ajoute un élément à la tête du deque.
dixpop (élément)Supprime un élément de la tête du deque et le renvoie.
OnzeremoveFirst ()Supprime l'élément en tête du deque.
12removeLast ()Supprime l'élément à la fin du deque.
13sondage()Récupère et supprime le premier élément du deque (représenté par la tête du deque); renvoie NULL si le deque est vide.
14pollFirst ()Récupère et supprime le premier élément de ce deque; renvoie null si ce deque est vide.
quinzepollLast ()Récupère et supprime le dernier élément de ce deque; renvoie null si ce deque est vide.
16coup d'oeil ()Récupère la tête (premier élément du deque) de la file représentée par ce deque; renvoie null si ce deque est vide.
Remarque: Cette opération ne supprime pas l'élément.
17peekFirst ()Récupère le premier élément de ce deque; renvoie null si ce deque est vide.
Remarque: Cette opération ne supprime pas l'élément.
18peekLast ()Récupère le dernier élément de ce deque, ou retourne null si ce deque est vide.
Remarque: Cette opération ne supprime pas l'élément.

L'implémentation Java suivante illustre les différentes opérations décrites ci-dessus.

import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + ' '); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println(' Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println(' Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println(' Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println(' Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } }

Production:

Et le (11, 7, 3, 1, 5, 9, 13)

Itérateur standard
11 7 3 1 5 9 13
Itérateur inversé
13 9 5 1 3 7 11

Coup d'oeil 11
Après coup d'œil: (11, 7, 3, 1, 5, 9, 13)

Pop 11
Après la pop: (7, 3, 1, 5, 9, 13)

Contient l'élément 3?: Vrai

Deque après avoir retiré le premier et le dernier élément: (3, 1, 5, 9)

Sortie Java Deque

Dans le programme ci-dessus, nous avons utilisé l'interface Deque de Java et nous avons défini un deque d'éléments entiers. Ensuite, nous avons effectué diverses opérations sur ce deque et en sortie les résultats de ces opérations sont affichés.

Applications

Deque peut être utilisé dans certaines des applications suivantes.

# 1) Algorithme de planification: Un algorithme de planification, «algorithme de planification A-steal», implémente la planification de tâches pour divers processeurs dans le système multiprocesseur. Cette implémentation utilise deque et le processeur obtient le premier élément du deque pour exécution.

# 2) Annuler la liste des activités: Dans les applications logicielles, nous avons de nombreuses actions. L'un est «annuler». Lorsque nous avons effectué plusieurs fois une action d'annulation, toutes ces actions sont stockées dans une liste. Cette liste est maintenue en tant que deque afin que nous puissions facilement ajouter / supprimer des entrées de n'importe quelle extrémité.

# 3) Supprimez les entrées après un certain temps: Les applications actualisent les entrées dans leur liste, comme les applications répertoriant les entrées de stock, etc. Ces applications suppriment les entrées après un certain temps et insèrent également de nouvelles entrées. Ceci est fait en utilisant un deque.

Conclusion

Deque est une file d'attente à deux extrémités qui nous permet d'ajouter / supprimer des éléments des deux extrémités, c'est-à-dire avant et arrière, de la file d'attente. Deque peut être implémenté à l'aide de tableaux ou de listes chaînées. Cependant, nous avons également une classe STL (Standard Template Library) qui implémente les différentes opérations du Deque.

En Java, nous avons une interface Deque héritée de l'interface de file d'attente pour implémenter Deque. Outre les opérations standard de base du Deque, cette interface prend en charge diverses autres opérations pouvant être effectuées sur Deque.

Deque est généralement utilisé pour les applications qui nécessitent l'ajout / la suppression d'éléments aux deux extrémités. Il est également principalement utilisé dans la planification des processeurs dans les systèmes multiprocesseurs.

=> Découvrez la série complète de formations C ++

lecture recommandée

^