DOUG LLOYD: Donc, si vous avez regardé la vidéo sur la pile, Cela va probablement se sentir comme un peu de déjà-vu. Il va à un concept très similaire, seulement avec une légère torsion sur elle. Nous allons maintenant parler des files d'attente. Donc, une file d'attente, semblable à une pile, est un autre type de structure de données que nous pouvons utiliser pour maintenir les données d'une manière organisée. Semblable à une pile, elle peut être réalisée comme un tableau ou une liste chaînée. Contrairement à une pile, les règles que nous utilisons pour déterminer Quand les choses deviennent ajoutés ou supprimés une file d'attente sont un peu différent. Contrairement à une pile, qui est une structure LIFO, dernier entré, premier sorti, une file d'attente est une FIFO structure FIFO, premier entré, premier sorti. Maintenant, les files d'attente, vous avez probablement avoir une analogie de files d'attente. Si vous avez déjà été dans la ligne à un parc d'attractions ou dans une banque, il ya une sorte de l'équité la mise en oeuvre structure. La première personne en ligne à la banque est la première personne qui arrive à parler à la caissière. 

Ce serait une sorte de course vers le bas si le seul moyen vous avez à parler à la caissière au banque devait être la dernière personne en ligne. Tout le monde voudrait toujours être la dernière personne en ligne, et la personne qui était là en premier qui a été en attente pendant un certain temps, pourrait être là pendant des heures, et des heures, et des heures avant qu'ils aient une chance de réellement retirer de l'argent à la banque. Et si les files d'attente sont en quelque sorte de la mise en œuvre de l'équité structure. Mais cela ne signifie pas nécessairement que les piles sont une mauvaise chose, juste que les files d'attente sont une autre façon de le faire. Donc encore une fois une file d'attente est premier entré, premier sur, par rapport à une pile qui dure en, premier sorti. Semblable à une pile, nous avons deux opérations que nous pouvons effectuer sur les files d'attente. Les noms sont en file d'attente, qui consiste à ajouter un nouvel élément à la fin de la file d'attente, et dequeue, qui est pour enlever la plus ancienne élément de l'avant de la file d'attente. Donc, nous allons ajouter des éléments sur l'extrémité de la file d'attente, et nous allons supprimer des éléments à partir de l'avant de la file d'attente. Encore une fois, avec la pile, nous avons ajouté éléments au sommet de la pile et des éléments de retirer à partir du haut de la pile. Donc, avec enqueue, il est à ajouter à Finalement, l'élimination de l'avant. Ainsi, la plus vieille chose là est toujours la chose suivante de sortir si nous essayons et dequeue quelque chose. 

Donc encore une fois, avec des files d'attente, nous pouvons implémentations sur baie et liste liée implémentations basées. Nous allons commencer à nouveau avec implémentations sur les baies. La définition de la structure semble assez similaire. Nous avons un autre tableau il de la valeur de type de données, de sorte qu'il peut contenir des types de données arbitraires. Nous allons utiliser à nouveau des nombres entiers dans cet exemple. 

Et tout comme avec notre la mise en œuvre de la pile basée sur la baie, parce que nous sommes en utilisant un tableau, nous avons nécessairement avoir cette limitation que C genre du fait respecter sur nous, ce qui est nous ne pas avoir de dynamisme dans notre capacité à croître et rétrécir le tableau. Nous devons décider au début Quel est le nombre maximum de choses que nous pouvons mettre dans cette file d'attente, et dans ce cas, la capacité serait une livre constante définie dans notre code. Et pour les fins de la présente vidéo, la capacité va être 10. 

Nous avons besoin de garder une trace de la face de la file d'attente nous savons donc quel élément nous voulons dequeue, et nous avons aussi besoin de garder une trace de quelque chose else-- le nombre d'éléments que nous avons dans notre file d'attente. Remarquez que nous ne sommes pas garder la trace de la fin de la file d'attente, juste la taille de la file d'attente. Et la raison de qui nous l'espérons devenu un peu plus clair dans un instant. Une fois que nous avons terminé cette définition de type, nous avons un nouveau type de données appelée file d'attente, ce qui nous pouvons maintenant déclarer des variables de ce type de données. Et peu à confusion, je me suis décidé d'appeler cette file d'attente q, la lettre q à la place du type de données q. 

Donc voici notre file d'attente. Il est d'une structure. Il contient trois membres ou trois champs, un tableau de taille CAPACITÉ. Dans ce cas, la capacité est de 10. Et ce tableau est va tenir entiers. Dans le vert est la face de notre file d'attente, la l'élément suivant à être enlevé, et en rouge sera la taille de la file d'attente, combien d'éléments sont actuellement qui sont dans la file d'attente. Donc, si nous disons égaux q.front 0, et la taille de q.size égale 0-- nous mettons 0s dans ces domaines. Et à ce moment, nous sommes à peu près prêt à commencer à travailler avec notre file d'attente. 

