1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Alle Rechte,
so von diesem Punkt bist du

3
00:00:05,990 --> 00:00:09,020
wahrscheinlich ziemlich vertraut
mit Arrays und verkettete Listen

4
00:00:09,020 --> 00:00:10,950
der die beiden Primär ist
Datenstrukturen, wir haben

5
00:00:10,950 --> 00:00:16,810
sprach über für die Aufbewahrung Sätze
Daten von ähnlichen Datentypen organisiert.

6
00:00:16,810 --> 00:00:19,080
>> Jetzt werden wir zu sprechen
über ein paar Variationen

7
00:00:19,080 --> 00:00:20,330
auf Arrays und verkettete Listen.

8
00:00:20,330 --> 00:00:22,362
In diesem Video werden wir
über Stapel zu sprechen.

9
00:00:22,362 --> 00:00:25,320
Insbesondere werden wir sprechen
über eine Datenstruktur, genannt ein Stapel.

10
00:00:25,320 --> 00:00:28,510
Rückruf von früheren Diskussionen
über Zeiger und Gedächtnis,

11
00:00:28,510 --> 00:00:32,060
daß der Stapel auch die
Bezeichnung für einen Abschnitt des Speichers

12
00:00:32,060 --> 00:00:34,980
wo statisch deklariert
memory-- Speicher, die Sie

13
00:00:34,980 --> 00:00:38,730
Namen, Variablen, die Sie nennen, et
cetera und Funktionsrahmen, die wir

14
00:00:38,730 --> 00:00:41,000
Call-Stack-Frames vorhanden sind.

15
00:00:41,000 --> 00:00:45,421
Das ist also ein Stapel-Datenstruktur
kein Stapelspeichersegment.

16
00:00:45,421 --> 00:00:45,920
OK.

17
00:00:45,920 --> 00:00:46,890
>> Aber was ist ein Stack?

18
00:00:46,890 --> 00:00:49,220
Es ist also ziemlich genau ein
besondere Art von Struktur

19
00:00:49,220 --> 00:00:51,190
dass die Daten pflegt in einer organisierten Art und Weise.

20
00:00:51,190 --> 00:00:53,760
Und es gibt zwei sehr
gemeinsame Wege zur Umsetzung

21
00:00:53,760 --> 00:00:57,380
Stacks unter Verwendung von zwei Datenstrukturen
dass wir bereits kennen,

22
00:00:57,380 --> 00:01:00,340
Arrays und verkettete Listen.

23
00:01:00,340 --> 00:01:04,430
Was macht ein Stapel besonderen ist die
Weise, in der wir uns stellen Informationen

24
00:01:04,430 --> 00:01:08,200
in den Stapel, und, wie wir
entfernen Sie Informationen aus dem Stapel.

25
00:01:08,200 --> 00:01:11,600
Insbesondere mit Stapeln
die Regel ist nur das

26
00:01:11,600 --> 00:01:15,830
zuletzt hinzugefügten Elements entfernt werden kann.

27
00:01:15,830 --> 00:01:17,660
>> Also denken Sie darüber nach, als ob es ein Stapel.

28
00:01:17,660 --> 00:01:21,170
Wir häufen Informationen
auf sich selbst,

29
00:01:21,170 --> 00:01:24,271
und nur das, was an der Spitze
des Stapels entfernt werden kann.

30
00:01:24,271 --> 00:01:27,020
Wir können die Sache nicht unter zu entfernen
denn alles andere würde

31
00:01:27,020 --> 00:01:28,020
Zusammenbruch und umfallen.

32
00:01:28,020 --> 00:01:32,580
So dass wir wirklich bauen ein Stack,
Wir müssen dann Stück für Stück zu entfernen.

33
00:01:32,580 --> 00:01:36,590
Aus diesem Grund haben wir gemeinhin beziehen
einen Stapel als LIFO-Struktur,

34
00:01:36,590 --> 00:01:38,940
last in, first out.

35
00:01:38,940 --> 00:01:42,290
LIFO, last in, first out.

36
00:01:42,290 --> 00:01:45,635
>> So, weil dieser Beschränkung
wie Informationen hinzugefügt werden

37
00:01:45,635 --> 00:01:49,080
und aus einem Stapel entfernt, gibt es wirklich
nur zwei Dinge, die wir mit einem Stapel tun können.

38
00:01:49,080 --> 00:01:52,010
Wir können zu drücken, die der ist
Begriff verwenden wir für das Hinzufügen

39
00:01:52,010 --> 00:01:55,130
ein neues Element in der Oberseite des
Stapel, oder wenn der Stapel nicht vorhanden

