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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Oké,
dus door dit punt bent

3
00:00:05,990 --> 00:00:09,020
waarschijnlijk vrij vertrouwd
met arrays en gelinkte lijsten

4
00:00:09,020 --> 00:00:10,950
dat de twee belangrijkste
datastructuren we hebben

5
00:00:10,950 --> 00:00:16,810
sprak over voor het houden sets
gegevens van soortgelijke data georganiseerd.

6
00:00:16,810 --> 00:00:19,080
>> Nu gaan we praten
over een paar variaties

7
00:00:19,080 --> 00:00:20,330
arrays en gelinkte lijsten.

8
00:00:20,330 --> 00:00:22,362
In deze video gaan we
om te praten over stapels.

9
00:00:22,362 --> 00:00:25,320
Concreet gaan we praten
over een gegevensstructuur genaamd een stapel.

10
00:00:25,320 --> 00:00:28,510
Recall van eerdere discussies
over pointers en het geheugen,

11
00:00:28,510 --> 00:00:32,060
of de stapel ook
naam voor een segment van het geheugen

12
00:00:32,060 --> 00:00:34,980
waarbij statisch verklaard
memory-- geheugen dat u

13
00:00:34,980 --> 00:00:38,730
naam, variabelen die u noemt, et
cetera en functie frames die ook

14
00:00:38,730 --> 00:00:41,000
call-stack frames bestaan.

15
00:00:41,000 --> 00:00:45,421
Dit is dus een stapel datastructuur
geen stack segment van het geheugen.

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

17
00:00:45,920 --> 00:00:46,890
>> Maar wat is een stapel?

18
00:00:46,890 --> 00:00:49,220
Dus het is vrij veel slechts een
speciaal soort structuur

19
00:00:49,220 --> 00:00:51,190
dat de gegevens handhaaft op een georganiseerde manier.

20
00:00:51,190 --> 00:00:53,760
En er zijn twee zeer
voorkomende manieren om te implementeren

21
00:00:53,760 --> 00:00:57,380
stapels met twee gegevensstructuren
dat we al bekend zijn met,

22
00:00:57,380 --> 00:01:00,340
arrays en gelinkte lijsten.

23
00:01:00,340 --> 00:01:04,430
Wat maakt een stapel speciaal is de
manier waarop plaatsen we informatie

24
00:01:04,430 --> 00:01:08,200
in de stack, en de manier waarop we
Verwijder informatie van de stapel.

25
00:01:08,200 --> 00:01:11,600
Vooral met stapels
de regel is alleen de meest

26
00:01:11,600 --> 00:01:15,830
recent toegevoegde element kan worden verwijderd.

27
00:01:15,830 --> 00:01:17,660
>> Dus denk erover alsof het een stapel.

28
00:01:17,660 --> 00:01:21,170
We stapelen informatie
bovenop zichzelf,

29
00:01:21,170 --> 00:01:24,271
en alleen de ding boven
van de paal kan worden verwijderd.

30
00:01:24,271 --> 00:01:27,020
We kunnen het niet verwijderen van de zaak onder
omdat alles anders zou

31
00:01:27,020 --> 00:01:28,020
instorten en omvallen.

32
00:01:28,020 --> 00:01:32,580
Dus we bouwen een stack die
we dan moeten stuk voor stuk te verwijderen.

33
00:01:32,580 --> 00:01:36,590
Hierdoor hebben we vaak verwijzen
Stapels als LIFO structuur,

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
>> Omdat deze beperking
hoe informatie kan worden toegevoegd aan

37
00:01:45,635 --> 00:01:49,080
en verwijderd uit een stapel, er is echt
slechts twee dingen die we kunnen doen met een stack.

38
00:01:49,080 --> 00:01:52,010
We kunnen duwen, wat het
term die we gebruiken voor het toevoegen

39
00:01:52,010 --> 00:01:55,130
een nieuw element aan de bovenkant van de
stack of wanneer de stapel niet bestaat

40
00:01:55,130 --> 00:01:58,550
en we zijn er creëren vanuit het niets,
het creëren van de stapel in de eerste plaats

41
00:01:58,550 --> 00:02:00,110
zou duwen.

42
00:02:00,110 --> 00:02:04,990
En pop dan, dat is het soort van CS
term die we gebruiken om de meest recent verwijderen

