1 00:00:00,000 --> 00:00:05,204 2 00:00:05,204 --> 00:00:07,370 DOUG LLOYD: Also, wenn Sie haben das Video gesehen auf Stapel, 3 00:00:07,370 --> 00:00:09,870 Dies ist wahrscheinlich zu fühlen wie ein bisschen von Déjà-vu. 4 00:00:09,870 --> 00:00:13,850 Es ist zu einem sehr ähnlichen Konzept gehen, nur mit einer leichten Drehung auf sie. 5 00:00:13,850 --> 00:00:15,530 Wir werden jetzt über Schlangen zu sprechen. 6 00:00:15,530 --> 00:00:19,350 So dass eine Warteschlange, ähnlich einem Stapel, eine andere Art von Datenstruktur 7 00:00:19,350 --> 00:00:22,412 dass wir verwenden können, um aufrecht zu erhalten Daten in einer organisierten Art und Weise. 8 00:00:22,412 --> 00:00:24,120 Ähnlich wie bei einem Stapel, sie eingesetzt werden kann 9 00:00:24,120 --> 00:00:27,000 als ein Array oder eine verkettete Liste. 10 00:00:27,000 --> 00:00:30,320 Im Gegensatz zu einem Stapel, die Regeln dass wir verwenden, um zu bestimmen, 11 00:00:30,320 --> 00:00:34,210 Wenn die Dinge hinzugefügt und aus entfernt eine Warteschlange sind ein bisschen anders. 12 00:00:34,210 --> 00:00:36,590 >> Im Gegensatz zu einem Stapel, der ist eine LIFO-Struktur, 13 00:00:36,590 --> 00:00:45,610 last in, first out, eine Warteschlange ein FIFO- Struktur, FIFO, first-in, first out. 14 00:00:45,610 --> 00:00:49,320 Jetzt Warteschlangen, werden Sie wahrscheinlich eine Analogie zu Warteschlangen. 15 00:00:49,320 --> 00:00:52,820 Wenn Sie schon einmal in der Schlange vor gewesen ein Freizeitpark oder bei einer Bank, 16 00:00:52,820 --> 00:00:56,430 es gibt eine Art von Fairness Durchführungsstruktur. 17 00:00:56,430 --> 00:00:59,160 Die erste Person in der Schlange vor die Bank ist die erste Person 18 00:00:59,160 --> 00:01:00,760 wer bekommt, um die Geld sprechen. 19 00:01:00,760 --> 00:01:03,522 >> Es wäre eine Art Rennen nach unten, wenn der einzige Weg, 20 00:01:03,522 --> 00:01:06,730 du musst mit dem teller in die sprechen Bank war es, die letzte Person im Einklang zu sein. 21 00:01:06,730 --> 00:01:09,146 Jeder will immer würde um die letzte Person in der Linie sein, 22 00:01:09,146 --> 00:01:12,580 und die Person, die zuerst da war die gewartet hat, für eine Weile, 23 00:01:12,580 --> 00:01:14,715 könnte es für Stunden, und Stunden und Stunden 24 00:01:14,715 --> 00:01:17,590 bevor sie eine Chance haben, tatsächlich Geld auf der Bank zurückziehen. 25 00:01:17,590 --> 00:01:22,510 Und so Warteschlangen sind eine Art der Fairness Durchführungsstruktur. 26 00:01:22,510 --> 00:01:25,780 Aber das bedeutet nicht unbedingt, dass Stacks sind eine schlechte Sache, gerade 27 00:01:25,780 --> 00:01:28,160 dass Warteschlangen sind eine weitere Möglichkeit, es zu tun. 28 00:01:28,160 --> 00:01:32,420 Also noch einmal eine Warteschlange first in, first aus, im Vergleich zu einem Stapel, die in dem letzten, 29 00:01:32,420 --> 00:01:34,440 first out. 30 00:01:34,440 --> 00:01:36,190 Ähnlich wie bei einem Stapel, wir haben zwei Operationen 31 00:01:36,190 --> 00:01:38,470 dass wir auf Warteschlangen durchführen können. 32 00:01:38,470 --> 00:01:43,910 Die Namen sind Enqueue, was hinzuzufügen ist ein neues Element am Ende der Warteschlange, 33 00:01:43,910 --> 00:01:47,330 und dequeue, das ist um den ältesten entfernen 34 00:01:47,330 --> 00:01:49,670 Element von der Vorderseite der Warteschlange. 35 00:01:49,670 --> 00:01:53,600 So werden wir Elemente hinzufügen auf das Ende der Warteschlange, 36 00:01:53,600 --> 00:01:57,220 und wir werden Elemente entfernen von der Vorderseite der Warteschlange. 37 00:01:57,220 --> 00:02:00,790 Wieder mit dem Stapel, waren wir das Hinzufügen Elemente, die der Oberseite des Stapels 38 00:02:00,790 --> 00:02:03,380 und Entfernen von Elementen von der Spitze des Stapels. 39 00:02:03,380 --> 00:02:07,570 Also mit Enqueue, es ist das Hinzufügen zu das Ende, das Entfernen von vorne. 40 00:02:07,570 --> 00:02:10,639 Also die älteste Sache drin ist immer das nächste, was 41 00:02:10,639 --> 00:02:13,620 zu kommen, wenn wir versuchen und aus der Warteschlange entfernt etwas. 42 00:02:13,620 --> 00:02:18,330 >> Also noch einmal, mit Warteschlangen, können wir Array-basierte Implementierungen 43 00:02:18,330 --> 00:02:20,110 und verknüpfte Liste basierte Implementierungen. 44 00:02:20,110 --> 00:02:24,620 Wir sehen uns wieder mit zu beginnen Array-basierte Implementierungen. 45 00:02:24,620 --> 00:02:27,070 Die Strukturdefinition sieht ziemlich ähnlich. 46 00:02:27,070 --> 00:02:30,720 Wir haben ein anderes Array gibt der Datentypwert, 47 00:02:30,720 --> 00:02:32,690 so kann beliebige Datentypen zu halten. 48 00:02:32,690 --> 00:02:35,570 Wir sind wieder in Gang zu bedienen Zahlen in diesem Beispiel. 49 00:02:35,570 --> 00:02:39,830 >> Und genau wie mit unseren Array-basierte Stack-Implementierung, 50 00:02:39,830 --> 00:02:42,340 weil wir mit ein Arrays, die wir unbedingt 51 00:02:42,340 --> 00:02:46,850 haben diese Einschränkung, dass C Art der setzt auf uns, die wir es 52 00:02:46,850 --> 00:02:51,670 keine Dynamik haben unsere Fähigkeit zu wachsen und schrumpfen Sie das Array. 53 00:02:51,670 --> 00:02:55,710 Wir haben zu Beginn entscheiden was ist die maximale Anzahl von Dingen 54 00:02:55,710 --> 00:02:59,300 dass wir in diese setzen Warteschlange, und in diesem Fall, 55 00:02:59,300 --> 00:03:02,070 Kapazitäten würden einige Pfund sein in unserem Code Konstante definiert. 56 00:03:02,070 --> 00:03:05,430 Und für die Zwecke dieser Video wird Kapazität werde 10 sein. 57 00:03:05,430 --> 00:03:07,690 >> Wir brauchen, um zu verfolgen die Vorderseite der Warteschlange 58 00:03:07,690 --> 00:03:11,160 so wissen wir, welches Element Wir wollen aus der Warteschlange entfernt, 59 00:03:11,160 --> 00:03:15,070 und wir müssen auch im Auge zu behalten etwas else-- die Anzahl der Elemente 60 00:03:15,070 --> 00:03:16,690 dass wir in unserer Warteschlange. 61 00:03:16,690 --> 00:03:19,360 Beachten Sie, dass wir nicht die Verfolgung der am Ende der Warteschlange, so 62 00:03:19,360 --> 00:03:21,150 die Größe der Warteschlange. 63 00:03:21,150 --> 00:03:24,310 Und der Grund dafür, dass hoffentlich sich etwas klarer in einem Augenblick. 64 00:03:24,310 --> 00:03:26,143 Sobald wir abgeschlossen haben Diese Typdefinition, 65 00:03:26,143 --> 00:03:29,080 Wir haben einen neuen Datentyp genannt Warteschlange, die wir nun 66 00:03:29,080 --> 00:03:30,630 deklarieren Variablen dieses Datentyps. 67 00:03:30,630 --> 00:03:35,350 Und etwas verwirrend, habe ich beschlossen, um diese Warteschlange q, der Brief nennen 68 00:03:35,350 --> 00:03:38,090 q anstelle des Datentyps q. 69 00:03:38,090 --> 00:03:39,600 >> So, hier ist unsere Warteschlange. 70 00:03:39,600 --> 00:03:40,700 Es ist eine Struktur. 71 00:03:40,700 --> 00:03:45,730 Es enthält drei Mitglieder oder drei Felder, ein Array der Größe Kapazität. 72 00:03:45,730 --> 00:03:47,340 In diesem Fall wird die Kapazität 10. 73 00:03:47,340 --> 00:03:49,580 Und das Array gehen, um ganze Zahlen zu halten. 74 00:03:49,580 --> 00:03:55,240 In grün ist der vor unserem Warteschlange, die nächste Element entfernt werden soll, und in roter 75 00:03:55,240 --> 00:03:58,610 wird die Größe der Warteschlange, wie viele Elemente liegen noch 76 00:03:58,610 --> 00:04:01,190 in der Warteschlange vorhanden sind. 77 00:04:01,190 --> 00:04:05,300 Also, wenn wir sagen, q.front equals 0 und q.size Größe entspricht 0-- 78 00:04:05,300 --> 00:04:07,120 Wir setzen 0s in diesen Bereichen. 79 00:04:07,120 --> 00:04:11,070 Und an diesem Punkt sind wir ziemlich viel bereit, mit unseren Warteschlange zu beginnen. 80 00:04:11,070 --> 00:04:14,140 >> So ist der erste Betrieb können wir durchzuführen ist, etwas einzureihen, 81 00:04:14,140 --> 00:04:16,860 um ein neues Element hinzuzufügen das Ende der Warteschlange. 82 00:04:16,860 --> 00:04:19,089 Nun, was brauchen wir, um machen im allgemeinen Fall? 83 00:04:19,089 --> 00:04:23,690 Nun diese Funktion Enqueue Bedürfnisse einen Zeiger auf unsere Warteschlange zu akzeptieren. 84 00:04:23,690 --> 00:04:26,370 Auch wenn wir erklärt hatten unsere Warteschlange global, 85 00:04:26,370 --> 00:04:29,490 wir würden nicht dies tun müssen unbedingt, aber im Allgemeinen haben wir 86 00:04:29,490 --> 00:04:32,330 müssen Zeigern akzeptieren Datenstrukturen 87 00:04:32,330 --> 00:04:35,040 so, weil sonst wir durch value-- wir sind vorbei 88 00:04:35,040 --> 00:04:38,140 Einleiten von Kopien der Warteschlange, und so sind wir nicht wirklich zu ändern 89 00:04:38,140 --> 00:04:41,050 die Schlange, die wir beabsichtigen, zu ändern. 90 00:04:41,050 --> 00:04:44,860 >> Das andere, was es tun muss, ist zu akzeptieren ein Datenelement des entsprechenden Typs. 91 00:04:44,860 --> 00:04:46,818 Auch in diesem Fall ist es gehen, um ganze Zahlen sein, 92 00:04:46,818 --> 00:04:49,330 aber man konnte beliebig deklarieren Sie den Datentyp als Wert 93 00:04:49,330 --> 00:04:51,160 und nutzen diese im Allgemeinen. 94 00:04:51,160 --> 00:04:56,030 Das ist das Element, das wir zu Enqueue möchten, Wir wollen bis zum Ende der Warteschlange hinzuzufügen. 95 00:04:56,030 --> 00:04:58,573 Dann werden wir wirklich wollen, stellen, dass die Daten in der Warteschlange. 96 00:04:58,573 --> 00:05:01,490 In diesem Fall wird dem Einlegen in das korrekte Position unseres Array, 97 00:05:01,490 --> 00:05:05,040 und dann, um die Größe ändern möchten wir der Schlange, wie viele Elemente wir 98 00:05:05,040 --> 00:05:07,050 Aktuell haben. 99 00:05:07,050 --> 00:05:07,990 >> Also lassen Sie uns loslegen. 100 00:05:07,990 --> 00:05:10,890 Hier ist wiederum, dass die allgemeine Form Funktionsdeklaration 101 00:05:10,890 --> 00:05:13,980 für das, was Enqueue aussehen könnte. 102 00:05:13,980 --> 00:05:14,910 Und es geht los. 103 00:05:14,910 --> 00:05:18,335 Lassen Sie uns die Anzahl Enqueue 28 in die Warteschlange. 104 00:05:18,335 --> 00:05:19,460 Also, was sollen wir tun? 105 00:05:19,460 --> 00:05:23,390 Nun, die vor unserem Warteschlange bei 0 und die Größe unseres Warteschlange 106 00:05:23,390 --> 00:05:29,680 ist bei 0, und so wollen wir wahrscheinlich zu setzen die Zahl 28 in Array-Element-Nummer 107 00:05:29,680 --> 00:05:31,124 0, oder? 108 00:05:31,124 --> 00:05:32,540 Also haben wir jetzt, dass dort platziert. 109 00:05:32,540 --> 00:05:34,820 So, jetzt, was müssen wir ändern? 110 00:05:34,820 --> 00:05:37,090 Wir wissen nicht ändern möchten die Spitze der Warteschlange, 111 00:05:37,090 --> 00:05:40,850 weil wir, in welchem ​​Element wissen wollen wir brauchen, um später aus der Warteschlange entfernt. 112 00:05:40,850 --> 00:05:44,020 Also der Grund, warum wir dort vorn ist eine Art Indikator für was ist 113 00:05:44,020 --> 00:05:46,439 das älteste, was in der Anordnung. 114 00:05:46,439 --> 00:05:49,730 Nun die älteste Sache der array-- in der Tat, das einzige, was in dem Feld rechts 115 00:05:49,730 --> 00:05:53,540 now-- ist 28, das ist, bei Matrixort 0. 116 00:05:53,540 --> 00:05:56,160 So dass wir nicht wollen, zu ändern, dass die grüne Nummer, 117 00:05:56,160 --> 00:05:57,910 denn das ist das älteste Element. 118 00:05:57,910 --> 00:06:00,510 Vielmehr um die Größe ändern wollen wir. 119 00:06:00,510 --> 00:06:04,110 Also in diesem Fall, wir Schrittweite 1. 120 00:06:04,110 --> 00:06:08,430 >> Jetzt eine allgemeine Art von Vorstellung davon, wo die nächste Element wird sich in einer Warteschlange zu gehen 121 00:06:08,430 --> 00:06:12,310 wird, jene zwei Zahlen zu addieren zusammen, vorne und Größe, 122 00:06:12,310 --> 00:06:16,390 und das werden Sie sagen, wo die nächste Element in der Warteschlange gehen wird. 123 00:06:16,390 --> 00:06:18,130 So, jetzt lassen Sie uns Enqueue eine andere Nummer. 124 00:06:18,130 --> 00:06:20,250 Lassen Sie uns Enqueue 33. 125 00:06:20,250 --> 00:06:24,480 So 33 wird sich in gehen Matrixort 0 plus 1. 126 00:06:24,480 --> 00:06:26,840 Also in diesem Fall, es geht in Feldposition 1 zu gehen, 127 00:06:26,840 --> 00:06:29,500 und jetzt die Größe unserer Warteschlange ist 2. 128 00:06:29,500 --> 00:06:31,840 >> Auch hier werden wir nicht ändern die vor unserem Warteschlange, 129 00:06:31,840 --> 00:06:34,730 weil 28 ist immer noch die älteste Element, und wir 130 00:06:34,730 --> 00:06:38,220 zu-- möchten, wenn wir irgendwann zum Entfernen aus Warteschlangen, Entfernen von Elementen 131 00:06:38,220 --> 00:06:43,300 aus dieser Warteschlange, wollen wir wissen wo das älteste Element ist. 132 00:06:43,300 --> 00:06:48,620 Und so müssen wir immer zu pflegen einige Indikator, wo das ist. 133 00:06:48,620 --> 00:06:50,410 Also das ist, was der 0 gibt es für. 134 00:06:50,410 --> 00:06:52,910 Das ist, was vorne ist für. 135 00:06:52,910 --> 00:06:55,022 >> Lassen Sie uns in Enqueue ein weiteres Element, 19. 136 00:06:55,022 --> 00:06:56,980 Ich bin sicher, dass Sie sich vorstellen können wo 19 gehen wird. 137 00:06:56,980 --> 00:06:59,860 Es wird in zu gehen Array Platznummer 2. 138 00:06:59,860 --> 00:07:01,570 Das ist 0 plus 2. 139 00:07:01,570 --> 00:07:03,199 Und jetzt die Größe unseres Warteschlange 3. 140 00:07:03,199 --> 00:07:04,240 Wir haben 3 Elemente darin. 141 00:07:04,240 --> 00:07:08,490 Also, wenn wir uns, und wir werden nicht gerade jetzt, Enqueue ein weiteres Element, 142 00:07:08,490 --> 00:07:11,370 wäre es in ein Array Standort gehen Nummer 3, und die Größe der Warteschlange 143 00:07:11,370 --> 00:07:13,160 würde 4 sein. 144 00:07:13,160 --> 00:07:15,279 Also haben wir mehrere Elemente jetzt eingereiht. 145 00:07:15,279 --> 00:07:16,570 Lassen Sie uns jetzt beginnen, sie zu entfernen. 146 00:07:16,570 --> 00:07:19,450 Lasst Warteschlange entfernt sie aus der Warteschlange. 147 00:07:19,450 --> 00:07:23,340 >> So ähnlich wie Pop, welche Art ist des Analog davon für Stapel, 148 00:07:23,340 --> 00:07:26,180 dequeue muss eine akzeptieren Zeiger auf den queue-- wieder 149 00:07:26,180 --> 00:07:28,140 es sei denn, es ist global deklariert. 150 00:07:28,140 --> 00:07:31,610 Nun, um die Position ändern möchten wir der Vorderseite der Warteschlange. 151 00:07:31,610 --> 00:07:35,050 Dies ist, wo es irgendwie geht ins Spiel, dass Front variable, 152 00:07:35,050 --> 00:07:37,310 denn wenn wir entfernen ein Element, wir wollen, 153 00:07:37,310 --> 00:07:40,720 um es auf die nächste älteste Element zu bewegen. 154 00:07:40,720 --> 00:07:44,180 >> Dann sinken wollen wir die Größe der Warteschlange, 155 00:07:44,180 --> 00:07:47,130 und dann, um den Wert zurückgeben möchten wir daß aus der Warteschlange entfernt. 156 00:07:47,130 --> 00:07:48,921 Auch hier wollen wir nicht nur verwerfen. 157 00:07:48,921 --> 00:07:51,170 Wir werden vermutlich extra es von der queue-- wir sind 158 00:07:51,170 --> 00:07:54,170 Entfernen aus Warteschlangen, weil wir darum kümmern. 159 00:07:54,170 --> 00:08:01,080 So wollen wir diese Funktion, um zurückzukehren ein Datenelement vom Typ Wert. 160 00:08:01,080 --> 00:08:04,360 Auch in diesem Fall ist der Wert Integer. 161 00:08:04,360 --> 00:08:05,670 >> So, jetzt lassen Sie uns etwas aus der Warteschlange entfernt. 162 00:08:05,670 --> 00:08:09,310 Lassen Sie uns ein Element aus der Warteschlange zu entfernen. 163 00:08:09,310 --> 00:08:15,970 Wenn wir sagen, int x gleich & q, Und-Zeichen Q-- wieder, das ist ein Zeiger auf diesen Q-Daten 164 00:08:15,970 --> 00:08:20,177 structure-- welchem ​​Element wird sich aus der Warteschlange entfernt werden? 165 00:08:20,177 --> 00:08:23,840 166 00:08:23,840 --> 00:08:29,480 In diesem Fall, weil es ein erstes in, first out Datenstruktur, FIFO, 167 00:08:29,480 --> 00:08:33,690 das erste, was wir uns in diese setzen Schlange war 28, und so in diesem Fall, 168 00:08:33,690 --> 00:08:37,245 wir werden 28 von nehmen die Schlange, nicht 19, das, was 169 00:08:37,245 --> 00:08:38,870 wir getan hätte, wenn es sich um eine Stack. 170 00:08:38,870 --> 00:08:42,220 Wir werden 28 aus der Warteschlange zu nehmen. 171 00:08:42,220 --> 00:08:44,960 >> Ähnlich dem, was wir haben ein Stapel, wir sind nicht wirklich 172 00:08:44,960 --> 00:08:47,345 gehen, um zu löschen 28 aus der Schlange selbst, 173 00:08:47,345 --> 00:08:49,470 wir sind gerade dabei, Art von so tun, es ist nicht da. 174 00:08:49,470 --> 00:08:51,678 Also, es wird dort bleiben im Speicher, aber wir sind 175 00:08:51,678 --> 00:08:57,820 gehen, um Art zu ignorieren, indem Sie die anderen beiden Felder der Q-Daten 176 00:08:57,820 --> 00:08:58,830 Struktur. 177 00:08:58,830 --> 00:09:00,230 Wir werden die Front ändern. 178 00:09:00,230 --> 00:09:04,290 Q.front geht jetzt um 1 sein, denn das ist jetzt 179 00:09:04,290 --> 00:09:07,740 das älteste Element, das wir in haben unsere Warteschlange, denn wir haben bereits entfernt 28, 180 00:09:07,740 --> 00:09:10,460 was war der ehemalige älteste Element. 181 00:09:10,460 --> 00:09:13,540 >> Und nun ändern möchten wir die Größe der Warteschlange 182 00:09:13,540 --> 00:09:15,780 auf zwei Elemente anstelle von drei. 183 00:09:15,780 --> 00:09:20,450 Jetzt erinnere früher sagte ich, als wir wollen Elemente zur Warteschlange hinzuzufügen, 184 00:09:20,450 --> 00:09:26,000 wir setzen es in einem Array Ort das ist die Summe der vorderen und Größe. 185 00:09:26,000 --> 00:09:29,050 Also in diesem Fall, wir sind noch dabei darauf das nächste Element in der Warteschlange, 186 00:09:29,050 --> 00:09:33,360 in Feldposition 3 und wir werden, dass in einem zweiten zu sehen. 187 00:09:33,360 --> 00:09:35,730 >> Also haben wir jetzt aus der Warteschlange entfernt haben unsere das erste Element aus der Warteschlange. 188 00:09:35,730 --> 00:09:36,480 Lass uns das nochmal machen. 189 00:09:36,480 --> 00:09:38,696 Lassen Sie uns eine andere zu entfernen Element aus der Warteschlange. 190 00:09:38,696 --> 00:09:42,400 In dem Fall, der aktuelle ältesten Element-Array Standort 1. 191 00:09:42,400 --> 00:09:44,220 Das ist, was sagt uns, q.front. 192 00:09:44,220 --> 00:09:46,980 Das grüne Feld zeigt uns, dass das ist das älteste Element. 193 00:09:46,980 --> 00:09:49,310 Und so wird x 33 geworden. 194 00:09:49,310 --> 00:09:52,130 Wir werden nur irgendwie vergessen dass 33 in der Anordnung vorhanden ist, 195 00:09:52,130 --> 00:09:55,100 und wir werden jetzt die sagen, dass neue älteste Element in der Warteschlange 196 00:09:55,100 --> 00:09:58,900 zumin Matrixort 2 und der Größe der Warteschlange, die Anzahl der Elemente 197 00:09:58,900 --> 00:10:02,152 Wir haben in der Warteschlange ist 1. 198 00:10:02,152 --> 00:10:05,110 Lassen Sie uns jetzt Enqueue etwas, und ich Art vor einer Sekunde gab diese weg, 199 00:10:05,110 --> 00:10:10,340 aber wenn wir auf 40 in die setzen wollen Warteschlange, wo ist 40 hingehen? 200 00:10:10,340 --> 00:10:12,880 201 00:10:12,880 --> 00:10:17,730 Nun wir haben es setzen in q.front zzgl Queue-Größe, 202 00:10:17,730 --> 00:10:20,850 und so ist es sinnvoll ist, tatsächlich zu 40 ablegen. 203 00:10:20,850 --> 00:10:22,840 Jetzt bemerken, dass bei Irgendwann werden wir 204 00:10:22,840 --> 00:10:27,980 bis zum Ende des zu erhalten unser Angebot innerhalb von q, 205 00:10:27,980 --> 00:10:32,010 aber das ausgeblendet 28 und 33-- sie tatsächlich, technisch 206 00:10:32,010 --> 00:10:33,300 Freiflächen, nicht wahr? 207 00:10:33,300 --> 00:10:36,040 Und so können wir eventually-- dass Regel Hinzufügen 208 00:10:36,040 --> 00:10:40,390 die beiden together-- wir kann schließlich müssen mod durch die Größe der Kapazität 209 00:10:40,390 --> 00:10:41,410 damit wir Wrap-around. 210 00:10:41,410 --> 00:10:43,620 >> Wenn wir also Element erhalten Nummer 10, wenn wir 211 00:10:43,620 --> 00:10:48,790 es in Elementnummer 10 zu ersetzen, würden wir tatsächlich legte es in Feldposition 0. 212 00:10:48,790 --> 00:10:50,997 Und wenn wir wurden zu gehen Array location-- mich entschuldigen, 213 00:10:50,997 --> 00:10:53,080 wenn wir sie zusammen hinzugefügt, und wir haben Nummer 214 00:10:53,080 --> 00:10:56,330 11 wäre, wo wir müssten setzen es, die in diesem array-- existiert 215 00:10:56,330 --> 00:10:58,200 es wäre aus gehen von Grenzen. 216 00:10:58,200 --> 00:11:03,367 Wir konnten um 10 MOD und setzen in Feldposition 1. 217 00:11:03,367 --> 00:11:04,450 Also das ist, wie Warteschlangen arbeiten. 218 00:11:04,450 --> 00:11:08,540 Sie sind immer gehen, um von links gehen nach rechts und möglicherweise herum wickeln. 219 00:11:08,540 --> 00:11:11,280 Und Sie wissen, dass sie voll, wenn Größe, dass rotes Feld, 220 00:11:11,280 --> 00:11:13,710 gleich Kapazität. 221 00:11:13,710 --> 00:11:16,720 Und so, nachdem wir 40, den Mehr Warteschlange, gut, was müssen wir tun? 222 00:11:16,720 --> 00:11:19,890 Nun, das älteste Element in der Warteschlange noch 19 223 00:11:19,890 --> 00:11:21,990 so dass wir nicht ändern wollen die Spitze der Warteschlange, 224 00:11:21,990 --> 00:11:23,820 aber jetzt haben wir zwei haben Elemente in der Warteschlange, 225 00:11:23,820 --> 00:11:28,710 und so zu erhöhen, wollen wir unsere Größe von 1 bis 2. 226 00:11:28,710 --> 00:11:31,820 >> Das ist ziemlich viel es mit Arbeit mit Array-basierte Warteschlangen, 227 00:11:31,820 --> 00:11:33,630 und ähnlich zu stapeln, es gibt auch eine Möglichkeit, 228 00:11:33,630 --> 00:11:36,450 eine Warteschlange als eine verknüpfte Liste zu implementieren. 229 00:11:36,450 --> 00:11:40,150 Nun, wenn diese Datenstruktur Typ kommt mir bekannt vor, Sie ist es. 230 00:11:40,150 --> 00:11:43,780 Es ist nicht eine einfach verkettete Liste, es ist eine doppelt verknüpfte Liste. 231 00:11:43,780 --> 00:11:46,790 Und nun Nebenbei ist es tatsächlich möglich zu implementieren 232 00:11:46,790 --> 00:11:50,160 eine Schlange als eine einfach verkettete Liste, aber Ich denke, dass in Bezug auf die Visualisierung, 233 00:11:50,160 --> 00:11:53,350 es könnte tatsächlich helfen, um zu sehen dies als eine doppelt verknüpfte Liste. 234 00:11:53,350 --> 00:11:56,850 Aber es ist auf jeden Fall möglich, tun dies als eine einfach verkettete Liste. 235 00:11:56,850 --> 00:12:00,110 >> Lassen Sie uns also einen Blick auf was diese aussehen könnte. 236 00:12:00,110 --> 00:12:02,750 Wenn wir wollen, enquue-- so jetzt, wieder sind wir 237 00:12:02,750 --> 00:12:05,360 Umstellung auf eine verknüpfte Liste basierend auf das Modell. 238 00:12:05,360 --> 00:12:08,420 Wenn wir Enqueue, wir wollen um ein neues Element hinzuzufügen, gut 239 00:12:08,420 --> 00:12:09,730 was müssen wir tun? 240 00:12:09,730 --> 00:12:12,770 Nun, zunächst einmal, weil die wir hinzufügen, um das Ende 241 00:12:12,770 --> 00:12:15,520 und Entfernen von der Anfang, wir wahrscheinlich 242 00:12:15,520 --> 00:12:20,050 wollen Zeigern, um sowohl die Aufrechterhaltung Kopf und der Schwanz des verknüpften Liste? 243 00:12:20,050 --> 00:12:22,660 Schwanz als eine andere Bezeichnung für das Ende der verketteten Liste, 244 00:12:22,660 --> 00:12:24,496 das letzte Element in der verketteten Liste. 245 00:12:24,496 --> 00:12:26,620 Und diese werden wahrscheinlich, wieder, von Vorteil sein, uns 246 00:12:26,620 --> 00:12:28,477 wenn sie globale Variablen. 247 00:12:28,477 --> 00:12:31,060 Aber jetzt, wenn wir einen neuen hinzufügen möchten Element, was müssen wir tun? 248 00:12:31,060 --> 00:12:35,262 Was wir gerade [? Malak?] oder dynamisch zuzuweisen unserem neuen Knoten für uns selbst. 249 00:12:35,262 --> 00:12:38,220 Und dann, wie gerade, wenn wir irgendeine hinzufügen Element zu einer doppelt verketteten Liste, die wir, 250 00:12:38,220 --> 00:12:40,410 einfach nur, um zu sortieren von-- diese letzten drei Schritte hier 251 00:12:40,410 --> 00:12:43,330 sind nur alles um bewegte die Zeiger in der richtigen Art und Weise 252 00:12:43,330 --> 00:12:46,710 so dass das Element wird hinzugefügt die Kette ohne die Kette 253 00:12:46,710 --> 00:12:49,580 oder machen eine Art von Fehler oder mit einer gewissen Art von Unfall 254 00:12:49,580 --> 00:12:54,505 passieren, wobei wir versehentlich Orphan einige Elemente unserer Warteschlange. 255 00:12:54,505 --> 00:12:55,880 Hier ist, was diese aussehen könnte. 256 00:12:55,880 --> 00:13:00,980 Wir wollen, um das Element hinzuzufügen 10 an das Ende dieser Warteschlange. 257 00:13:00,980 --> 00:13:03,380 Also das älteste Element hier wird durch den Kopf dargestellt. 258 00:13:03,380 --> 00:13:06,800 Das ist das erste, was wir setzen in diesem hypothetischen Warteschlange hier. 259 00:13:06,800 --> 00:13:10,430 Und Schwanz, 13, ist die zuletzt hinzugefügten Elements. 260 00:13:10,430 --> 00:13:17,030 Und so, wenn wir in 10 einreihen wollen diese Warteschlange, wir wollen es nach 13 gesetzt. 261 00:13:17,030 --> 00:13:19,860 Und so werden wir dynamisch Speicherplatz zuweisen für einen neuen Knoten 262 00:13:19,860 --> 00:13:23,280 und überprüfen Sie null, um sicherzustellen, wir haben nicht einen Speicherfehler. 263 00:13:23,280 --> 00:13:27,040 Dann werden wir zu gehen platzieren 10 in diesem Knoten, 264 00:13:27,040 --> 00:13:30,030 und jetzt müssen wir vorsichtig sein, darüber, wie wir organisieren Zeigern 265 00:13:30,030 --> 00:13:32,180 so dass wir die Kette nicht brechen. 266 00:13:32,180 --> 00:13:38,910 >> Wir können 10 bisherige Feld gesetzt auf den alten Schwanz zurückweisen, 267 00:13:38,910 --> 00:13:41,620 und seit '10 wird die neue Schwanz zu einem bestimmten Zeitpunkt 268 00:13:41,620 --> 00:13:44,459 durch die Zeit, alle diese Ketten verbunden sind, 269 00:13:44,459 --> 00:13:46,250 nichts wird kommen nach 10 jetzt. 270 00:13:46,250 --> 00:13:49,880 Und so 10 der nächste Zeiger wird darauf auf null, 271 00:13:49,880 --> 00:13:53,580 und dann, nachdem wir dies tun, nachdem wir Verbindung 10 nach hinten an die Kette, 272 00:13:53,580 --> 00:13:57,780 können wir den alten Kopf, oder Entschuldigung zu nehmen mich, die alte Ende der Warteschlange. 273 00:13:57,780 --> 00:14:02,980 Der alte Ende der Warteschlange, 13, und machen es bis 10 zeigen. 274 00:14:02,980 --> 00:14:08,220 Und jetzt, an diesem Punkt, wir haben reiht die Nummer 10 in dieser Warteschlange. 275 00:14:08,220 --> 00:14:14,740 Alles, was wir jetzt tun müssen, ist gerade bewegen Schwanz bis 10 statt bis 13 zeigen. 276 00:14:14,740 --> 00:14:17,630 >> Entfernen aus Warteschlangen ist eigentlich sehr ähnlich zu knallen 277 00:14:17,630 --> 00:14:21,710 aus einem Stapel, die ist als eine verknüpfte Liste implementiert 278 00:14:21,710 --> 00:14:24,040 wenn Sie die Stapel-Video gesehen habe. 279 00:14:24,040 --> 00:14:27,280 Alles, was wir tun müssen, ist ab dem beginnen, finden Sie das zweite Element, 280 00:14:27,280 --> 00:14:30,480 befreien das erste Element, und bewegen Sie den Kopf 281 00:14:30,480 --> 00:14:32,930 bis zu dem zweiten Element zu verweisen. 282 00:14:32,930 --> 00:14:37,920 Wahrscheinlich besser, es zu visualisieren nur um zusätzliche klaren darüber sein. 283 00:14:37,920 --> 00:14:39,230 Also hier ist unsere Warteschlange wieder. 284 00:14:39,230 --> 00:14:42,600 12 ist das älteste Element in unserer Warteschlange, den Kopf. 285 00:14:42,600 --> 00:14:46,210 10 ist das neueste Element in unserer Warteschlange unsere Schwanz. 286 00:14:46,210 --> 00:14:49,310 >> Und so, wenn wir wollen, , ein Element aus der Warteschlange entfernt, 287 00:14:49,310 --> 00:14:52,202 wollen wir das älteste Element zu entfernen. 288 00:14:52,202 --> 00:14:52,910 Also, was machen wir? 289 00:14:52,910 --> 00:14:55,243 Nun setzen wir einen Durchlauf-Zeiger das beginnt an der Spitze, 290 00:14:55,243 --> 00:14:57,840 und wir es so zu bewegen, dass es Punkte an dem zweiten Element 291 00:14:57,840 --> 00:15:02,290 Dies queue-- etwas sagen trav gleich trav Pfeil neben beispielsweise 292 00:15:02,290 --> 00:15:07,170 würde trav dort zu bewegen, um darauf hinzuweisen 15, die, nach einer 12 aus der Warteschlange entfernt, 293 00:15:07,170 --> 00:15:13,030 oder nach dem entfernen wir 12, wird zu der damals älteste Element. 294 00:15:13,030 --> 00:15:16,360 >> Jetzt haben wir einen Halt an der zum ersten Mal Element über den Zeiger Kopf 295 00:15:16,360 --> 00:15:19,440 und das zweite Element über den Zeiger trav. 296 00:15:19,440 --> 00:15:25,170 Wir können jetzt kostenlos Kopf, und dann können wir sagen, es kommt nichts vor dem 15. mehr. 297 00:15:25,170 --> 00:15:29,990 So können wir 15 früheren ändern Zeiger auf Punkt auf null, 298 00:15:29,990 --> 00:15:31,874 und wir nur den Kopf bewegen vorbei. 299 00:15:31,874 --> 00:15:32,540 Und wir gehen. 300 00:15:32,540 --> 00:15:35,840 Jetzt müssen wir erfolgreich aus der Warteschlange entfernt 12, und jetzt sind wir 301 00:15:35,840 --> 00:15:39,180 haben eine andere Warteschlange der 4 Elemente. 302 00:15:39,180 --> 00:15:41,700 Das ist so ziemlich alles, gibt es Warteschlangen, 303 00:15:41,700 --> 00:15:45,810 sowohl Array-basierte und verketteten Liste basiert. 304 00:15:45,810 --> 00:15:46,860 Ich bin Doug Lloyd. 305 00:15:46,860 --> 00:15:49,100 Dies CS 50. 306 00:15:49,100 --> 00:15:50,763