DOUG LLOYD: Also, wenn Sie haben das Video gesehen auf Stapel, Dies ist wahrscheinlich zu fühlen wie ein bisschen von Déjà-vu. Es ist zu einem sehr ähnlichen Konzept gehen, nur mit einer leichten Drehung auf sie. Wir werden jetzt über Schlangen zu sprechen. So dass eine Warteschlange, ähnlich einem Stapel, eine andere Art von Datenstruktur dass wir verwenden können, um aufrecht zu erhalten Daten in einer organisierten Art und Weise. Ähnlich wie bei einem Stapel, sie eingesetzt werden kann als ein Array oder eine verkettete Liste. Im Gegensatz zu einem Stapel, die Regeln dass wir verwenden, um zu bestimmen, Wenn die Dinge hinzugefügt und aus entfernt eine Warteschlange sind ein bisschen anders. Im Gegensatz zu einem Stapel, der ist eine LIFO-Struktur, last in, first out, eine Warteschlange ein FIFO- Struktur, FIFO, first-in, first out. Jetzt Warteschlangen, werden Sie wahrscheinlich eine Analogie zu Warteschlangen. Wenn Sie schon einmal in der Schlange vor gewesen ein Freizeitpark oder bei einer Bank, es gibt eine Art von Fairness Durchführungsstruktur. Die erste Person in der Schlange vor die Bank ist die erste Person wer bekommt, um die Geld sprechen. 

Es wäre eine Art Rennen nach unten, wenn der einzige Weg, du musst mit dem teller in die sprechen Bank war es, die letzte Person im Einklang zu sein. Jeder will immer würde um die letzte Person in der Linie sein, und die Person, die zuerst da war die gewartet hat, für eine Weile, könnte es für Stunden, und Stunden und Stunden bevor sie eine Chance haben, tatsächlich Geld auf der Bank zurückziehen. Und so Warteschlangen sind eine Art der Fairness Durchführungsstruktur. Aber das bedeutet nicht unbedingt, dass Stacks sind eine schlechte Sache, gerade dass Warteschlangen sind eine weitere Möglichkeit, es zu tun. Also noch einmal eine Warteschlange first in, first aus, im Vergleich zu einem Stapel, die in dem letzten, first out. Ähnlich wie bei einem Stapel, wir haben zwei Operationen dass wir auf Warteschlangen durchführen können. Die Namen sind Enqueue, was hinzuzufügen ist ein neues Element am Ende der Warteschlange, und dequeue, das ist um den ältesten entfernen Element von der Vorderseite der Warteschlange. So werden wir Elemente hinzufügen auf das Ende der Warteschlange, und wir werden Elemente entfernen von der Vorderseite der Warteschlange. Wieder mit dem Stapel, waren wir das Hinzufügen Elemente, die der Oberseite des Stapels und Entfernen von Elementen von der Spitze des Stapels. Also mit Enqueue, es ist das Hinzufügen zu das Ende, das Entfernen von vorne. Also die älteste Sache drin ist immer das nächste, was zu kommen, wenn wir versuchen und aus der Warteschlange entfernt etwas. 

Also noch einmal, mit Warteschlangen, können wir Array-basierte Implementierungen und verknüpfte Liste basierte Implementierungen. Wir sehen uns wieder mit zu beginnen Array-basierte Implementierungen. Die Strukturdefinition sieht ziemlich ähnlich. Wir haben ein anderes Array gibt der Datentypwert, so kann beliebige Datentypen zu halten. Wir sind wieder in Gang zu bedienen Zahlen in diesem Beispiel. 

Und genau wie mit unseren Array-basierte Stack-Implementierung, weil wir mit ein Arrays, die wir unbedingt haben diese Einschränkung, dass C Art der setzt auf uns, die wir es keine Dynamik haben unsere Fähigkeit zu wachsen und schrumpfen Sie das Array. Wir haben zu Beginn entscheiden was ist die maximale Anzahl von Dingen dass wir in diese setzen Warteschlange, und in diesem Fall, Kapazitäten würden einige Pfund sein in unserem Code Konstante definiert. Und für die Zwecke dieser Video wird Kapazität werde 10 sein. 