43
00:02:04,990 --> 00:02:08,330
toegevoegde element van de bovenkant van de stapel.

44
00:02:08,330 --> 00:02:11,130
>> Dus we gaan op zowel kijken
implementaties, zowel array gebaseerde

45
00:02:11,130 --> 00:02:13,120
en gelinkte lijst gebaseerd.

46
00:02:13,120 --> 00:02:14,870
En we gaan
beginnen met array gebaseerde.

47
00:02:14,870 --> 00:02:19,990
Dus hier is het basisidee van wat
de array gebaseerde stack datastructuur

48
00:02:19,990 --> 00:02:21,140
eruit zou zien.

49
00:02:21,140 --> 00:02:23,740
We hebben een getypte definitie hier.

50
00:02:23,740 --> 00:02:27,790
Binnenkant van dat we twee leden
of gebied van de structuur.

51
00:02:27,790 --> 00:02:29,880
We hebben een scala.

52
00:02:29,880 --> 00:02:32,400
En nogmaals, ik ben met behulp van de
willekeurige data type waarde.

53
00:02:32,400 --> 00:02:35,180
>> Dus dit elk gegevenstype kan zijn,
int char of een andere data

54
00:02:35,180 --> 00:02:37,080
typt u eerder hebt gemaakt.

55
00:02:37,080 --> 00:02:39,861
Dus we hebben een scala van grootte capaciteit.

56
00:02:39,861 --> 00:02:44,010
Capaciteit wordt een pond gedefinieerd constant,
misschien ergens anders in ons bestand.

57
00:02:44,010 --> 00:02:47,550
Zo merkt al met deze
implementatie wij begrenzende

58
00:02:47,550 --> 00:02:49,800
onszelf als typisch was
het geval met arrays

59
00:02:49,800 --> 00:02:53,170
die we kunnen niet dynamisch vergroten of verkleinen,
waar een aantal

60
00:02:53,170 --> 00:02:55,450
maximale elementen
we kunnen zetten in onze stack.

61
00:02:55,450 --> 00:02:57,930
In dit geval is het vermogen elementen.

62
00:02:57,930 --> 00:03:00,310
>> We houden ook het bijhouden van
de bovenkant van de stapel.

63
00:03:00,310 --> 00:03:04,350
Wat element is de
onlangs toegevoegd aan de stapel?

64
00:03:04,350 --> 00:03:07,470
En zo houden we van die
in een top variabele genaamd.

65
00:03:07,470 --> 00:03:11,692
En dit alles wordt samen verpakt
een nieuw datatype zogenaamde stack.

66
00:03:11,692 --> 00:03:13,400
En zodra we zijn geschapen
dit nieuwe type data

67
00:03:13,400 --> 00:03:15,410
kunnen we het behandelen als
andere soorten data.

68
00:03:15,410 --> 00:03:20,970
We kunnen verklaren stack s, net als
we konden int x, y of klusje doen.

69
00:03:20,970 --> 00:03:22,990
En als we zeggen stapelen
s, goed wat er gebeurt

70
00:03:22,990 --> 00:03:26,420
is krijgen we een set van
geheugen gereserveerd voor ons.

71
00:03:26,420 --> 00:03:28,770
>> In dit geval wordt de capaciteit
Ik heb blijkbaar besloten

72
00:03:28,770 --> 00:03:33,470
10 omdat ik heb
enkele variabele van het type stack

73
00:03:33,470 --> 00:03:35,320
die bevat twee velden te roepen.

74
00:03:35,320 --> 00:03:38,330
Een array, in dit geval gaat
een array van gehele getallen

75
00:03:38,330 --> 00:03:40,440
zoals in de meeste van mijn voorbeelden.

76
00:03:40,440 --> 00:03:43,996
En een andere integer variabele
geschikt voor het opslaan boven,

77
00:03:43,996 --> 00:03:45,870
De meest recent toegevoegde
element om de stapel.

78
00:03:45,870 --> 00:03:50,290
Dus één stapel van wat wij
net gedefinieerd ziet er als volgt.

79
00:03:50,290 --> 00:03:53,190
Het is een doos met
een array van 10 wat