Donc, la première opération que nous pouvons à effectuer est en file d'attente de quelque chose, pour ajouter un nouvel élément à la fin de la file d'attente. Eh bien ce que devons-nous faire dans le cas général? Eh bien cette fonction en file d'attente besoins à accepter un pointeur à notre file d'attente. Encore une fois, si nous avions déclaré notre file d'attente à l'échelle mondiale, nous ne serions pas besoin de faire cela nécessairement, mais en général, nous besoin d'accepter des pointeurs de structures de données comme ça, parce que sinon, nous passons par value-- nous sommes passant dans les copies de la file d'attente, et donc nous ne sommes pas réellement changer la file d'attente que nous avons l'intention de changer. 

L'autre chose qu'il doit faire est d'accepter un élément de données du type approprié. Là encore, dans ce cas, il est va être entiers, Mais vous pourriez arbitrairement déclarer le type de données que la valeur et utiliser ce plus généralement. Voilà l'élément que nous voulons en file d'attente, nous voulons ajouter à la fin de la file d'attente. Ensuite, nous voulons effectivement placer ces données dans la file d'attente. Dans ce cas, le plaçant dans le emplacement correct de notre tableau, et ensuite nous voulons changer la taille de la file d'attente, le nombre d'éléments nous ont actuellement. 

Donc, nous allons commencer. Voici, encore une fois, que le général déclaration de fonction de forme pour ce enqueue pourrait ressembler. Et c'est reparti. Disons ENQUEUE le nombre 28 dans la file d'attente. Alors qu'est-ce qu'on va faire? Eh bien, la face de notre file d'attente est à 0, et la taille de notre file d'attente est à 0, et donc nous voulons probablement de mettre le nombre 28 dans le tableau numéro d'élément 0, non? Donc, nous avons désormais mis ça là. Alors maintenant, que devons-nous changer? Nous ne voulons pas changer l'avant de la file d'attente, parce que nous voulons savoir ce que l'élément nous pourrions avoir besoin de dequeue tard. Donc, la raison pour laquelle nous avons avant il est une sorte d'indicateur de ce qui est la plus vieille chose dans le tableau. Eh bien, la plus vieille chose dans le array-- dans fait, la seule chose dans le tableau à droite est maintenant-- 28, qui est à l'emplacement de tableau 0. Donc, nous ne voulons pas changer ce numéro vert, parce que ce l'élément le plus ancien. Au contraire, nous voulons changer la taille. Donc dans ce cas, nous allons incrémenter la taille à 1. 

Maintenant, une sorte de général idée d'où le élément suivant va aller dans une file d'attente est d'ajouter ces deux nombres ensemble, avant et taille, et que vais vous dire où la prochaine élément dans la file d'attente va aller. Alors maintenant, nous allons ENQUEUE un autre numéro. Disons ENQUEUE 33. Donc 33 va aller dans Lieu de gamme 0 + 1. Donc dans ce cas, il va pour aller dans l'emplacement du tableau 1, et maintenant la taille de notre file d'attente est de 2. 

Encore une fois, nous ne sommes pas changer l'avant de notre file d'attente, parce que 28 est toujours le le plus ancien élément, et nous to-- veulent quand nous obtenons finalement à dequeuing, la suppression d'éléments à partir de cette file d'attente, nous voulons savoir où l'élément le plus ancien est. Et donc nous avons toujours besoin de maintenir un indicateur de l'endroit où ce qui est. Voilà ce que le 0 est là pour cela. Voilà ce que l'avant est là pour cela. 

Voyons dans enqueue un élément de plus, 19. Je suis sûr que vous pouvez deviner où 19 va aller. Il va aller dans tableau emplacement numéro 2. Voilà plus 2 0. Et maintenant, la taille de notre file d'attente est de 3. Nous avons 3 éléments en elle. Donc, si nous devions, et on ne va pas à ce moment, un autre élément en file d'attente, il irait dans l'emplacement de tableau Numéro 3, et la taille de notre file d'attente serait 4. Nous avons donc mis en file plusieurs éléments maintenant. Maintenant, nous allons commencer à les retirer. Donnons-leur DEQUEUE de la file. 

Si semblable à la pop, qui est une sorte de l'analogue de ce pour les piles, dequeue doit accepter un pointeur vers le nouveau queue--, sauf si elle est déclarée à l'échelle mondiale. Maintenant, nous voulons changer l'emplacement de l'avant de la file d'attente. Ceci est où il vient sorte de en jeu, cette variable avant, car une fois que nous enlevons un élément, nous voulons pour le déplacer vers le prochain élément le plus ancien. 