Wir brauchen, um zu verfolgen die Vorderseite der Warteschlange so wissen wir, welches Element Wir wollen aus der Warteschlange entfernt, und wir müssen auch im Auge zu behalten etwas else-- die Anzahl der Elemente dass wir in unserer Warteschlange. Beachten Sie, dass wir nicht die Verfolgung der am Ende der Warteschlange, so die Größe der Warteschlange. Und der Grund dafür, dass hoffentlich sich etwas klarer in einem Augenblick. Sobald wir abgeschlossen haben Diese Typdefinition, Wir haben einen neuen Datentyp genannt Warteschlange, die wir nun deklarieren Variablen dieses Datentyps. Und etwas verwirrend, habe ich beschlossen, um diese Warteschlange q, der Brief nennen q anstelle des Datentyps q. 

So, hier ist unsere Warteschlange. Es ist eine Struktur. Es enthält drei Mitglieder oder drei Felder, ein Array der Größe Kapazität. In diesem Fall wird die Kapazität 10. Und das Array gehen, um ganze Zahlen zu halten. In grün ist der vor unserem Warteschlange, die nächste Element entfernt werden soll, und in roter wird die Größe der Warteschlange, wie viele Elemente liegen noch in der Warteschlange vorhanden sind. Also, wenn wir sagen, q.front equals 0 und q.size Größe entspricht 0-- Wir setzen 0s in diesen Bereichen. Und an diesem Punkt sind wir ziemlich viel bereit, mit unseren Warteschlange zu beginnen. 

So ist der erste Betrieb können wir durchzuführen ist, etwas einzureihen, um ein neues Element hinzuzufügen das Ende der Warteschlange. Nun, was brauchen wir, um machen im allgemeinen Fall? Nun diese Funktion Enqueue Bedürfnisse einen Zeiger auf unsere Warteschlange zu akzeptieren. Auch wenn wir erklärt hatten unsere Warteschlange global, wir würden nicht dies tun müssen unbedingt, aber im Allgemeinen haben wir müssen Zeigern akzeptieren Datenstrukturen so, weil sonst wir durch value-- wir sind vorbei Einleiten von Kopien der Warteschlange, und so sind wir nicht wirklich zu ändern die Schlange, die wir beabsichtigen, zu ändern. 

Das andere, was es tun muss, ist zu akzeptieren ein Datenelement des entsprechenden Typs. Auch in diesem Fall ist es gehen, um ganze Zahlen sein, aber man konnte beliebig deklarieren Sie den Datentyp als Wert und nutzen diese im Allgemeinen. Das ist das Element, das wir zu Enqueue möchten, Wir wollen bis zum Ende der Warteschlange hinzuzufügen. Dann werden wir wirklich wollen, stellen, dass die Daten in der Warteschlange. In diesem Fall wird dem Einlegen in das korrekte Position unseres Array, und dann, um die Größe ändern möchten wir der Schlange, wie viele Elemente wir Aktuell haben. 

Also lassen Sie uns loslegen. Hier ist wiederum, dass die allgemeine Form Funktionsdeklaration für das, was Enqueue aussehen könnte. Und es geht los. Lassen Sie uns die Anzahl Enqueue 28 in die Warteschlange. Also, was sollen wir tun? Nun, die vor unserem Warteschlange bei 0 und die Größe unseres Warteschlange ist bei 0, und so wollen wir wahrscheinlich zu setzen die Zahl 28 in Array-Element-Nummer 0, oder? Also haben wir jetzt, dass dort platziert. So, jetzt, was müssen wir ändern? Wir wissen nicht ändern möchten die Spitze der Warteschlange, weil wir, in welchem ​​Element wissen wollen wir brauchen, um später aus der Warteschlange entfernt. Also der Grund, warum wir dort vorn ist eine Art Indikator für was ist das älteste, was in der Anordnung. Nun die älteste Sache der array-- in der Tat, das einzige, was in dem Feld rechts now-- ist 28, das ist, bei Matrixort 0. So dass wir nicht wollen, zu ändern, dass die grüne Nummer, denn das ist das älteste Element. Vielmehr um die Größe ändern wollen wir. Also in diesem Fall, wir Schrittweite 1. 