80
00:03:53,190 --> 00:03:57,280
zal zijn gehele getallen in deze zaak en
een andere integer variabele er in het groen

81
00:03:57,280 --> 00:04:00,010
naar de top van de stack geven.

82
00:04:00,010 --> 00:04:02,600
>> Naar de top van de termijn
stack we gewoon s.top zeggen.

83
00:04:02,600 --> 00:04:04,890
Dat is hoe we toegang tot een
veld van een structuur recall.

84
00:04:04,890 --> 00:04:10,460
s.top gelijk is aan 0 effectief
Dit doet ons stack.

85
00:04:10,460 --> 00:04:12,960
Dus nogmaals hebben we twee operaties
dat we nu kunnen uitvoeren.

86
00:04:12,960 --> 00:04:14,270
We kunnen duwen en we kunnen pop.

87
00:04:14,270 --> 00:04:15,635
Laten we beginnen met push.

88
00:04:15,635 --> 00:04:18,260
Nogmaals, het duwen is het toevoegen van een nieuwe
element naar de top van de stack.

89
00:04:18,260 --> 00:04:21,460
>> Dus wat moeten we doen
deze array gebaseerde implementatie?

90
00:04:21,460 --> 00:04:23,210
Welnu, in het algemeen de
push-functie gaat

91
00:04:23,210 --> 00:04:26,160
nodig hebben om een ​​accepteren
Pointer naar de stapel.

92
00:04:26,160 --> 00:04:28,610
Neem nu een tweede en denk erover na.

93
00:04:28,610 --> 00:04:32,840
Waarom zouden we willen accepteren
een pointer naar de stapel?

94
00:04:32,840 --> 00:04:36,830
Recall van de vorige video's op
variabele reikwijdte en pointers,

95
00:04:36,830 --> 00:04:42,350
wat er zou gebeuren als we gewoon gestuurd
stack, s plaats in als een parameter?

96
00:04:42,350 --> 00:04:45,770
Wat zou eigenlijk worden doorgegeven daar?

97
00:04:45,770 --> 00:04:49,430
Vergeet niet dat we het maken van een kopie
als we doorgeven aan een functie

98
00:04:49,430 --> 00:04:51,160
tenzij we gebruiken pointers.

99
00:04:51,160 --> 00:04:55,380
En dus deze functie te duwen behoeften
een pointer naar de stapel accepteren

100
00:04:55,380 --> 00:04:59,160
zodat we daadwerkelijk te veranderen
de stapel willen we veranderen.

101
00:04:59,160 --> 00:05:03,060
>> Het andere ding push waarschijnlijk wil
aanvaarden is een data-element van het type waarde.

102
00:05:03,060 --> 00:05:06,970
In dit geval weer een geheel getal dat
we gaan toe te voegen aan de top van de stapel.

103
00:05:06,970 --> 00:05:08,680
Dus we hebben onze twee parameters.

104
00:05:08,680 --> 00:05:11,310
Wat gaan we
nu doen binnenkant van push?

105
00:05:11,310 --> 00:05:14,860
Nou, gewoon, we gaan gewoon om toe te voegen
dat element aan de bovenkant van de stapel

106
00:05:14,860 --> 00:05:22,860
en wijzig waar de top van
de stapel, dat S DOT top waarde.

107
00:05:22,860 --> 00:05:25,639
Dus dit is wat een functie
verklaring voor push

108
00:05:25,639 --> 00:05:27,680
eruit zou kunnen zien in een
array-gebaseerde implementatie.

109
00:05:27,680 --> 00:05:30,967
>> Ook dit is niet een harde en snelle regel
dat je dit zou kunnen veranderen en

110
00:05:30,967 --> 00:05:32,050
Het variëren op verschillende manieren.

111
00:05:32,050 --> 00:05:33,840
Misschien s is wereldwijd uitgeroepen.

112
00:05:33,840 --> 00:05:36,180
En dus heb je niet eens nodig
pass is als een parameter.

113
00:05:36,180 --> 00:05:39,125
Dit is opnieuw slechts een
algemene geval voor push.

114
00:05:39,125 --> 00:05:41,000
Er zijn verschillende
manieren om het uit te voeren.

115
00:05:41,000 --> 00:05:42,810
Maar in dit geval onze
push gaat nemen