Ensuite, nous voulons diminuer la taille de la file d'attente, et ensuite nous voulons retourner la valeur qui a été retiré de la file d'attente. Encore une fois, nous ne voulons pas simplement le jeter. Nous vraisemblablement extrayons à partir de la queue-- nous sommes dequeuing parce que nous nous soucions de lui. Donc, nous voulons cette fonction pour revenir un élément de données d'une valeur de type. Encore une fois, dans ce cas, la valeur est entier. 

Alors maintenant, nous allons DEQUEUE quelque chose. Enlevons un élément de la file d'attente. Si nous disons int x est égal & q, esperluette q-- nouveau ce est un pointeur vers ces données q structure-- quel élément va être dequeued? Dans ce cas, parce qu'il est un premier entré, premier sorti structure de données, FIFO, la première chose que nous mettons dans ce file d'attente était de 28, et dans ce cas, nous allons prendre 28 sur la file d'attente, et non pas 19, ce qui est nous aurions fait si cela avait une pile. Nous allons prendre 28 hors de la file d'attente. 

Semblable à ce que nous avons fait avec une pile, nous ne sommes pas réellement va supprimer 28 à partir de la file d'attente elle-même, nous allons juste genre de prétendre qu'il n'y est pas. Donc il va y rester dans la mémoire, mais nous sommes juste aller au genre de l'ignorer en déplaçant les deux autres domaines de nos données q la structure. Nous allons changer l'avant. Q.front va maintenant être 1, car cela est maintenant l'élément le plus ancien que nous avons dans notre file d'attente, parce que nous avons déjà enlevé 28, qui était l'ancien élément le plus ancien. 

Et maintenant, nous voulons changer la taille de la file d'attente à deux éléments au lieu de trois. Maintenant, rappelez-tôt je l'ai dit lorsque nous vouloir ajouter des éléments à la file d'attente, on le met dans une situation de tableau qui est la somme de l'avant et de taille. Donc dans ce cas, nous sommes encore en mettant il, l'élément suivant dans la file d'attente, dans l'emplacement du tableau 3, et nous verrons que, dans une seconde. 

Donc, nous avons maintenant notre dequeued premier élément de la file. Faisons le encore. Enlevons autre élément de la file d'attente. Dans le cas, le courant le plus ancien élément est l'emplacement du tableau 1. Voilà ce que nous dit q.front. Cette boîte verte nous dit que qui est l'élément le plus ancien. Et donc, deviendra x 33. Nous allons juste genre de oublions qui 33 existe dans le tableau, et nous disons que maintenant, la nouveau plus ancien élément de la file d'attente est au tableau localité 2, et de la taille de la file d'attente, le nombre d'éléments nous avons dans la file d'attente, est 1. Maintenant, nous allons ENQUEUE quelque chose, et je sorte de donné cette distance il ya une seconde, mais si nous voulons mettre 40 dans la file d'attente, où est 40 va aller? Eh bien, nous avons été le mettons en plus de file d'attente q.front taille, et il fait donc sens pour effectivement de mettre 40 ici. Maintenant, remarquez qu'au un certain point, nous allons se rendre à la fin de notre tableau à l'intérieur de q, mais fanée sur 28 et 33-- ils sont en fait, techniquement espaces ouverts, non? Et donc, nous pouvons eventually-- cette règle d'ajouter ces deux together-- nous pouvons éventuellement mod besoin de par la taille de la capacité afin que nous puissions envelopper. 

Donc, si nous arrivons à l'élément Numéro 10, si nous sommes remplaçant dans l'élément numéro 10, nous serions effectivement le mettre dans un endroit de tableau 0. Et si nous allions tableau location-- excusez-moi, si nous les avons ajoutés ensemble, et nous sommes arrivés à nombre 11 serait le cas où nous aurions à mettre , ce qui ne existe pas dans ce array-- ce serait aller en dehors des limites. Nous pourrions mod de 10 et de mettre dans l'emplacement du tableau 1. Voilà donc comment fonctionnent les files d'attente. Ils vont toujours aller de gauche à droite à droite et éventuellement enrouler autour. Et vous savez qu'ils sont complète si la taille, cette boîte rouge, devient égale à la capacité. Et donc après nous avons ajouté 40 à la file d'attente, ainsi que devons-nous faire? Eh bien, l'élément le plus ancien dans la file d'attente est toujours 19, de sorte que nous ne voulons pas changer l'avant de la file d'attente, mais maintenant nous avons deux éléments dans la file d'attente, et donc nous voulons augmenter notre taille de 1 à 2. 

Voilà à peu près tout avec travailler avec des files d'attente sur les baies, et semblable à empiler, il ya également un moyen de mettre en œuvre une file d'attente comme une liste chaînée. Or, si ce type de structure de données semble familier pour vous, il est. Il est pas une liste chaînée, il est une liste doublement chaînée. Et maintenant, comme un côté, il est effectivement possible de mettre en œuvre une file d'attente comme une liste chaînée, mais Je pense en termes de visualisation, il fait pourrait aider à voir cela comme une liste doublement chaînée. Mais il est certainement possible de faire cela comme une liste chaînée. 