40
00:01:55,130 --> 00:01:58,550
und wir schaffen es von Grund auf,
Erstellen des Stapels in dem ersten Platz

41
00:01:58,550 --> 00:02:00,110
wäre schieben.

42
00:02:00,110 --> 00:02:04,990
Und dann Pop, das ist die Art von CS
Begriff verwenden wir, um die zuletzt entfernen

43
00:02:04,990 --> 00:02:08,330
von der Oberseite des Stapels aufgenommen Element.

44
00:02:08,330 --> 00:02:11,130
>> So werden wir an beiden freuen
Implementierungen, sowohl Array basiert

45
00:02:11,130 --> 00:02:13,120
und verknüpften Liste basiert.

46
00:02:13,120 --> 00:02:14,870
Und wir sind zu gehen
beginnen mit Array basiert.

47
00:02:14,870 --> 00:02:19,990
Also hier ist die grundlegende Idee von dem, was
die Array-basierte Stapeldatenstruktur

48
00:02:19,990 --> 00:02:21,140
aussehen würde.

49
00:02:21,140 --> 00:02:23,740
Wir haben eine typisierte Definition hier.

50
00:02:23,740 --> 00:02:27,790
Innenseite, dass wir zwei Mitglieder
oder Felder der Struktur.

51
00:02:27,790 --> 00:02:29,880
Wir haben ein Array.

52
00:02:29,880 --> 00:02:32,400
Und wieder bin ich mit der
beliebige Datentyp Wert.

53
00:02:32,400 --> 00:02:35,180
>> So könnte dies ein beliebiger Datentyp sein,
int char oder eine andere Daten

54
00:02:35,180 --> 00:02:37,080
Geben Sie zuvor erstellt haben.

55
00:02:37,080 --> 00:02:39,861
So haben wir eine Reihe von Größe Kapazität.

56
00:02:39,861 --> 00:02:44,010
Kapazität, die ein Pfund definierte Konstante,
vielleicht irgendwo anders in unserer Datei.

57
00:02:44,010 --> 00:02:47,550
So bemerken bereits mit diesem
Umsetzung wir begrenze

58
00:02:47,550 --> 00:02:49,800
uns als war typisch
mit Arrays der Fall ist,

59
00:02:49,800 --> 00:02:53,170
die wir nicht dynamisch die Größe können,
wo es eine bestimmte Anzahl

60
00:02:53,170 --> 00:02:55,450
von Elementen Höchstbetrag,
Wir können in unserem Stapel gelegt.

61
00:02:55,450 --> 00:02:57,930
In diesem Fall ist es Kapazitätselemente.

62
00:02:57,930 --> 00:03:00,310
>> Wir halten auch verfolgen
das obere Ende des Stapels.

63
00:03:00,310 --> 00:03:04,350
Welches Element am meisten,
vor kurzem zu dem Stapel hinzugefügt?

64
00:03:04,350 --> 00:03:07,470
Und so verfolgen wir, dass
in einer Variablen namens top.

65
00:03:07,470 --> 00:03:11,692
Und all dies wird zusammen eingewickelt
in einen neuen Datentyp mit dem Namen eines Stapels.

66
00:03:11,692 --> 00:03:13,400
Und sobald wir geschaffen sind
Diese neue Datentyp

67
00:03:13,400 --> 00:03:15,410
wir können sie zu behandeln wie
andere Datentyps.

68
00:03:15,410 --> 00:03:20,970
Wir können Stapel s gerade wie zu erklären,
wir könnten int x, y oder char zu tun.

69
00:03:20,970 --> 00:03:22,990
Und wenn wir sagen stapeln
s, auch, was passiert,

70
00:03:22,990 --> 00:03:26,420
wird wir eine Reihe von zu bekommen
Speicher für uns beiseite stellen.

71
00:03:26,420 --> 00:03:28,770
>> In diesem Fall Kapazität
Ich habe offenbar beschlossen

72
00:03:28,770 --> 00:03:33,470
ist 10, weil ich eine bekommen
Einzel Variable des Typs Stack

73
00:03:33,470 --> 00:03:35,320
welche enthält zwei Felder wieder zu verwenden.

74
00:03:35,320 --> 00:03:38,330
Eine Anordnung, in diesem Fall wird
um eine Anordnung von Zahlen sein

75
00:03:38,330 --> 00:03:40,440
wie es in den meisten meiner Beispielen der Fall ist.

76
00:03:40,440 --> 00:03:43,996
Und noch ein Integer-Variable
fähig zur Speicherung der Spitze,

77
00:03:43,996 --> 00:03:45,870
die zuletzt hinzugefügten
Element auf den Stapel.

78
00:03:45,870 --> 00:03:50,290
So ein Einzelstapel, was wir
gerade definiert sieht wie folgt aus.

