Dans cet article, nous discuterons de la file d'attente à double extrémité ou deque. Nous devrions d’abord voir une brève description de la file d’attente.
Qu'est-ce qu'une file d'attente ?
Une file d'attente est une structure de données dans laquelle tout ce qui arrive en premier sera sorti en premier, et elle suit la politique FIFO (First-In-First-Out). L'insertion dans la file d'attente se fait à partir d'une extrémité connue sous le nom de extrémité arrière ou la queue, alors que la suppression est effectuée à partir d'une autre extrémité connue sous le nom de l'extrémité avant ou la tête de la file d'attente.
table ascii en c
L'exemple concret d'une file d'attente est la file d'attente pour les billets à l'extérieur d'une salle de cinéma, où la personne qui entre en premier dans la file d'attente obtient le billet en premier, et la personne qui entre en dernier dans la file d'attente obtient enfin le billet.
Qu'est-ce qu'un Deque (ou file d'attente à double extrémité)
Le deque signifie Double Ended Queue. Deque est une structure de données linéaire où les opérations d'insertion et de suppression sont effectuées des deux côtés. On peut dire que deque est une version généralisée de la file d'attente.
Bien que l'insertion et la suppression dans un deque puissent être effectuées aux deux extrémités, elles ne suivent pas la règle FIFO. La représentation d'un deque est donnée comme suit -
Types de deque
Il existe deux types de deque -
- File d'attente restreinte en entrée
- File d'attente restreinte en sortie
File d'attente restreinte aux entrées
Dans la file d'attente d'entrée restreinte, l'opération d'insertion peut être effectuée à une seule extrémité, tandis que la suppression peut être effectuée aux deux extrémités.
File d'attente de sortie restreinte
Dans la file d'attente de sortie restreinte, l'opération de suppression peut être effectuée à une seule extrémité, tandis que l'insertion peut être effectuée à partir des deux extrémités.
Opérations effectuées sur deque
Les opérations suivantes peuvent être appliquées sur un deque -
- Insertion devant
- Insertion à l'arrière
- Suppression au recto
- Suppression à l'arrière
Nous pouvons également effectuer des opérations de peek dans le deque ainsi que les opérations répertoriées ci-dessus. Grâce à l'opération Peek, nous pouvons obtenir les éléments avant et arrière du deque. Ainsi, en plus des opérations ci-dessus, les opérations suivantes sont également prises en charge dans deque -
âge ensoleillé deol
- Obtenez l'élément avant du deque
- Obtenez l'élément arrière du deque
- Vérifiez si le deque est plein ou non
- Vérifie si le deque est vide ou non
Maintenant, comprenons l'opération effectuée sur deque à l'aide d'un exemple.
Insertion à l'avant
Dans cette opération, l’élément est inséré depuis le début de la file d’attente. Avant de mettre en œuvre l'opération, il faut d'abord vérifier si la file d'attente est pleine ou non. Si la file d'attente n'est pas pleine, l'élément peut être inséré depuis le front-end en utilisant les conditions ci-dessous :
exemple de code c#
- Si la file d'attente est vide, Rear et Front sont initialisés à 0. Désormais, les deux pointeront vers le premier élément.
- Sinon, vérifiez la position du devant si le devant est inférieur à 1 (avant<1), then reinitialize it by front = n - 1 , c'est-à-dire le dernier index du tableau.
Insertion à l'arrière
Dans cette opération, l'élément est inséré depuis l'arrière de la file d'attente. Avant de mettre en œuvre l'opération, il faut d'abord vérifier à nouveau si la file d'attente est pleine ou non. Si la file d'attente n'est pas pleine, l'élément peut être inséré depuis l'arrière en utilisant les conditions ci-dessous :
- Si la file d'attente est vide, Rear et Front sont initialisés à 0. Désormais, les deux pointeront vers le premier élément.
- Sinon, incrémentez l'arrière de 1. Si l'arrière est au dernier indice (ou taille - 1), alors au lieu de l'augmenter de 1, nous devons le rendre égal à 0.
Suppression au début
Dans cette opération, l’élément est supprimé du début de la file d’attente. Avant de mettre en œuvre l'opération, il faut d'abord vérifier si la file d'attente est vide ou non.
Si la file d'attente est vide, c'est-à-dire front = -1, il s'agit d'une condition de dépassement insuffisant et nous ne pouvons pas effectuer la suppression. Si la file d'attente n'est pas pleine, l'élément peut être inséré depuis le front-end en utilisant les conditions ci-dessous :
Si le deque n'a qu'un seul élément, définissez Rear = -1 et Front = -1.
Sinon, si front est à la fin (cela signifie front = taille - 1), définissez front = 0.
surcharge de méthode
Sinon, incrémentez le front de 1 (c'est-à-dire front = front + 1).
Suppression à l’arrière
Dans cette opération, l’élément est supprimé de l’arrière de la file d’attente. Avant de mettre en œuvre l'opération, il faut d'abord vérifier si la file d'attente est vide ou non.
Si la file d'attente est vide, c'est-à-dire front = -1, il s'agit d'une condition de dépassement insuffisant et nous ne pouvons pas effectuer la suppression.
Si le deque n'a qu'un seul élément, définissez Rear = -1 et Front = -1.
Si arrière = 0 (l'arrière est à l'avant), alors définissez arrière = n - 1.
Sinon, décrémentez l'arrière de 1 (ou arrière = arrière -1).
Chèque vide
Cette opération est effectuée pour vérifier si le deque est vide ou non. Si front = -1, cela signifie que le deque est vide.
Chèque complet
Cette opération est effectuée pour vérifier si le deque est plein ou non. Si front = arrière + 1, ou avant = 0 et arrière = n - 1 cela signifie que le deque est plein.
La complexité temporelle de toutes les opérations ci-dessus du deque est O(1), c'est-à-dire constante.
Applications de deque
- Deque peut être utilisé à la fois comme pile et comme file d'attente, car il prend en charge les deux opérations.
- Deque peut être utilisé comme vérificateur de palindrome, ce qui signifie que si nous lisons la chaîne des deux extrémités, la chaîne serait la même.
Implémentation de deque
Voyons maintenant l'implémentation de deque dans le langage de programmation C.
python chameau
#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; } Sortir:
Donc, c'est tout à propos de l'article. J'espère que l'article vous sera utile et informatif.