116
00:05:42,810 --> 00:05:48,540
twee argumenten, een pointer naar een stapel en
een data-element van het type waarde, integer

117
00:05:48,540 --> 00:05:49,840
in dit geval.

118
00:05:49,840 --> 00:05:52,100
>> Dus we verklaard s, we
zei s.top gelijk is aan 0.

119
00:05:52,100 --> 00:05:55,969
Laten we nu druk op de
nummer 28 op de stapel.

120
00:05:55,969 --> 00:05:57,010
Tja, wat betekent dat?

121
00:05:57,010 --> 00:05:59,600
Goed moment de
bovenkant van de stapel 0.

122
00:05:59,600 --> 00:06:01,350
En dus wat is eigenlijk
gaat gebeuren is

123
00:06:01,350 --> 00:06:05,820
we gaan het aantal steken
28 in de serie locatie 0.

124
00:06:05,820 --> 00:06:09,540
Vrij eenvoudig, recht, dat
was de top en nu zijn we goed om te gaan.

125
00:06:09,540 --> 00:06:12,910
En dan moeten we wat veranderen
de top van de stack wordt.

126
00:06:12,910 --> 00:06:15,130
Zodat de volgende keer
duwen we een element,

127
00:06:15,130 --> 00:06:18,017
we gaan het op te slaan in
scala locatie, waarschijnlijk niet 0.

128
00:06:18,017 --> 00:06:20,100
We willen niet overschrijven
wat we daar te zetten gewoon.

129
00:06:20,100 --> 00:06:23,510
En dus gaan we gewoon verder de top naar 1.

130
00:06:23,510 --> 00:06:24,890
Dat maakt het waarschijnlijk zinvol.

131
00:06:24,890 --> 00:06:28,940
>> Nu willen we een ander element te zetten
op de stapel, zeggen we willen duwen 33,

132
00:06:28,940 --> 00:06:33,190
en nu zijn we gewoon gaan nemen 33
en zet het op scala locatie nummer

133
00:06:33,190 --> 00:06:37,580
1, en wijzig de top van onze
stack array plaats nummer twee.

134
00:06:37,580 --> 00:06:40,650
Dus als de volgende keer dat we willen
duwen een element op de stack,

135
00:06:40,650 --> 00:06:43,087
het zal in slagorde locatie 2 worden gezet.

136
00:06:43,087 --> 00:06:44,420
En laten we dat nog een keer.

137
00:06:44,420 --> 00:06:45,753
We zullen duwen 19 off van de stacks.

138
00:06:45,753 --> 00:06:48,940
We zullen 19 toegerust locatie 2 zetten
en verander de top van onze stack

139
00:06:48,940 --> 00:06:51,220
array locatie 3 zijn
dus als we de volgende keer

140
00:06:51,220 --> 00:06:54,780
moet een push we goed te gaan maken.

141
00:06:54,780 --> 00:06:56,980
>> OK, dus dat is het duwen in een notendop.

142
00:06:56,980 --> 00:06:57,830
Hoe zit het met popping?

143
00:06:57,830 --> 00:07:00,240
Dus popping is het soort
tegenhanger duwen.

144
00:07:00,240 --> 00:07:02,720
Het is hoe we gegevens uit de stapel te verwijderen.

145
00:07:02,720 --> 00:07:04,610
En in het algemeen pop behoeften
het volgende doen.

146
00:07:04,610 --> 00:07:07,600
Het moet een verwijzing naar het accepteren
stack, opnieuw het algemene geval.

147
00:07:07,600 --> 00:07:10,480
In sommige andere geval je misschien
hebben de stapel wereldwijd verklaard,

148
00:07:10,480 --> 00:07:13,910
in welk geval u niet hoeft door te geven
in want het heeft al toegang tot deze

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

150
00:07:15,541 --> 00:07:17,040
Maar wat anders doen we moeten doen?

151
00:07:17,040 --> 00:07:21,000
Wel waren we verhogen
de bovenkant van de stapel duwen,

152
00:07:21,000 --> 00:07:24,050
dus we waarschijnlijk zal willen
aan de bovenkant van de stapel verlagen

153
00:07:24,050 --> 00:07:25,009
in pop, toch?

154
00:07:25,009 --> 00:07:26,800
En dan natuurlijk
We zijn ook van plan te willen