Donc, nous allons jeter un oeil à ce que cela pourrait ressembler. Si nous voulons enquue-- alors maintenant, nous sommes à nouveau le passage à une liste chaînée modèle basé ici. Si nous voulons en file d'attente, nous voulons pour ajouter un nouvel élément, ainsi Que devons-nous faire? Eh bien, tout d'abord, parce que nous ajoutons à la fin et l'élimination de la commencer, nous avons probablement veulent maintenir pointeurs à la fois le la tête et la queue de la liste chaînée? Tail être un autre terme pour la fin de la liste liée, le dernier élément de la liste chaînée. Et ce sera probablement, encore une fois, être bénéfique pour nous si elles sont des variables globales. Mais maintenant, si nous voulons ajouter un nouveau élément que devons-nous faire? Ce que nous venons [? Malak?] ou dynamiquement allouer notre nouveau noeud pour nous-mêmes. Et puis, tout comme lorsque nous ajoutons tout élément à une liste que nous avons doublement chaînée, suffit de trier de-- ces trois dernières étapes ici sont juste tout sur le déplacement du pointeurs dans le bon sens de sorte que l'élément est ajouté à la chaîne sans rupture de la chaîne ou de faire une sorte de erreur ou d'avoir une sorte d'accident arriver lequel nous avons accidentellement orphelin quelques éléments de notre file d'attente. Voici ce que cela pourrait ressembler. Nous voulons ajouter l'élément 10 à la fin de cette file d'attente. Donc, l'élément le plus ancien ici est représenté par la tête. Voilà la première chose que nous avons mis dans cette file d'attente hypothétique ici. Et la queue, 13, est le plus élément récemment ajouté. Et si nous voulons en file d'attente dans 10 cette file d'attente, nous voulons le mettre après le 13. Et donc nous allons dynamiquement allouer de l'espace pour un nouveau noeud et vérifier null pour vous assurer nous ne disposons pas d'une défaillance de la mémoire. Ensuite, nous allons placer 10 dans ce nœud, et maintenant nous devons être prudents sur la façon dont nous organisons des pointeurs afin de ne pas briser la chaîne. 

Nous pouvons mettre en champ précédent de 10 pour pointer à la vieille queue, et depuis '10 sera le nouvelle queue à un certain point au moment où l'ensemble de ces les chaînes sont connectés, rien ne va à venir après 10 dès maintenant. Et donc la prochaine pointeur de 10 pointera à null, et puis après nous faisons cela, après que nous ayons 10 vers l'arrière reliée à la chaîne, nous pouvons prendre la vieille tête, ou, excuse moi, la vieille queue de la file d'attente. Le vieux fin de la file d'attente, 13, et le faire pointer vers 10. Et maintenant, à ce stade, nous avons en file d'attente le numéro 10 dans cette file d'attente. Tout ce que nous devons faire maintenant est simplement déplacer le queue pour pointer sur la place de 10 à 13. 

Est en fait dequeuing très similaire à éclater à partir d'une pile qui est mis en œuvre comme une liste chaînée si vous avez vu la vidéo des piles. Tout ce que nous devons faire est de commencer à la commencer, trouvez le deuxième élément, libérer le premier élément, et puis déplacez la tête pour pointer vers le second élément. Probablement mieux le visualiser juste pour être très clair à ce sujet. Alors, voici à nouveau notre file d'attente. 12 est l'élément le plus ancien dans notre file d'attente, la tête. 10 est l'élément le plus récent dans notre file d'attente, notre queue. 

Et donc quand nous voulons dequeue à un élément, nous voulons supprimer l'élément le plus ancien. Alors que faisons-nous? Eh bien nous avons mis un pointeur de parcours qui commence à la tête, et nous nous déplaçons pour qu'il des points sur le second élément de cette queue-- quelque chose en disant trav égal trav flèche à côté, par exemple, ferait passer trav là pour pointer vers 15, qui, après nous DEQUEUE 12, ou après nous enlevons 12, sera devenu l'élément puis plus ancienne. 

Maintenant, nous avons une emprise sur le premier élément via la tête de pointeur et le second élément via le pointeur de trav. Nous pouvons tête maintenant libre, et alors nous pouvons rien ne vient dire avant le 15 plus. Donc, nous pouvons changer de 15 précédente pointeur pour pointer vers null, et nous passons juste la tête au-dessus. Et là nous allons. Maintenant, nous avons avec succès dequeued 12, et maintenant nous avoir une autre file d'attente de 4 éléments. Voilà à peu près tout il ya des files d'attente, à la fois basée sur la baie et la liste chaînée base. Je suis Doug Lloyd. Ceci est 50 CS.