Jetzt eine allgemeine Art von Vorstellung davon, wo die nächste Element wird sich in einer Warteschlange zu gehen wird, jene zwei Zahlen zu addieren zusammen, vorne und Größe, und das werden Sie sagen, wo die nächste Element in der Warteschlange gehen wird. So, jetzt lassen Sie uns Enqueue eine andere Nummer. Lassen Sie uns Enqueue 33. So 33 wird sich in gehen Matrixort 0 plus 1. Also in diesem Fall, es geht in Feldposition 1 zu gehen, und jetzt die Größe unserer Warteschlange ist 2. 

Auch hier werden wir nicht ändern die vor unserem Warteschlange, weil 28 ist immer noch die älteste Element, und wir zu-- möchten, wenn wir irgendwann zum Entfernen aus Warteschlangen, Entfernen von Elementen aus dieser Warteschlange, wollen wir wissen wo das älteste Element ist. Und so müssen wir immer zu pflegen einige Indikator, wo das ist. Also das ist, was der 0 gibt es für. Das ist, was vorne ist für. 

Lassen Sie uns in Enqueue ein weiteres Element, 19. Ich bin sicher, dass Sie sich vorstellen können wo 19 gehen wird. Es wird in zu gehen Array Platznummer 2. Das ist 0 plus 2. Und jetzt die Größe unseres Warteschlange 3. Wir haben 3 Elemente darin. Also, wenn wir uns, und wir werden nicht gerade jetzt, Enqueue ein weiteres Element, wäre es in ein Array Standort gehen Nummer 3, und die Größe der Warteschlange würde 4 sein. Also haben wir mehrere Elemente jetzt eingereiht. Lassen Sie uns jetzt beginnen, sie zu entfernen. Lasst Warteschlange entfernt sie aus der Warteschlange. 

So ähnlich wie Pop, welche Art ist des Analog davon für Stapel, dequeue muss eine akzeptieren Zeiger auf den queue-- wieder es sei denn, es ist global deklariert. Nun, um die Position ändern möchten wir der Vorderseite der Warteschlange. Dies ist, wo es irgendwie geht ins Spiel, dass Front variable, denn wenn wir entfernen ein Element, wir wollen, um es auf die nächste älteste Element zu bewegen. 

Dann sinken wollen wir die Größe der Warteschlange, und dann, um den Wert zurückgeben möchten wir daß aus der Warteschlange entfernt. Auch hier wollen wir nicht nur verwerfen. Wir werden vermutlich extra es von der queue-- wir sind Entfernen aus Warteschlangen, weil wir darum kümmern. So wollen wir diese Funktion, um zurückzukehren ein Datenelement vom Typ Wert. Auch in diesem Fall ist der Wert Integer. 

So, jetzt lassen Sie uns etwas aus der Warteschlange entfernt. Lassen Sie uns ein Element aus der Warteschlange zu entfernen. Wenn wir sagen, int x gleich & q, Und-Zeichen Q-- wieder, das ist ein Zeiger auf diesen Q-Daten structure-- welchem ​​Element wird sich aus der Warteschlange entfernt werden? In diesem Fall, weil es ein erstes in, first out Datenstruktur, FIFO, das erste, was wir uns in diese setzen Schlange war 28, und so in diesem Fall, wir werden 28 von nehmen die Schlange, nicht 19, das, was wir getan hätte, wenn es sich um eine Stack. Wir werden 28 aus der Warteschlange zu nehmen. 

Ähnlich dem, was wir haben ein Stapel, wir sind nicht wirklich gehen, um zu löschen 28 aus der Schlange selbst, wir sind gerade dabei, Art von so tun, es ist nicht da. Also, es wird dort bleiben im Speicher, aber wir sind gehen, um Art zu ignorieren, indem Sie die anderen beiden Felder der Q-Daten Struktur. Wir werden die Front ändern. Q.front geht jetzt um 1 sein, denn das ist jetzt das älteste Element, das wir in haben unsere Warteschlange, denn wir haben bereits entfernt 28, was war der ehemalige älteste Element. 

Und nun ändern möchten wir die Größe der Warteschlange auf zwei Elemente anstelle von drei. Jetzt erinnere früher sagte ich, als wir wollen Elemente zur Warteschlange hinzuzufügen, wir setzen es in einem Array Ort das ist die Summe der vorderen und Größe. Also in diesem Fall, wir sind noch dabei darauf das nächste Element in der Warteschlange, in Feldposition 3 und wir werden, dass in einem zweiten zu sehen. 