155
00:07:26,800 --> 00:07:29,240
de waarde die we verwijderen terugkeren.

156
00:07:29,240 --> 00:07:32,125
Als we elementen toe te voegen, willen we
elementen later op te krijgen,

157
00:07:32,125 --> 00:07:34,000
we waarschijnlijk eigenlijk
willen ze dus we slaan

158
00:07:34,000 --> 00:07:36,490
ze niet gewoon verwijderen van de
stapelen en vervolgens niets doen met hen.

159
00:07:36,490 --> 00:07:38,500
Over het algemeen als we
duwen en hier popping

160
00:07:38,500 --> 00:07:41,250
We willen dit op te slaan
informatie op een zinvolle manier

161
00:07:41,250 --> 00:07:43,250
en zo is het niet maken
zin om gewoon gooi hem weg.

162
00:07:43,250 --> 00:07:46,380
Dus deze functie moet
Waarschijnlijk een waarde terug te keren naar ons.

163
00:07:46,380 --> 00:07:51,040
>> Dus dit is wat een verklaring voor pop
eruit zou kunnen zien is er in de linkerbovenhoek.

164
00:07:51,040 --> 00:07:53,870
Deze functie geeft
gegevens van het type waarde.

165
00:07:53,870 --> 00:07:56,320
Opnieuw hebben we het gebruik geweest
integers overal.

166
00:07:56,320 --> 00:08:01,916
En een pointer naar een stack accepteert
zijn enige argument of enige parameter.

167
00:08:01,916 --> 00:08:03,040
Dus wat is pop gaat doen?

168
00:08:03,040 --> 00:08:07,990
Laten we zeggen dat we willen nu
pop een element uit van s.

169
00:08:07,990 --> 00:08:14,000
Dus onthoud ik zei dat stapels zijn laatste
in, first out, LIFO datastructuren.

170
00:08:14,000 --> 00:08:17,855
Welk element gaat
van de stapel worden verwijderd?

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

172
00:08:21,780 --> 00:08:24,150
Hebt u raden 19?

173
00:08:24,150 --> 00:08:25,290
Omdat je gelijk zou zijn.

174
00:08:25,290 --> 00:08:28,836
19 was het laatste element we toegevoegd
stack toen we duwen elementen op,

175
00:08:28,836 --> 00:08:31,210
en zo het gaat om de eerste
element dat wordt verwijderd.

176
00:08:31,210 --> 00:08:34,780
Het is alsof we zeiden 28 en
dan zetten we 33 op de top van het,

177
00:08:34,780 --> 00:08:36,659
en zetten we 19 op de top van dat.

178
00:08:36,659 --> 00:08:40,650
Het enige element kunnen we opstijgen is 19.

179
00:08:40,650 --> 00:08:45,019
>> Nu in het diagram hier wat ik heb gedaan
is een soort van 19 verwijderd uit de array.

180
00:08:45,019 --> 00:08:46,810
Dat is niet echt
wat we gaan doen.

181
00:08:46,810 --> 00:08:48,934
We gaan gewoon naar soort
van te doen alsof het er niet is.

182
00:08:48,934 --> 00:08:51,441
Het is er nog steeds in
dat het geheugen locatie,

183
00:08:51,441 --> 00:08:54,190
maar we gaan gewoon te negeren
door het veranderen van de top van onze stack

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

185
00:08:56,080 --> 00:08:58,720
Dus als we nu te duwen
een ander element op de stack,

186
00:08:58,720 --> 00:09:00,720
het zou dan te schrijven 19.

187
00:09:00,720 --> 00:09:03,990
>> Maar laten we niet gaan door de moeite
schrappen 19 van de stapel.

188
00:09:03,990 --> 00:09:05,830
We kunnen net doen alsof het er niet is.

189
00:09:05,830 --> 00:09:11,107
Voor de toepassing van de stapel het is gegaan als
we veranderen boven om 2 in plaats van 3.

190
00:09:11,107 --> 00:09:12,690
Oké, dus dat was het wel zo'n beetje.

191
00:09:12,690 --> 00:09:15,080
Dat is alles wat we moeten doen
een element knallen.

192
00:09:15,080 --> 00:09:16,090
Laten we het nog eens doen.

