introduction
Une file d'attente est un ensemble d'éléments, où le premier élément ajouté à la liste doit être le premier élément à supprimer ensuite. Ainsi, au fur et à mesure que des articles sont ajoutés à la collection, sa taille augmente, c'est-à-dire sa longueur. Chaque fois qu'un élément doit être supprimé, il doit être le premier ajouté. Si des éléments sont supprimés en continu, le suivant supprimé est le deuxième élément ; le troisième est supprimé par la suite, et ainsi de suite.
Une fois le premier élément de la liste d'origine supprimé, le second devient le premier élément. Une fois le deuxième élément supprimé, le troisième devient le premier élément, et ainsi de suite.
Un bon exemple concret de file d'attente est lorsque les gens font la queue pour attendre un service ou un bien. La première personne est servie avant la dernière. Cependant, la file d'attente dont il est question dans ce didacticiel est la file d'attente logicielle, telle qu'elle est conçue en C++.
FIFO
FIFO signifie premier entré, premier sorti. C'est une autre façon d'apprécier la file d'attente. Cela signifie que le premier élément à entrer dans la liste est le premier élément à être supprimé, chaque fois que la suppression doit avoir lieu. Le début de la liste s'appelle la tête ou le devant ; la fin de la liste est appelée le dos ou la queue.
Opérations essentielles
Une file d'attente logicielle doit avoir au moins les opérations suivantes :
pousser
Cette opération, ajoute un nouvel élément à la fin de la file d'attente. Cette opération s'appelle officiellement mise en file d'attente.
décalage
Cette opération supprime le premier élément de la file d'attente et le deuxième élément devient le nouveau premier élément. Cette opération est officiellement appelée dequeue. Cela s'appelle pop en C++.
Cet article explique comment utiliser la structure de données de file d'attente C++. Vous devez connaître les pointeurs et références C++ pour comprendre le reste de cet article.
Classe et objets
Une classe est un ensemble de variables et de fonctions qui fonctionnent ensemble, où les variables n'ont pas de valeurs affectées. Lorsque des valeurs sont affectées aux variables, la classe devient un objet. Des valeurs différentes attribuées à la même classe entraînent des objets différents ; c'est-à-dire que différents objets sont la même classe avec des valeurs différentes. On dit que la création d'un objet à partir d'une classe instancie l'objet.
Le nom, file d'attente, est une classe. Un objet créé à partir de la classe de file d'attente a un nom choisi par le programmeur.
Une fonction qui appartient à une classe est nécessaire pour instancier un objet de la classe. En C++, cette fonction a le même nom que le nom de la classe. Les objets créés (instanciés) à partir de la classe ont des noms différents qui leur sont attribués par le programmeur.
Créer un objet à partir de la classe, c'est construire l'objet ; cela signifie également instancier.
Un programme C++ qui utilise la classe queue commence par les lignes suivantes en haut du fichier :
#comprendre#comprendre
en utilisant l'espace de noms std;
La première ligne est pour l'entrée/sortie. La deuxième ligne permet au programme d'utiliser toutes les fonctionnalités de la classe de file d'attente. La troisième ligne permet au programme d'utiliser les noms dans l'espace de noms standard.
Surcharger une fonction
Lorsque deux signatures de fonction différentes ou plus ont le même nom, ce nom est dit surchargé. Lorsqu'une fonction est appelée, le nombre et le type d'arguments déterminent quelle fonction est réellement exécutée.
Construction
file d'attente<taper>Nom()La déclaration suivante instancie une file d'attente nommée, que de type int.
file d'attente<entier>Quoi;La file d'attente est vide. La déclaration commence par le mot réservé, queue suivi de chevrons avec le type de données. Ensuite, vous avez le nom donné au programmeur pour la file d'attente.
Construction avec la liste d'initialisation
La définition suivante montre comment créer une file d'attente avec une liste d'initialisation :
file d'attente<flotter>Quoi({1.1, 2.2, 3.3, 4.4});Détruire une file d'attente
Pour détruire une file d'attente, laissez-la simplement hors de portée.
Accès aux éléments de file d'attente
pousser (valeur)
Une file d'attente est une liste First-In-First-Out. Ainsi, chaque valeur est ajoutée à l'arrière. Le segment de code suivant crée une file d'attente vide, après quoi cinq valeurs flottantes sont ajoutées à l'arrière :
file d'attente<flotter>Quoi;Quoi.pousser(1.1);
Quoi.pousser(2.2);
Quoi.pousser(3.3);
Quoi.pousser(4.4);
Quoi.pousser(5.5);
taille() const
Cela renvoie le nombre d'éléments dans la file d'attente. Le code suivant illustre :
file d'attente<flotter>Quoi;Quoi.pousser(1.1);Quoi.pousser(2.2);Quoi.pousser(3.3);Quoi.pousser(4.4);Quoi.pousser(5.5);
cout<<Quoi.Taille() << ' ';
La sortie est 5.
de face()
Cela renvoie une référence au premier élément de la file d'attente, sans supprimer l'élément. La sortie du code suivant est 1.1.
file d'attente<flotter>Quoi;Quoi.pousser(1.1);Quoi.pousser(2.2);Quoi.pousser(3.3);Quoi.pousser(4.4);Quoi.pousser(5.5);
cout<<Quoi.de face() << ' ';
L'élément n'est pas supprimé de la file d'attente.
avant() const
Lorsque la construction de la file d'attente est précédée de const, l'expression front() const est exécutée à la place de front(). Il est utilisé dans le code suivant, par exemple.
constfile d'attente<flotter>Quoi({1.1, 2.2, 3.3, 4.4, 5.5});cout<<Quoi.de face() << ' ';
Une référence constante est renvoyée. L'élément n'est pas supprimé du vecteur. Les éléments de file d'attente ne peuvent pas être modifiés.
arrière()
Cela renvoie une référence au dernier élément de la file d'attente, sans supprimer l'élément. La sortie du code suivant est 5.5.
file d'attente<flotter>Quoi;Quoi.pousser(1.1);Quoi.pousser(2.2);Quoi.pousser(3.3);Quoi.pousser(4.4);Quoi.pousser(5.5);
cout<<Quoi.arrière() << ' ';
retour() const
Lorsque la construction de la file d'attente est précédée de const, l'expression back() const est exécutée à la place de back(). Il est utilisé dans le code suivant, par exemple.
constfile d'attente<flotter>Quoi({1.1, 2.2, 3.3, 4.4, 5.5});cout<<Quoi.arrière() << ' ';
Une référence constante est renvoyée. L'élément n'est pas supprimé de la file d'attente. Avec le const précédent pour la construction de la file d'attente, les éléments de la file d'attente ne peuvent pas être modifiés.
Capacité de la file d'attente
taille() const
- voir au dessus
vide() const
Cela renvoie 1 pour vrai s'il n'y a aucun élément dans la file d'attente, ou 0 pour faux si la file d'attente est vide. Le code suivant illustre cela :
file d'attente<flotter>que1({1.1, 2.2, 3.3, 4.4, 5.5});cout<<que1.vide() << ' ';
file d'attente<flotter>que2;
cout<<que2.vide() << ' ';
La sortie est :
01
Modificateurs de file d'attente
pop ()
Une file d'attente est FIFO, donc tout élément qui doit être supprimé doit être supprimé du haut (tête) de la file d'attente. Cette fonction membre supprime le premier élément sans le retourner. Le code suivant illustre cela :
file d'attente<flotter>Quoi({1.1, 2.2, 3.3, 4.4, 5.5});cout<<Quoi.de face() << ' ';
Quoi.pop();
cout<<Quoi.Taille() << ' ';
La sortie est :
1.14
a.swap(b)
Deux files d'attente peuvent être permutées, comme illustré dans ce segment de code :
file d'attente<flotter>que1({1.1, 2.2, 3.3, 4.4, 5.5});file d'attente<flotter>que2({dix, vingt});
que1.échanger(que2);
cout<< 'Premier élément et taille de que1 :
'<<que1.de face() <<','<<que1.Taille() << ' ';
cout<< 'Premier élément et taille de que2'<<
que2.de face() <<','<<que2.Taille() << ' ';
La sortie est :
Premier élément et taille de que1 : 10, 2
Premier élément et taille de que2 : 1.1, 5
Notez que la longueur d'une file d'attente est augmentée si nécessaire. De plus, les valeurs qui n'avaient pas de remplacements sont remplacées par une valeur par défaut. Les types de données doivent être du même type.
Égalité et opérateurs relationnels pour les files d'attente
Pour les caractères ordinaires en C++, dans l'ordre croissant, les nombres précèdent les lettres majuscules, qui précèdent les lettres minuscules. Le caractère espace vient avant zéro et tous.
Opérateurs d'égalité
Renvoie 1 pour vrai et 0 pour faux.
L'opérateur ==
Renvoie 1 si les deux files d'attente ont la même taille et les éléments correspondants sont égaux ; sinon il renvoie 0. Exemple :
file d'attente<const carboniser*>que1({'type', 'autre chose'});file d'attente<const carboniser*>que2({'méchant'});
entiersur une=que1==que2;
cout<<sur une<< ' ';
La sortie est : 0.
L'opérateur !=
- à l'opposé de ce qui précède. Exemple:
file d'attente<const carboniser*>que1({'type', 'autre chose'});file d'attente<const carboniser*>que2({'méchant'});
entiersur une=que1! =que2;
cout<<sur une<< ' ';
La sortie est : 1.
Opérateurs relationnels
Renvoie 1 pour vrai et 0 pour faux.
Les
Renvoie 1 si la première file d'attente est le sous-ensemble initial de la deuxième file d'attente, les éléments des deux parties égales étant les mêmes et dans le même ordre. Si les deux files d'attente sont de même taille ou de tailles différentes, et se déplaçant de gauche à droite, un élément est rencontré dans la première file d'attente qui est inférieur à l'élément correspondant dans la seconde file d'attente, alors 1 sera toujours renvoyé. Sinon, 0 est renvoyé. Exemple:
file d'attente<const carboniser*>que1({'type', 'autre chose'});file d'attente<const carboniser*>que2({'méchant'});
entiersur une=que1<que2;
cout<<sur une<< ' ';
La sortie est 1. L'opérateur > - à l'opposé de ce qui précède. Exemple: Sortie : 0 Les<= Operator - pareil que Sortie : 1 L'opérateur >= - à l'opposé de ce qui précède. Exemple: Sortie : 0 Une valeur est à un type de données, comme un objet instancié est à une classe. La construction de la file d'attente peut également accepter une classe comme type de données. Le programme suivant illustre cela : La sortie est 5. La liste de file d'attente est techniquement appelée liste chaînée. Il existe deux types de listes chaînées pour la file d'attente : la liste chaînée simple et la liste chaînée double. Un élément de liste chaînée peut être implémenté par une structure de deux membres. Un membre contient un pointeur vers l'élément suivant et l'autre membre contient la donnée (singulier pour les données). Un élément de liste doublement chaîné peut être implémenté par une structure de trois membres. L'élément central contient la référence, tandis que les premier et troisième éléments contiennent des pointeurs vers leurs éléments adjacents. La file d'attente est une structure de données premier entré, premier sorti. Il existe des situations en informatique où les données arrivent sous la forme d'une file d'attente, nécessitant un comportement premier entré, premier sorti. Une ressource dans un ordinateur est tout composant physique ou virtuel de disponibilité limitée. Ils comprennent le processeur, la carte vidéo, le disque dur et la mémoire. Le partage d'une telle ressource nécessite une file d'attente. Les périphériques informatiques doivent interrompre l'ordinateur de temps en temps. Les interruptions doivent être traitées de la même manière qu'elles sont arrivées. Cela nécessite une file d'attente. La file d'attente peut être utilisée, par exemple, pour gérer les fichiers d'application pour un travail, si les fichiers sont stockés dans l'ordinateur. Une file d'attente est une structure de données de liste, qui est soit une liste à chaînage simple, soit une liste à chaînage double. En règle générale, le premier élément qui entre dans la liste est le premier élément à en sortir. C++ fournit une structure de données de file d'attente dans sa bibliothèque standard. Les catégories de fonctions membres et d'opérateurs disponibles pour cette structure sont la construction de file d'attente, l'accès aux éléments de file d'attente, la capacité de file d'attente, les modificateurs de file d'attente et les opérateurs de file d'attente surchargée. Toute structure de données de file d'attente doit fournir au moins les fonctions membres push() et pop(). push() signifie envoyer un nouvel élément à la fin de la file d'attente ; et pop() signifie supprimer l'élément qui se trouve au début de la file d'attente. Malheureusement, en C++, ces fonctions ne renvoient pas la valeur poussée ou sautée. Donc, pour connaître le dernier élément avant de pousser, la fonction extra back() doit être utilisée ; et pour connaître le premier élément avant d'apparaître, la fonction supplémentaire front() doit être utilisée. Une valeur est à un type de données, comme un objet instancié est à une classe. Ainsi, une classe particulière peut être utilisée comme type de données pour l'instanciation du modèle de file d'attente. Différents objets pour la classe deviennent comme des valeurs différentes pour la classe. La file d'attente a des applications sur l'ordinateur. Il peut être utilisé, par exemple, pour gérer les fichiers d'application pour un travail, si les fichiers sont stockés dans l'ordinateur. Chrys
file d'attente<const carboniser*>que2({'méchant'});
entiersur une=que1>que2;
cout<<sur une<< '
';
file d'attente<const carboniser*>que2({'méchant'});
entiersur une=que1<=que2;
cout<<sur une<< '
';
file d'attente<const carboniser*>que2({'méchant'});
entiersur une=que1> =que2;
cout<<sur une<< '
'; Classe et ses objets instanciés
#comprendre
en utilisant l'espace de noms std;
classe TheCla
{
Publique:
entiersur une;
statique carboniserch;
annulerfonction(carbonisernon, const carboniser *p)
{
cout<< 'Il y a ' <<sur une<< 'les livres valent' <<non<<p<< ' dans le magasin.' << '
';
}
statique annuleramusant(carboniserch)
{
si (ch== 'à')
cout<< 'Fonction membre statique officielle' << '
';
}
};
entierprincipale()
{
La Cla obj1;La Cla obj2;La Cla obj3;La Cla obj4;La Cla obj5;
file d'attente<La Cla>Quoi;
Quoi.pousser(obj1);Quoi.pousser(obj2);Quoi.pousser(obj3);Quoi.pousser(obj4);Quoi.pousser(obj5);
cout<<Quoi.Taille() << '
';
revenir 0;
} Liste liée
Applications de la file d'attente
Partage de ressources informatiques
Gestion des interruptions
Gérer les informations.
Conclusion