79
00:03:50,290 --> 00:03:53,190
Es ist eine Kiste mit
ein Array von 10 Meinung

80
00:03:53,190 --> 00:03:57,280
werden Zahlen in diesem Fall, und
ein weiterer Integer-Variablen gibt es in grün

81
00:03:57,280 --> 00:04:00,010
um die Oberseite des Stapels anzuzeigen.

82
00:04:00,010 --> 00:04:02,600
>> Um die Oberseite des Fernseh
Stapel wir nur sagen s.top.

83
00:04:02,600 --> 00:04:04,890
Das ist, wie wir Zugang zu einem
Feld einer Struktur Rückruf.

84
00:04:04,890 --> 00:04:10,460
s.top effektiv gleich 0
tut dies, um unsere Stack.

85
00:04:10,460 --> 00:04:12,960
So haben wir wieder zwei Operationen
dass wir jetzt durchführen können.

86
00:04:12,960 --> 00:04:14,270
Wir können schieben und wir knallen kann.

87
00:04:14,270 --> 00:04:15,635
Lassen Sie uns mit Push starten.

88
00:04:15,635 --> 00:04:18,260
Auch hier drängt das Hinzufügen einer neuen
Element mit dem oberen Ende des Stapels.

89
00:04:18,260 --> 00:04:21,460
>> Also, was tun wir in tun müssen
Dieses Array basierte Implementierung?

90
00:04:21,460 --> 00:04:23,210
Gut im Allgemeinen die
Push-Funktion wird

91
00:04:23,210 --> 00:04:26,160
zu müssen, um eine zu akzeptieren
Zeiger auf den Stack.

92
00:04:26,160 --> 00:04:28,610
Nun nehmen Sie sich die Zeit und denken Sie darüber nach.

93
00:04:28,610 --> 00:04:32,840
Warum sollten wir annehmen wollen,
ein Zeiger zu dem Stapel?

94
00:04:32,840 --> 00:04:36,830
Recall aus früheren Videos auf
Geltungsbereich von Variablen und Zeiger,

95
00:04:36,830 --> 00:04:42,350
was passieren würde, wenn wir gerade geschickt
Stapel, s eher als Parameter?

96
00:04:42,350 --> 00:04:45,770
Was wäre eigentlich da drin übergeben werden?

97
00:04:45,770 --> 00:04:49,430
Denken Sie daran, wir schaffen eine Kopie
wenn wir es übergeben, um eine Funktion

98
00:04:49,430 --> 00:04:51,160
es sei denn, wir Zeigern.

99
00:04:51,160 --> 00:04:55,380
Und so diese Funktion schieben Bedürfnisse
einen Zeiger auf den Stapel übernehmen

100
00:04:55,380 --> 00:04:59,160
so dass wir wirklich zu ändern
der Stapel wollen wir ändern.

101
00:04:59,160 --> 00:05:03,060
>> Die andere Sache, Push wahrscheinlich will
akzeptieren, ist ein Datenelement vom Typ Wert.

102
00:05:03,060 --> 00:05:06,970
In diesem Fall wieder eine ganze Zahl,
wir werden an die Spitze der Stapel hinzufügen.

103
00:05:06,970 --> 00:05:08,680
So haben wir unsere beiden Parameter hat.

104
00:05:08,680 --> 00:05:11,310
Was machen wir
Jetzt innerhalb von Push zu tun?

105
00:05:11,310 --> 00:05:14,860
Nun, ganz einfach, wir sind gerade dabei, fügen
dass das Element nach oben aus dem Stapel

106
00:05:14,860 --> 00:05:22,860
und ändern Sie dann in dem die Spitze der
der Stapel, dass s-Punktoberwert.

107
00:05:22,860 --> 00:05:25,639
Also das ist, was eine Funktion
Erklärung für Push-

108
00:05:25,639 --> 00:05:27,680
könnte wie in einem Blick
Array-basierte Implementierung.

109
00:05:27,680 --> 00:05:30,967
>> Auch dies ist keine feste Regel,
dass man dies ändern und

110
00:05:30,967 --> 00:05:32,050
sie unterscheiden sich in unterschiedlicher Weise.

111
00:05:32,050 --> 00:05:33,840
Vielleicht s global deklariert.

112
00:05:33,840 --> 00:05:36,180
Und damit Sie brauchen noch nicht einmal
einen Pass zu spielen ist als Parameter.

113
00:05:36,180 --> 00:05:39,125
Dies ist wiederum nur ein
allgemeine Fall für Push.

114
00:05:39,125 --> 00:05:41,000
Und es gibt verschiedene
Möglichkeiten, es zu implementieren.

