Deque ou file d'attente à double extrémité est une file d'attente de données de collecte linéaire séquentielle qui offre des fonctionnalités similaires à une file d'attente à double extrémité. Dans cette structure de données, la méthode ne suit pas la règle du premier entré, premier sorti (FIFO) pour le traitement des données. Cette structure de données est également appelée deque car les éléments sont insérés à la fin de la file d'attente et supprimés du début. Avec un deque, nous ne pouvons ajouter et supprimer des données qu'aux deux extrémités. La complexité temporelle de l’opération deque est O(1). Il existe deux types de deque -
Les entrées sont limitées
Limite d'entrée asymétrique.
Permet la suppression des données des deux côtés.
Sortie limitée
Limite de sortie asymétrique.
Permet d'insérer des données aux deux extrémités.
Les commandes suivantes aident les codeurs à effectuer diverses opérations en utilisant le regroupement d'ensembles de données sur un deque -
push_back() - Insère un élément à l'arrière du deque.
push_front() - Insère un élément depuis l'avant du deque.
pop_back() - Supprime les éléments du dos d'un deque.
pop_front() - Supprime les éléments du devant du deque.
front() - Renvoie l'élément avant du deque.
back() - Renvoie l'élément à l'arrière du deque.
at() - Définit/renvoie l'index spécifié.
size() - Renvoie le nombre d'éléments.
empty() - Renvoie vrai si le deque est vide.
Dans un tableau circulaire, nous pouvons utiliser l'opération deque. Si le tableau est plein, nous pouvons recommencer le processus depuis le début. Mais avec un tableau linéaire, si le tableau est plein, plus aucune donnée ne peut être insérée. Ensuite, nous pouvons voir une « popup de débordement ».
Deque propose de nombreuses applications en temps réel.
Pour une demande de planification de travaux.
Nous pouvons effectuer des opérations de rotation dans le sens horaire et antihoraire en temps O(1).
L'algorithme deque est également présent dans l'historique du navigateur Web.
Pour annuler les opérations de tri.
Deque présente de nombreux avantages.
Nous pouvons ajouter et supprimer des données du recto et du verso.
Leur taille est dynamique.
Deque fournit un timing efficace pour effectuer les opérations.
La pile LIFO est utilisée ici.
La redistribution n'est pas possible ici.
Il s'agit d'un processus thread-safe avec une synchronisation appropriée.
Compatible avec le cache.
Les inconvénients de la file d'attente à double extrémité sont
Le taux de consommation de mémoire du processus Deque est élevé.
Il a un problème de synchronisation multi-thread.
Non disponible sur toutes les plateformes.
Ne convient pas à la mise en œuvre d'opérations de tri.
Deque a moins de fonctionnalités.
Étape 1 - Considérez un tableau deque de taille n.
Étape 2 - Réglez les deux pointeurs sur "front=-1" (ce qui signifie avant) et "rear=0" (qui signifie réglé).
Il existe de nombreuses sous-parties dans ce processus. Nous pouvons effectuer plusieurs opérations dans un deque. Nous les résumons ici.
Algorithme d'insertion de données de face dans deque :-
Étape 1 - Vérifiez la position avant.
Étape 2 - Si "front
Étape 3 - Sinon, il faut réduire "front" de 1.
Étape 4 - Ajoutez le nouvel élément clé au début du tableau.
Algorithme d'insertion de données après deque :-
Étape 1 - Vérifiez si le tableau est plein.
Étape 2 - S'il est plein, appliquez "rear=0".
Étape 3 - Sinon, augmentez la valeur de "arrière" de 1.
Étape 4 - Ajoutez à nouveau la nouvelle clé à "array[rear]".
Algorithme de suppression des données du devant deque :-
Étape 1 - Vérifiez si le deque est vide.
Étape 2 - Si la liste est vide ("front=-1"), il s'agit d'une condition de dépassement insuffisant et la suppression ne peut pas être effectuée.
Étape 3 - S'il n'y a qu'un seul élément dans le deque. Puis "avant=arrière=-1".
Étape 4 - Sinon, "front" est à la fin, puis défini sur "front=0".
Étape 5 - Sinon, front=front+1.
Algorithme de suppression des données du dos de deque :-
Étape 1 - Vérifiez si le deque est vide.
Étape 2 - S'il est vide ("front=-1"), la suppression ne peut pas être effectuée. Il s'agit d'une condition de dépassement insuffisant.
Étape 3 - Si le deque n'a qu'une seule donnée, alors "front=rear=-1".
Étape 4 - Sinon, suivez les étapes ci-dessous.
Étape 5 - Si l'arrière est à l'avant "arrière=0". Allez vers l'avant "arrière = n-1".
Étape 6 - Sinon, arrière=arrière-1.
Algorithme pour vérifier si deque est vide :-
Étape 1 - Si front=-1, alors le deque est vide.
Algorithme pour vérifier si deque est plein :-
Étape 1 - si avant=0 et après=n-1
Étape 2 - Ou, avant=arrière+1
deque< object_type > deque_name;
deque<int> deque1 = {11, 21, 31, 41, 51};
deque<int> deque2 {10, 20, 30, 40, 50};
Dans les structures de données, deque hérite de certaines propriétés de stack et de file d'attente. En C++, un deque est implémenté comme vecteur de vecteurs.
Méthode 1 - Implémenter un deque de manière générale
Méthode 2 - Insérer un élément dans deque
Méthode 3 - Accéder aux éléments depuis un deque
Méthode 4 - Changer les éléments d'un deque
Dans ce code de build C++, nous configurons l'opération deque de manière générique. Dans cet exemple, nous insérons un élément au backend de la file d’attente, et c’est ainsi que fonctionne l’ensemble du système.
<iostream>#include <iostream>
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\n"
<< 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\n " << 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\n"
<< 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\n"
<< 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\n"
<< endl;
return -1;
}
return arr[front];
}
int Deque::getRear() {
if (isEmpty() || rear < 0) {
cout << " Underflow\n"
<< endl;
return -1;
}
return arr[rear];
}
int main() {
Deque dq(4);
cout << "insert element at rear end \n";
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 \n";
dq.insertfront(8);
cout << "front element: " << dq.getFront() << endl;
dq.deletefront();
cout << "after deletion of front element new front element: " << dq.getFront() << endl;
}
</iostream>insert element at rear end rear element: 11 after deletion of the rear element, the new rear element: 5 insert element at front end front element: 8 after deletion of front element new front element: 5
Dans ce code, nous essayons de créer du code C++ pour insérer des éléments dans un deque. Il existe deux façons de procéder.
push_back() - Insère un élément à la fin du tableau.
push_front() - Insère un élément au début du tableau.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums {16, 7};
cout << "Initial Deque As We Give: ";
for (const int& num : nums) {
cout << num << ", ";
}
nums.push_back(2001);
nums.push_front(1997);
cout << "\nFinal Deque Is Here: ";
for (const int& num : nums) {
cout << num << ", ";
}
return 0;
}
Initial Deque As We Give: 16, 7, Final Deque Is Here: 1997, 16, 7, 2001,
Nous pouvons accéder aux éléments d'un deque en utilisant deux méthodes.
front() - Au premier plan, nous pouvons obtenir la valeur de retour.
back() - Renvoie les données suivantes.
at() - Renvoie l'index spécifié.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums {16, 07, 10};
cout << "Front element are here: " << nums.front() << endl;
cout << "Back element are here: " << nums.back() << endl;
cout << "Element at index 1 present here: " << nums.at(1) << endl;
cout << "Element at index 0 present here: " << nums[0];
return 0;
}
Front element are here: 16 Back element are here: 10 Element at index 1 present here: 7 Element at index 0 present here: 16
Dans ce code, nous pouvons utiliser la méthode at() pour remplacer ou modifier les éléments de ce deque particulier.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums = {07,16,10,1997,2001};
cout << "Initial Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
nums.at(0) = 2022;
nums.at(1) = 10-05;
cout << "\nUpdated Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
return 0;
}
Initial Deque: 7, 16, 10, 1997, 2001, Updated Deque: 2022, 5, 10, 1997, 2001,
À travers cet article, nous avons découvert la file d'attente double, ses méthodes de fonctionnement, ses applications, ses avantages et ses inconvénients, ainsi que les algorithmes et les codes possibles utilisant C++.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