Also haben wir jetzt aus der Warteschlange entfernt haben unsere das erste Element aus der Warteschlange. Lass uns das nochmal machen. Lassen Sie uns eine andere zu entfernen Element aus der Warteschlange. In dem Fall, der aktuelle ältesten Element-Array Standort 1. Das ist, was sagt uns, q.front. Das grüne Feld zeigt uns, dass das ist das älteste Element. Und so wird x 33 geworden. Wir werden nur irgendwie vergessen dass 33 in der Anordnung vorhanden ist, und wir werden jetzt die sagen, dass neue älteste Element in der Warteschlange zumin Matrixort 2 und der Größe der Warteschlange, die Anzahl der Elemente Wir haben in der Warteschlange ist 1. Lassen Sie uns jetzt Enqueue etwas, und ich Art vor einer Sekunde gab diese weg, aber wenn wir auf 40 in die setzen wollen Warteschlange, wo ist 40 hingehen? Nun wir haben es setzen in q.front zzgl Queue-Größe, und so ist es sinnvoll ist, tatsächlich zu 40 ablegen. Jetzt bemerken, dass bei Irgendwann werden wir bis zum Ende des zu erhalten unser Angebot innerhalb von q, aber das ausgeblendet 28 und 33-- sie tatsächlich, technisch Freiflächen, nicht wahr? Und so können wir eventually-- dass Regel Hinzufügen die beiden together-- wir kann schließlich müssen mod durch die Größe der Kapazität damit wir Wrap-around. 

Wenn wir also Element erhalten Nummer 10, wenn wir es in Elementnummer 10 zu ersetzen, würden wir tatsächlich legte es in Feldposition 0. Und wenn wir wurden zu gehen Array location-- mich entschuldigen, wenn wir sie zusammen hinzugefügt, und wir haben Nummer 11 wäre, wo wir müssten setzen es, die in diesem array-- existiert es wäre aus gehen von Grenzen. Wir konnten um 10 MOD und setzen in Feldposition 1. Also das ist, wie Warteschlangen arbeiten. Sie sind immer gehen, um von links gehen nach rechts und möglicherweise herum wickeln. Und Sie wissen, dass sie voll, wenn Größe, dass rotes Feld, gleich Kapazität. Und so, nachdem wir 40, den Mehr Warteschlange, gut, was müssen wir tun? Nun, das älteste Element in der Warteschlange noch 19 so dass wir nicht ändern wollen die Spitze der Warteschlange, aber jetzt haben wir zwei haben Elemente in der Warteschlange, und so zu erhöhen, wollen wir unsere Größe von 1 bis 2. 

Das ist ziemlich viel es mit Arbeit mit Array-basierte Warteschlangen, und ähnlich zu stapeln, es gibt auch eine Möglichkeit, eine Warteschlange als eine verknüpfte Liste zu implementieren. Nun, wenn diese Datenstruktur Typ kommt mir bekannt vor, Sie ist es. Es ist nicht eine einfach verkettete Liste, es ist eine doppelt verknüpfte Liste. Und nun Nebenbei ist es tatsächlich möglich zu implementieren eine Schlange als eine einfach verkettete Liste, aber Ich denke, dass in Bezug auf die Visualisierung, es könnte tatsächlich helfen, um zu sehen dies als eine doppelt verknüpfte Liste. Aber es ist auf jeden Fall möglich, tun dies als eine einfach verkettete Liste. 