193
00:09:16,090 --> 00:09:18,610
Dus ik heb het rood gemarkeerd hier
geven we een andere oproep maken.

194
00:09:18,610 --> 00:09:19,720
We gaan hetzelfde doen.

195
00:09:19,720 --> 00:09:20,803
>> Dus wat gaat er gebeuren?

196
00:09:20,803 --> 00:09:23,670
Nou, we gaan slaan
33 in x en we gaan

197
00:09:23,670 --> 00:09:26,217
naar de top van de stack veranderen 1.

198
00:09:26,217 --> 00:09:29,050
Dus dat als we nu een push
element in de stapel die we

199
00:09:29,050 --> 00:09:31,610
ga naar rechts nu doen,
wat gaat er gebeuren

200
00:09:31,610 --> 00:09:36,367
is we gaan overschrijven
scala locatie nummer 1.

201
00:09:36,367 --> 00:09:38,950
Zodat 33 dat soort werd achtergelaten
achter dat we net alsof

202
00:09:38,950 --> 00:09:44,390
is er niet meer, we gewoon gaan
om het afranselen en zet 40 daar van harte welkom.

203
00:09:44,390 --> 00:09:46,290
En dan natuurlijk,
omdat we maakten een duw,

204
00:09:46,290 --> 00:09:48,780
we gaan naar het verhogen
bovenkant van de stapel 1-2

205
00:09:48,780 --> 00:09:50,950
dus dat als we nu toevoegen
een ander element het zal

206
00:09:50,950 --> 00:09:54,700
ga in serie plaats nummer twee.

207
00:09:54,700 --> 00:09:57,590
>> Nu gekoppelde lijsten ander
manier om stapels voeren.

208
00:09:57,590 --> 00:10:01,210
Als deze definitie op
screen hier ziet er bekend uit voor u,

209
00:10:01,210 --> 00:10:04,260
het is want het ziet er bijna
dezelfde, in feite,

210
00:10:04,260 --> 00:10:07,790
het vrij veel is precies
hetzelfde als enkelvoudig gekoppelde lijst,

211
00:10:07,790 --> 00:10:11,990
Als u zich herinneren van onze bespreking van
enkelvoudig gelinkte lijsten in een andere video.

212
00:10:11,990 --> 00:10:15,510
De enige beperking hier
is voor ons als programmeurs,

213
00:10:15,510 --> 00:10:17,900
we zijn niet toegestaan
invoegen of verwijderen willekeurig

214
00:10:17,900 --> 00:10:20,620
uit de enkelvoudig gelinkte lijst
die we eerder konden doen.

215
00:10:20,620 --> 00:10:25,820
We kunnen nu alleen invoegen en verwijderen uit
de voor- of bovenzijde van de gekoppelde

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

217
00:10:26,320 --> 00:10:28,028
Dat is echt de enige
verschil hoor.

218
00:10:28,028 --> 00:10:29,700
Dit is anders een enkelvoudig gelinkte lijst.

219
00:10:29,700 --> 00:10:32,060
Het is slechts de beperking
vervangen onszelf

220
00:10:32,060 --> 00:10:35,770
als programmeurs dat
verandert het in een stapel.

221
00:10:35,770 --> 00:10:39,280
>> De regel is hier altijd een
Pointer naar het hoofd van een gekoppelde lijst.

222
00:10:39,280 --> 00:10:41,520
Dit is natuurlijk algemeen
belangrijke regel als eerste.

223
00:10:41,520 --> 00:10:44,260
Voor afzonderlijk gelinkte lijst toch je
alleen een pointer naar de kop

224
00:10:44,260 --> 00:10:46,160
om te hebben dat
keten kunnen verwijzen

225
00:10:46,160 --> 00:10:48,596
elk ander element
in de gekoppelde lijst.

226
00:10:48,596 --> 00:10:50,470
Maar het is vooral
belangrijk bij een stack.

227
00:10:50,470 --> 00:10:52,386
En dus over het algemeen je bent
gaat eigenlijk willen

228
00:10:52,386 --> 00:10:54,090
Deze pointer naar een globale variabele.

229
00:10:54,090 --> 00:10:56,574
Het gaat waarschijnlijk
zelfs gemakkelijker op die manier.