115
00:05:41,000 --> 00:05:42,810
Aber in diesem Fall unsere
Push dauern wird

116
00:05:42,810 --> 00:05:48,540
zwei Argumente einen Zeiger auf einen Stapel und
ein Datenelement vom Typ Wert, integer

117
00:05:48,540 --> 00:05:49,840
in diesem Fall.

118
00:05:49,840 --> 00:05:52,100
>> So erklärten wir s, wir
sagte s.top gleich 0.

119
00:05:52,100 --> 00:05:55,969
Lassen Sie uns jetzt drücken Sie die
Nummer 28 auf den Stapel.

120
00:05:55,969 --> 00:05:57,010
Nun, was soll das bedeuten?

121
00:05:57,010 --> 00:05:59,600
Nun noch die
oben auf dem Stapel ist 0.

122
00:05:59,600 --> 00:06:01,350
Und was ist im Grunde
geschehen ist

123
00:06:01,350 --> 00:06:05,820
wir werden die Anzahl Stick
28 in Feldposition 0.

124
00:06:05,820 --> 00:06:09,540
Ziemlich einfach, nicht wahr, dass
war der Top-und jetzt sind wir gut zu gehen.

125
00:06:09,540 --> 00:06:12,910
Und dann zu dem, was wir ändern müssen
Die Oberseite des Stapels wird.

126
00:06:12,910 --> 00:06:15,130
So daß das nächste Mal,
schieben wir ein Element,

127
00:06:15,130 --> 00:06:18,017
wir werden es in speichern
Array Lage, wahrscheinlich nicht 0.

128
00:06:18,017 --> 00:06:20,100
Wir wollen nicht zu überschreiben,
was wir dort setzen gerade.

129
00:06:20,100 --> 00:06:23,510
Und so werden wir nur bewegen Sie den oben nach 1.

130
00:06:23,510 --> 00:06:24,890
Das macht wohl Sinn.

131
00:06:24,890 --> 00:06:28,940
>> Wenn wir nun ein weiteres Element setzen wollen
auf den Stapel, sagen wir, bis 33 zu schieben möchten,

132
00:06:28,940 --> 00:06:33,190
und jetzt sind wir gerade dabei, 33 nehmen
und legen Sie sie auf Array Platznummer

133
00:06:33,190 --> 00:06:37,580
1, und ändern Sie dann die Spitze unserer
stapeln, um Matrixort Nummer zwei zu sein.

134
00:06:37,580 --> 00:06:40,650
Also, wenn das nächste Mal, wenn wir wollen,
drücken Sie ein Element auf den Stapel,

135
00:06:40,650 --> 00:06:43,087
es wird in der Anordnung Standort 2 gestellt werden.

136
00:06:43,087 --> 00:06:44,420
Und lassen Sie uns tun, dass man mehr Zeit.

137
00:06:44,420 --> 00:06:45,753
Wir drücken 19 Aus der Stapel.

138
00:06:45,753 --> 00:06:48,940
Wir werden 19 in Array Standort 2 gesetzt
und ändern Sie die Spitze unserer Stapel

139
00:06:48,940 --> 00:06:51,220
Array Lage 3 sein
so dass, wenn das nächste Mal, wenn wir

140
00:06:51,220 --> 00:06:54,780
brauchen, um eine Push wir sind gut zu gehen zu machen.

141
00:06:54,780 --> 00:06:56,980
>> OK, also ist das Schieben auf den Punkt.

142
00:06:56,980 --> 00:06:57,830
Was ist mit knallen?

143
00:06:57,830 --> 00:07:00,240
So knallen ist die Art von
Gegenstück zu schieben.

144
00:07:00,240 --> 00:07:02,720
Es ist, wie wir Daten aus dem Stapel zu entfernen.

145
00:07:02,720 --> 00:07:04,610
Und im allgemeinen pop Bedürfnisse
um Folgendes zu tun.

146
00:07:04,610 --> 00:07:07,600
Es braucht, um einen Zeiger auf die Annahme
Stapel, wieder in den allgemeinen Fall.

147
00:07:07,600 --> 00:07:10,480
In einem anderen Fall, dass Sie vielleicht
haben Sie den Stapel global deklariert,

148
00:07:10,480 --> 00:07:13,910
In diesem Fall brauchen Sie nicht, um es zu übergeben
in, da es bereits Zugang hat

149
00:07:13,910 --> 00:07:15,541
als globale Variable.

150
00:07:15,541 --> 00:07:17,040
Aber dann, was wir sonst noch tun müssen?

151
00:07:17,040 --> 00:07:21,000
Nun, wir waren Erhöhen
die Oberseite des Stapels in push,