Lassen Sie uns also einen Blick auf was diese aussehen könnte. Wenn wir wollen, enquue-- so jetzt, wieder sind wir Umstellung auf eine verknüpfte Liste basierend auf das Modell. Wenn wir Enqueue, wir wollen um ein neues Element hinzuzufügen, gut was müssen wir tun? Nun, zunächst einmal, weil die wir hinzufügen, um das Ende und Entfernen von der Anfang, wir wahrscheinlich wollen Zeigern, um sowohl die Aufrechterhaltung Kopf und der Schwanz des verknüpften Liste? Schwanz als eine andere Bezeichnung für das Ende der verketteten Liste, das letzte Element in der verketteten Liste. Und diese werden wahrscheinlich, wieder, von Vorteil sein, uns wenn sie globale Variablen. Aber jetzt, wenn wir einen neuen hinzufügen möchten Element, was müssen wir tun? Was wir gerade [? Malak?] oder dynamisch zuzuweisen unserem neuen Knoten für uns selbst. Und dann, wie gerade, wenn wir irgendeine hinzufügen Element zu einer doppelt verketteten Liste, die wir, einfach nur, um zu sortieren von-- diese letzten drei Schritte hier sind nur alles um bewegte die Zeiger in der richtigen Art und Weise so dass das Element wird hinzugefügt die Kette ohne die Kette oder machen eine Art von Fehler oder mit einer gewissen Art von Unfall passieren, wobei wir versehentlich Orphan einige Elemente unserer Warteschlange. Hier ist, was diese aussehen könnte. Wir wollen, um das Element hinzuzufügen 10 an das Ende dieser Warteschlange. Also das älteste Element hier wird durch den Kopf dargestellt. Das ist das erste, was wir setzen in diesem hypothetischen Warteschlange hier. Und Schwanz, 13, ist die zuletzt hinzugefügten Elements. Und so, wenn wir in 10 einreihen wollen diese Warteschlange, wir wollen es nach 13 gesetzt. Und so werden wir dynamisch Speicherplatz zuweisen für einen neuen Knoten und überprüfen Sie null, um sicherzustellen, wir haben nicht einen Speicherfehler. Dann werden wir zu gehen platzieren 10 in diesem Knoten, und jetzt müssen wir vorsichtig sein, darüber, wie wir organisieren Zeigern so dass wir die Kette nicht brechen. 

Wir können 10 bisherige Feld gesetzt auf den alten Schwanz zurückweisen, und seit '10 wird die neue Schwanz zu einem bestimmten Zeitpunkt durch die Zeit, alle diese Ketten verbunden sind, nichts wird kommen nach 10 jetzt. Und so 10 der nächste Zeiger wird darauf auf null, und dann, nachdem wir dies tun, nachdem wir Verbindung 10 nach hinten an die Kette, können wir den alten Kopf, oder Entschuldigung zu nehmen mich, die alte Ende der Warteschlange. Der alte Ende der Warteschlange, 13, und machen es bis 10 zeigen. Und jetzt, an diesem Punkt, wir haben reiht die Nummer 10 in dieser Warteschlange. Alles, was wir jetzt tun müssen, ist gerade bewegen Schwanz bis 10 statt bis 13 zeigen. 

Entfernen aus Warteschlangen ist eigentlich sehr ähnlich zu knallen aus einem Stapel, die ist als eine verknüpfte Liste implementiert wenn Sie die Stapel-Video gesehen habe. Alles, was wir tun müssen, ist ab dem beginnen, finden Sie das zweite Element, befreien das erste Element, und bewegen Sie den Kopf bis zu dem zweiten Element zu verweisen. Wahrscheinlich besser, es zu visualisieren nur um zusätzliche klaren darüber sein. Also hier ist unsere Warteschlange wieder. 12 ist das älteste Element in unserer Warteschlange, den Kopf. 10 ist das neueste Element in unserer Warteschlange unsere Schwanz. 

Und so, wenn wir wollen, , ein Element aus der Warteschlange entfernt, wollen wir das älteste Element zu entfernen. Also, was machen wir? Nun setzen wir einen Durchlauf-Zeiger das beginnt an der Spitze, und wir es so zu bewegen, dass es Punkte an dem zweiten Element Dies queue-- etwas sagen trav gleich trav Pfeil neben beispielsweise würde trav dort zu bewegen, um darauf hinzuweisen 15, die, nach einer 12 aus der Warteschlange entfernt, oder nach dem entfernen wir 12, wird zu der damals älteste Element. 

Jetzt haben wir einen Halt an der zum ersten Mal Element über den Zeiger Kopf und das zweite Element über den Zeiger trav. Wir können jetzt kostenlos Kopf, und dann können wir sagen, es kommt nichts vor dem 15. mehr. So können wir 15 früheren ändern Zeiger auf Punkt auf null, und wir nur den Kopf bewegen vorbei. Und wir gehen. Jetzt müssen wir erfolgreich aus der Warteschlange entfernt 12, und jetzt sind wir haben eine andere Warteschlange der 4 Elemente. Das ist so ziemlich alles, gibt es Warteschlangen, sowohl Array-basierte und verketteten Liste basiert. Ich bin Doug Lloyd. Dies CS 50.