230
00:10:56,574 --> 00:10:58,240
Dus wat zijn de analogen van push en pop?

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

232
00:10:58,740 --> 00:11:01,812
Dus nogmaals duwen voegt
een nieuw element aan de stapel.

233
00:11:01,812 --> 00:11:03,770
In een gekoppelde lijst die
betekent dat we gaan moeten

234
00:11:03,770 --> 00:11:07,770
naar een nieuw knooppunt dat we creëren
ga toe te voegen in de gelinkte lijst,

235
00:11:07,770 --> 00:11:10,500
en volg de voorzichtige stappen
die we eerder hebben geschetst

236
00:11:10,500 --> 00:11:16,050
in afzonderlijk gelinkte lijsten toe te voegen aan
de ketting zonder de ketting

237
00:11:16,050 --> 00:11:18,900
en het verliezen of orphaning elke
elementen van de gekoppelde lijst.

238
00:11:18,900 --> 00:11:21,820
En dat is eigenlijk wat dat
kleine blob van tekst is er een samenvatting.

239
00:11:21,820 --> 00:11:23,740
En laten we eens een kijkje
het als een diagram.

240
00:11:23,740 --> 00:11:24,823
>> Dus hier is onze gelinkte lijst.

241
00:11:24,823 --> 00:11:26,620
Het bevat tegelijk vier elementen.

242
00:11:26,620 --> 00:11:30,420
En meer perfect hier onze
stack met vier elementen.

243
00:11:30,420 --> 00:11:36,030
En laten we zeggen dat we nu willen
duwen een nieuw item op deze stapel.

244
00:11:36,030 --> 00:11:39,792
En we willen een nieuwe push
voorwerp waarvan de gegevens waarde is 12.

245
00:11:39,792 --> 00:11:41,000
Nou, wat gaan we doen?

246
00:11:41,000 --> 00:11:43,420
Wel eerst gaan we
malloc ruimte, dynamisch

247
00:11:43,420 --> 00:11:45,411
toewijzen ruimte voor een nieuw knooppunt.

248
00:11:45,411 --> 00:11:48,160
En natuurlijk onmiddellijk na
maken we een oproep om altijd malloc we

249
00:11:48,160 --> 00:11:52,989
zorg ervoor om te controleren op null,
want als we nul terug

250
00:11:52,989 --> 00:11:54,280
er was een soort van probleem.

251
00:11:54,280 --> 00:11:57,570
We willen niet dereferentie dat null
aanwijzer of u een seg fout lijden.

252
00:11:57,570 --> 00:11:58,510
Dat is niet goed.

253
00:11:58,510 --> 00:11:59,760
Dus we hebben malloced van het knooppunt.

254
00:11:59,760 --> 00:12:01,260
We gaan ervan uit dat we succes hadden hier.

255
00:12:01,260 --> 00:12:06,090
We gaan om te zetten in 12
het dataveld van dat knooppunt.

256
00:12:06,090 --> 00:12:11,570
Nu heb je te herinneren welke van onze pointers
verhuist komende zodat we niet breken de keten?

257
00:12:11,570 --> 00:12:15,100
We hebben een paar opties hier, maar
de enige die gaat om veilig te zijn

258
00:12:15,100 --> 00:12:19,330
is het nieuws volgende pointer op te zetten
punt om de oude hoofd van de lijst

259
00:12:19,330 --> 00:12:21,360
of wat zal binnenkort de
oude kop van de lijst.

260
00:12:21,360 --> 00:12:23,610
En nu dat al onze
elementen worden aan elkaar geketend,

261
00:12:23,610 --> 00:12:27,370
kunnen we gewoon verhuizen lijst te wijzen
op dezelfde plaats die nieuwe doet.

262
00:12:27,370 --> 00:12:33,550
En we hebben nu effectief geduwd een
nieuw element op de voorkant van de stapel.

263
00:12:33,550 --> 00:12:36,420
>> Pop we willen gewoon
verwijderen die eerste element.

264
00:12:36,420 --> 00:12:38,150
En dus eigenlijk wat
we hebben hier te doen,

265
00:12:38,150 --> 00:12:40,050
goed we moeten het tweede element te vinden.

266
00:12:40,050 --> 00:12:43,540
Uiteindelijk dat zal de nieuwe worden
hoofd nadat we de eerste te verwijderen.