152
00:07:21,000 --> 00:07:24,050
so dass wir wahrscheinlich gehen zu wollen,
um die Oberseite des Stapels zu dekrementieren

153
00:07:24,050 --> 00:07:25,009
in Pop, nicht wahr?

154
00:07:25,009 --> 00:07:26,800
Und dann natürlich
wir auch gehen zu wollen,

155
00:07:26,800 --> 00:07:29,240
um den Wert, den wir entfernen zurückzukehren.

156
00:07:29,240 --> 00:07:32,125
Wenn wir das Hinzufügen von Elementen wollen wir
Elemente später raus,

157
00:07:32,125 --> 00:07:34,000
wir wohl tatsächlich
wollen sie, so dass wir speichern

158
00:07:34,000 --> 00:07:36,490
nicht nur aus dem löschen
stapeln und dann nichts zu tun mit ihnen.

159
00:07:36,490 --> 00:07:38,500
Im Allgemeinen, wenn wir
Schieben und hier knallen

160
00:07:38,500 --> 00:07:41,250
wir diese speichern möchten
Informationen in sinnvoller Weise

161
00:07:41,250 --> 00:07:43,250
und so ist es nicht sinn
Sinn, nur verwerfen.

162
00:07:43,250 --> 00:07:46,380
So sollte diese Funktion
Wert wahrscheinlich zu uns zurückkehren.

163
00:07:46,380 --> 00:07:51,040
>> Also das ist, was eine Erklärung für die Pop-
könnte wie es in der oberen linken aussehen.

164
00:07:51,040 --> 00:07:53,870
Diese Funktion gibt
Daten vom Typ Wert.

165
00:07:53,870 --> 00:07:56,320
Wieder haben wir habe mit
Zahlen überall.

166
00:07:56,320 --> 00:08:01,916
Und es nimmt einen Zeiger auf einen Stapel als
das einzige Argument ist oder einzige Parameter.

167
00:08:01,916 --> 00:08:03,040
Also, was ist pop tun?

168
00:08:03,040 --> 00:08:07,990
Nehmen wir an, wir wollen jetzt
Pop ein Element aus der s.

169
00:08:07,990 --> 00:08:14,000
So erinnere ich mich, dass Stacks letzten
in, first out, LIFO-Datenstrukturen.

170
00:08:14,000 --> 00:08:17,855
Welches Element zu gehen wird
aus dem Stapel entfernt werden?

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
Haben Sie erraten, 19?

173
00:08:24,150 --> 00:08:25,290
Da hätten Sie recht.

174
00:08:25,290 --> 00:08:28,836
19 war das letzte Element, das wir auf der Mehr
stapeln, als wir an Schubelemente,

175
00:08:28,836 --> 00:08:31,210
und so ist es mit dem ersten gehen
Element, das entfernt wird.

176
00:08:31,210 --> 00:08:34,780
Es ist, als ob wir die 28, und
dann setzen wir 33 oben drauf,

177
00:08:34,780 --> 00:08:36,659
und wir haben 19 obendrein.

178
00:08:36,659 --> 00:08:40,650
Das einzige Element, die wir ergreifen können ausgeschaltet ist 19.

179
00:08:40,650 --> 00:08:45,019
>> Jetzt in der Grafik hier was ich getan habe
ist eine Art gelöscht 19 aus dem Array.

180
00:08:45,019 --> 00:08:46,810
Das ist nicht wirklich
was wir tun werden.

181
00:08:46,810 --> 00:08:48,934
Wir sind gerade dabei, Art
von so tun, es ist nicht da.

182
00:08:48,934 --> 00:08:51,441
Es ist immer noch da in
dass Speicherplatz,

183
00:08:51,441 --> 00:08:54,190
aber wir sind gerade dabei, es zu ignorieren
durch Ändern der Spitze unserer Stapel

184
00:08:54,190 --> 00:08:56,080
entfernt, 3-2.

185
00:08:56,080 --> 00:08:58,720
So, jetzt zu schieben, wenn wir
ein anderes Element auf dem Stapel,

186
00:08:58,720 --> 00:09:00,720
Es wäre mehr als 19 schreiben.

187
00:09:00,720 --> 00:09:03,990
>> Aber lasst uns nicht die Mühe zu gehen
das Löschen 19 von dem Stapel.

188
00:09:03,990 --> 00:09:05,830
Wir können einfach so tun, es ist nicht da.

189
00:09:05,830 --> 00:09:11,107
Für die Zwecke des Stapels ist es, wenn gegangen
wir die Spitze zu ändern, um 2 statt 3 sein.

190
00:09:11,107 --> 00:09:12,690
Na gut, das war so ziemlich alles.

191
00:09:12,690 --> 00:09:15,080
Das ist alles, was wir tun müssen
um ein Element abspringt.

192
00:09:15,080 --> 00:09:16,090
Lass uns das nochmal machen.

193
00:09:16,090 --> 00:09:18,610
Also habe ich es hier rot hervorgehoben
zeigen wir machen einen weiteren Anruf.

194
00:09:18,610 --> 00:09:19,720
Wir werden das gleiche tun.

195
00:09:19,720 --> 00:09:20,803
>> Also, was wird passieren?

196
00:09:20,803 --> 00:09:23,670
Nun, wir werden zu speichern
33 in x und wir werden

197
00:09:23,670 --> 00:09:26,217
um die Oberseite des Stapels auf 1 zu ändern.

198
00:09:26,217 --> 00:09:29,050
So dass, wenn wir nun auf ein Push
Element in den Stapel, die wir sind

199
00:09:29,050 --> 00:09:31,610
gehen zu tun, gerade jetzt,
was wird passieren

200
00:09:31,610 --> 00:09:36,367
wird wir überschreiben gehen
Array Platznummer 1.

201
00:09:36,367 --> 00:09:38,950
So dass 33, die Art von übrig blieb
hinter, dass wir nur vorgab

202
00:09:38,950 --> 00:09:44,390
nicht mehr da ist, sind wir gerade dabei
um es zu verprügeln und legte 40 dort statt.

203
00:09:44,390 --> 00:09:46,290
Und dann natürlich,
da wir einen Push,

204
00:09:46,290 --> 00:09:48,780
wir werden das Inkrement
Oberseite des Stapels 1-2

205
00:09:48,780 --> 00:09:50,950
so dass, wenn wir jetzt hinzufügen
ein weiteres Element, es wird

206
00:09:50,950 --> 00:09:54,700
gehen Sie in Feldposition Nummer zwei.

207
00:09:54,700 --> 00:09:57,590
>> Jetzt verkettete Listen sind ein weiterer
Weg, um Stapel zu implementieren.

208
00:09:57,590 --> 00:10:01,210
Und wenn dieser Definition auf die
Bildschirm Hier schaut Ihnen vertraut,

209
00:10:01,210 --> 00:10:04,260
es ist, weil es sieht fast aus
genau gleich sind, in der Tat,

210
00:10:04,260 --> 00:10:07,790
es ziemlich viel ist genau die
Gleiche wie eine einfach verkettete Liste,

211
00:10:07,790 --> 00:10:11,990
wenn Sie von unserer Diskussion erinnern
einzeln in einem anderen Video-verknüpften Listen.

212
00:10:11,990 --> 00:10:15,510
Die einzige Einschränkung hier
ist für uns als Programmierer,

213
00:10:15,510 --> 00:10:17,900
wir dürfen nicht
einfügen oder löschen Zufallsprinzip

214
00:10:17,900 --> 00:10:20,620
aus der einzeln verkettete Liste
die wir vorher tun könnte.

215
00:10:20,620 --> 00:10:25,820
Wir können nur jetzt einlegen und aus löschen
der Vorder- oder Oberseite des verknüpften

216
00:10:25,820 --> 00:10:26,320
Liste.

217
00:10:26,320 --> 00:10:28,028
Das ist wirklich die einzige
Unterschied though.

218
00:10:28,028 --> 00:10:29,700
Das ist sonst eine einfach verkettete Liste.

219
00:10:29,700 --> 00:10:32,060
Es ist nur die Beschränkung
Ersatz an uns selbst

220
00:10:32,060 --> 00:10:35,770
wie Programmierer,
verwandelt es sich in einem Stapel.

221
00:10:35,770 --> 00:10:39,280
>> Die Regel hier ist, um immer einen
Zeiger auf den Kopf einer verketteten Liste.

222
00:10:39,280 --> 00:10:41,520
Das ist natürlich eine allgemein
wichtige Regel zuerst.

223
00:10:41,520 --> 00:10:44,260
Für einfach verkettete Liste irgendwie, das Sie
brauchen nur einen Zeiger auf den Kopf

224
00:10:44,260 --> 00:10:46,160
Um dies zu haben
Kette in der Lage, zu beziehen

225
00:10:46,160 --> 00:10:48,596
zu jedem anderen Element
in der verknüpften Liste.

226
00:10:48,596 --> 00:10:50,470
Aber es ist vor allem
wichtig mit einem Stapel.

227
00:10:50,470 --> 00:10:52,386
Und so in der Regel sind Sie
gehen, um wirklich wollen

228
00:10:52,386 --> 00:10:54,090
Diese Zeiger auf eine globale Variable sein.