267
00:12:43,540 --> 00:12:47,300
Dus we hoeven alleen maar uit te gaan van
het begin, ga één vooruit.

268
00:12:47,300 --> 00:12:50,340
Zodra we hebben een greep op één
voorwaarts waar we op dit moment

269
00:12:50,340 --> 00:12:53,850
zijn we de eerste veilig verwijderen
en dan kunnen we gewoon bewegen het hoofd

270
00:12:53,850 --> 00:12:57,150
te wijzen op wat de
tweede termijn en nu dan

271
00:12:57,150 --> 00:12:59,170
is de eerste daarna
knooppunt is verwijderd.

272
00:12:59,170 --> 00:13:01,160
>> Dus nogmaals, het nemen van een blik
het als een diagram wij

273
00:13:01,160 --> 00:13:05,022
wil nu een pop
onderdeel uit van deze stapel.

274
00:13:05,022 --> 00:13:05,730
Dus wat doen we?

275
00:13:05,730 --> 00:13:08,188
Nou we eerst gaat maken
een nieuw pointer dat gaat

276
00:13:08,188 --> 00:13:10,940
te wijzen op dezelfde plek als het hoofd.

277
00:13:10,940 --> 00:13:13,790
We gaan het één positie te verplaatsen
voorwaarts door te zeggen trav gelijken

278
00:13:13,790 --> 00:13:17,510
trav volgende bijvoorbeeld, die
zou het trav wijzer één vooruit

279
00:13:17,510 --> 00:13:19,324
positie naar voren.

280
00:13:19,324 --> 00:13:21,240
Nu dat we hebben een
Houd op het eerste element

281
00:13:21,240 --> 00:13:24,573
door de wijzer genaamd lijst en de
tweede element door middel van een pointer genaamd

282
00:13:24,573 --> 00:13:28,692
trav, kunnen we veilig verwijderen dat
eerste element van de stapel

283
00:13:28,692 --> 00:13:30,650
zonder dat de overige
van de keten omdat we

284
00:13:30,650 --> 00:13:32,358
een manier verwijzen
met het tweede element

285
00:13:32,358 --> 00:13:34,780
doorsturen door middel van de
pointer genaamd trav.

286
00:13:34,780 --> 00:13:37,100
>> Dus nu kunnen we bevrijden dat knooppunt.

287
00:13:37,100 --> 00:13:38,404
We kunnen bevrijden lijst.

288
00:13:38,404 --> 00:13:41,320
En dan alles wat we nu moeten doen is
lijst te verplaatsen naar naar dezelfde plaats

289
00:13:41,320 --> 00:13:44,482
trav dat doet, en we zijn een soort van back
waar we begonnen voordat we geduwd 12

290
00:13:44,482 --> 00:13:45,690
op in de eerste plaats, rechts.

291
00:13:45,690 --> 00:13:46,940
Dit is precies waar we waren.

292
00:13:46,940 --> 00:13:48,840
We hadden deze vier elementen stack.

293
00:13:48,840 --> 00:13:49,690
We voegden een vijfde.

294
00:13:49,690 --> 00:13:51,910
We geduwd een vijfde
element op, en dan hebben we

295
00:13:51,910 --> 00:13:55,980
geknald die het meest recent
back off toegevoegd element.

296
00:13:55,980 --> 00:13:58,816
>> Dat is echt vrij veel
alles wat er te stacks.

297
00:13:58,816 --> 00:14:00,190
U kunt ze uit te voeren als arrays.

298
00:14:00,190 --> 00:14:01,815
U kunt ze uit te voeren zoals gelinkte lijsten.

299
00:14:01,815 --> 00:14:04,810
Er zijn natuurlijk andere
manieren om ze uit te voeren ook.

300
00:14:04,810 --> 00:14:09,060
Eigenlijk de reden dat we zouden gebruiken
stacks is gegevens zodanig te handhaven

301
00:14:09,060 --> 00:14:12,090
dat de meest recent toegevoegde
element is het eerste wat we

302
00:14:12,090 --> 00:14:14,980
gaat te willen terug te krijgen.

303
00:14:14,980 --> 00:14:17,900
Ik ben Doug Lloyd, dit is CS50.

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