229
00:10:54,090 --> 00:10:56,574
Es ist wahrscheinlich zu
sogar noch einfacher.

230
00:10:56,574 --> 00:10:58,240
Was also sind die Analoga von Push- und Pop?

231
00:10:58,240 --> 00:10:58,740
Recht.

232
00:10:58,740 --> 00:11:01,812
Also noch einmal drücken wird das Hinzufügen
ein neues Element in den Stapel.

233
00:11:01,812 --> 00:11:03,770
In einer verknüpften Liste,
bedeutet, dass wir gehen zu müssen,

234
00:11:03,770 --> 00:11:07,770
um einen neuen Knoten, die wir erstellen
gehen, um sich der Liste hinzuzufügen,

235
00:11:07,770 --> 00:11:10,500
und befolgen Sie die vorsichtige Schritte
dass wir vorher skizziert habe,

236
00:11:10,500 --> 00:11:16,050
in einfach verkettete Listen, um sie hinzuzufügen
die Kette ohne die Kette

237
00:11:16,050 --> 00:11:18,900
und verlieren oder zu verwaisen jede
Elemente der verketteten Liste.

238
00:11:18,900 --> 00:11:21,820
Und das ist im Grunde, was das
kleinen Klecks Text gibt einen Überblick.

239
00:11:21,820 --> 00:11:23,740
Und lassen Sie uns einen Blick
es als ein Diagramm.

240
00:11:23,740 --> 00:11:24,823
>> Also hier ist unsere verknüpften Liste.

241
00:11:24,823 --> 00:11:26,620
Es enthält gleichzeitig vier Elemente.

242
00:11:26,620 --> 00:11:30,420
Und mehr perfekt hier ist unsere
Stack mit vier Elementen.

243
00:11:30,420 --> 00:11:36,030
Und lassen Sie uns sagen, wir wollen jetzt
drücken Sie ein neues Element auf diesem Stapel.

244
00:11:36,030 --> 00:11:39,792
Und wir ein neues zu schieben möchten
Artikel, deren Datenwert ist 12.

245
00:11:39,792 --> 00:11:41,000
Nun, was sollen wir tun?

246
00:11:41,000 --> 00:11:43,420
Nun zunächst sind wir zu gehen
malloc Raum, dynamisch

247
00:11:43,420 --> 00:11:45,411
Speicherplatz zuweisen für einen neuen Knoten.

248
00:11:45,411 --> 00:11:48,160
Und selbstverständlich unmittelbar nach
Wir machen einen Aufruf an die wir immer malloc

249
00:11:48,160 --> 00:11:52,989
stellen Sie sicher, für null zu überprüfen,
denn wenn wir null zurückkamen

250
00:11:52,989 --> 00:11:54,280
es war eine Art von Problem.

251
00:11:54,280 --> 00:11:57,570
Wir wollen nicht zu dereferenzieren, die NULL
Zeiger oder Sie eine seg Störung leiden.

252
00:11:57,570 --> 00:11:58,510
Das ist nicht gut.

253
00:11:58,510 --> 00:11:59,760
Also haben wir des Knotens malloced habe.

254
00:11:59,760 --> 00:12:01,260
Wir gehen davon aus, wir haben Erfolg hatte hier.

255
00:12:01,260 --> 00:12:06,090
Wir werden 12 kannst
das Datenfeld dieses Knotens.

256
00:12:06,090 --> 00:12:11,570
Jetzt müssen Sie sich erinnern was unserer Zeigern
bewegt sich weiter, so dass wir die Kette nicht zu brechen?

257
00:12:11,570 --> 00:12:15,100
Wir haben ein paar Optionen hier, aber
das einzige, das geht sicher zu sein

258
00:12:15,100 --> 00:12:19,330
ist es, Nachrichten nächsten Zeiger zu setzen
Punkt zum alten Kopf der Liste

259
00:12:19,330 --> 00:12:21,360
oder was wird bald die
alte Spitze der Liste.

260
00:12:21,360 --> 00:12:23,610
Und jetzt, da alle unsere
Elemente werden miteinander verkettet,

261
00:12:23,610 --> 00:12:27,370
wir können einfach bewegen Liste zu Punkt
an der gleichen Stelle, die neuen tut.

262
00:12:27,370 --> 00:12:33,550
Und wir haben nun effektiv geschoben a
neues Element auf der Vorderseite des Stapels.

263
00:12:33,550 --> 00:12:36,420
>> Um wir wollen einfach nur Pop-
löschen Sie diese erste Element.

264
00:12:36,420 --> 00:12:38,150
Und so im Grunde, was
Wir haben hier zu tun,

265
00:12:38,150 --> 00:12:40,050
auch wir haben, um das zweite Element zu finden.

266
00:12:40,050 --> 00:12:43,540
Schließlich, dass das neue geworden
Kopf, nachdem wir die erste löschen.

267
00:12:43,540 --> 00:12:47,300
Also müssen wir nur noch aus starten
der Anfang, verschieben Sie eine nach vorn.

268
00:12:47,300 --> 00:12:50,340
Sobald wir einen Halt auf der einen stand
vorne, wo wir aktuell

269
00:12:50,340 --> 00:12:53,850
sind wir die erste sicher löschen
und dann können wir nur den Kopf bewegen

270
00:12:53,850 --> 00:12:57,150
zu dem, was war, zeigen die
zweite Amtszeit und jetzt dann

271
00:12:57,150 --> 00:12:59,170
ist das erste danach
Knoten gelöscht wurde.

272
00:12:59,170 --> 00:13:01,160
>> Also noch einmal, sich einen Blick
es als ein Diagramm wir

273
00:13:01,160 --> 00:13:05,022
will jetzt ein Pop-
Element weg von diesem Stapel.

274
00:13:05,022 --> 00:13:05,730
Also, was machen wir?

275
00:13:05,730 --> 00:13:08,188
Nun wir zuerst zu erstellen
ein neuer Zeiger, die gehen

276
00:13:08,188 --> 00:13:10,940
an der gleichen Stelle wie der Kopf zeigen.

277
00:13:10,940 --> 00:13:13,790
Wir werden sie um eine Position
vorne mit den Worten trav equals

278
00:13:13,790 --> 00:13:17,510
trav nächsten zum Beispiel, die
würde die trav Zeiger einem voran

279
00:13:17,510 --> 00:13:19,324
Position nach vorne.

280
00:13:19,324 --> 00:13:21,240
Jetzt, wo wir haben ein
Halten Sie auf dem ersten Element

281
00:13:21,240 --> 00:13:24,573
durch den Zeiger namens Liste und die
zweite Element durch einen Zeiger namens

282
00:13:24,573 --> 00:13:28,692
trav, können wir sicher zu löschen, dass
das erste Element aus dem Stapel

283
00:13:28,692 --> 00:13:30,650
ohne den Rest zu verlieren
der Kette, weil wir

284
00:13:30,650 --> 00:13:32,358
eine Möglichkeit haben, beziehen
an dem zweiten Element

285
00:13:32,358 --> 00:13:34,780
mitteln über das
Zeiger namens trav.

286
00:13:34,780 --> 00:13:37,100
>> So, jetzt können wir diese Knoten zu befreien.

287
00:13:37,100 --> 00:13:38,404
Wir können die Liste zu befreien.

288
00:13:38,404 --> 00:13:41,320
Und dann alles, was wir jetzt tun müssen, ist,
bewegen Liste Punkt an der gleichen Stelle

289
00:13:41,320 --> 00:13:44,482
dass trav tut, und wir sind Art von Rück
wo wir angefangen haben, bevor wir 12 geschoben

290
00:13:44,482 --> 00:13:45,690
auf in den ersten Platz, richtig.

291
00:13:45,690 --> 00:13:46,940
Das ist genau das, wo wir waren.

292
00:13:46,940 --> 00:13:48,840
Wir hatten diese vier Elementstapel.

293
00:13:48,840 --> 00:13:49,690
Wir haben ein Fünftel.

294
00:13:49,690 --> 00:13:51,910
Wir schoben einen fünften
Element auf, und dann werden wir

295
00:13:51,910 --> 00:13:55,980
geknallt, dass die zuletzt
Mehrelement wieder aus.

296
00:13:55,980 --> 00:13:58,816
>> Das ist wirklich ziemlich
alles, was man stapelt.

297
00:13:58,816 --> 00:14:00,190
Sie können sie als Arrays zu implementieren.

298
00:14:00,190 --> 00:14:01,815
Sie können sie als verkettete Listen zu implementieren.

299
00:14:01,815 --> 00:14:04,810
Es gibt natürlich andere
Möglichkeiten, auch diese zu implementieren.

300
00:14:04,810 --> 00:14:09,060
Grundsätzlich ist der Grund, warum wir verwenden würden,
Stapeln ist es, Daten in unter- halten

301
00:14:09,060 --> 00:14:12,090
dass der zuletzt hinzugefügten
Element ist das erste, was wir sind

302
00:14:12,090 --> 00:14:14,980
gehen zu wollen, zurück zu bekommen.

303
00:14:14,980 --> 00:14:17,900
Ich bin Doug Lloyd, ist dies CS50.

304
00:14:17,900 --> 00:14:19,926