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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Alle reg,
so by hierdie punt is jy

3
00:00:05,990 --> 00:00:09,020
waarskynlik redelik vertroud
met skikkings en geskakelde lyste

4
00:00:09,020 --> 00:00:10,950
wat is die twee primêre
data strukture wat ons het

5
00:00:10,950 --> 00:00:16,810
gepraat oor vir die behoud van stelle
data van soortgelyke tipes data georganiseer.

6
00:00:16,810 --> 00:00:19,080
>> Nou gaan ons praat
oor 'n paar variasies

7
00:00:19,080 --> 00:00:20,330
op skikkings en geskakelde lyste.

8
00:00:20,330 --> 00:00:22,362
In hierdie video wat ons gaan
om te praat oor stapels.

9
00:00:22,362 --> 00:00:25,320
Spesifiek ons ​​gaan praat
ongeveer 'n data struktuur genaamd 'n stapel.

10
00:00:25,320 --> 00:00:28,510
Onthou van die vorige besprekings
oor wysers en geheue,

11
00:00:28,510 --> 00:00:32,060
dat die stapel is ook die
naam vir 'n segment van die geheue

12
00:00:32,060 --> 00:00:34,980
waar staties verklaar
memory-- geheue dat jy

13
00:00:34,980 --> 00:00:38,730
noem, veranderlikes wat jy noem, et
ens en funksie rame wat ons ook

14
00:00:38,730 --> 00:00:41,000
oproep stapel rame bestaan ​​nie.

15
00:00:41,000 --> 00:00:45,421
So, dit is 'n stapel data struktuur
nie 'n stapel segment van die geheue.

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

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

18
00:00:46,890 --> 00:00:49,220
So dit is pretty much net 'n
spesiale soort struktuur

19
00:00:49,220 --> 00:00:51,190
dat die data handhaaf in 'n georganiseerde manier.

20
00:00:51,190 --> 00:00:53,760
En daar is twee baie
algemene maniere om te implementeer

21
00:00:53,760 --> 00:00:57,380
stapels met behulp van twee data strukture
dat ons reeds vertroud is met,

22
00:00:57,380 --> 00:01:00,340
skikkings en geskakelde lyste.

23
00:01:00,340 --> 00:01:04,430
Wat maak 'n stapel spesiaal maak, is die
manier waarop ons sit inligting

24
00:01:04,430 --> 00:01:08,200
in die stapel, en die manier waarop ons
verwyder inligting van die stapel.

25
00:01:08,200 --> 00:01:11,600
In die besonder met stapels
die reël is net die mees

26
00:01:11,600 --> 00:01:15,830
onlangs bygevoeg element kan verwyder word.

27
00:01:15,830 --> 00:01:17,660
>> So dink oor dit asof dit 'n stapel.

28
00:01:17,660 --> 00:01:21,170
Ons hei inligting
op die top van die self,

29
00:01:21,170 --> 00:01:24,271
en net die ding op die top
van die paal verwyder kan word.

30
00:01:24,271 --> 00:01:27,020
Ons kan nie die ding onder
want anders sou alles

31
00:01:27,020 --> 00:01:28,020
ineenstorting en val oor.

32
00:01:28,020 --> 00:01:32,580
So ons werklik die bou van 'n stapel dat
ons dan 'n stuk te verwyder stuk.

33
00:01:32,580 --> 00:01:36,590
As gevolg van hierdie ons gewoonlik verwys
om 'n stapel as 'n LIFO struktuur,

34
00:01:36,590 --> 00:01:38,940
laaste in, eerste uit.

35
00:01:38,940 --> 00:01:42,290
LIFO, laaste in, eerste uit.

36
00:01:42,290 --> 00:01:45,635
>> So as gevolg van hierdie beperking op
hoe inligting kan bygevoeg word om

37
00:01:45,635 --> 00:01:49,080
en verwyder van 'n stapel, daar is regtig
net twee dinge wat ons kan doen met 'n stapel.

38
00:01:49,080 --> 00:01:52,010
Ons kan stoot, wat is die
term wat ons gebruik vir die toevoeging

39
00:01:52,010 --> 00:01:55,130
'n nuwe element na die top van die
stapel, of as die stapel bestaan ​​nie

40
00:01:55,130 --> 00:01:58,550
en ons is dit skep van nuuts af,
die skep van die stapel in die eerste plek

41
00:01:58,550 --> 00:02:00,110
sou wees stoot.

42
00:02:00,110 --> 00:02:04,990
En pop dan, dis die soort van CS
term wat ons gebruik om die mees onlangs verwyder

43
00:02:04,990 --> 00:02:08,330
bygevoeg element van die top van die stapel.

44
00:02:08,330 --> 00:02:11,130
>> So ons gaan by albei kyk
implementering, sowel verskeidenheid gebaseer

45
00:02:11,130 --> 00:02:13,120
en gekoppel lys gebasseer.

46
00:02:13,120 --> 00:02:14,870
En ons gaan
begin met array gebaseer is.

47
00:02:14,870 --> 00:02:19,990
So hier is die basiese idee van wat
die skikking gebaseer stapel data struktuur

48
00:02:19,990 --> 00:02:21,140
sou lyk.

49
00:02:21,140 --> 00:02:23,740
Ons het 'n getikte definisie hier.

50
00:02:23,740 --> 00:02:27,790
Binnekant van dat ons twee lede
of velde van die struktuur.

51
00:02:27,790 --> 00:02:29,880
Ons het 'n skikking.

52
00:02:29,880 --> 00:02:32,400
En weer die gebruik van die ek
arbitrêre data tipe waarde.

53
00:02:32,400 --> 00:02:35,180
>> So dit enige tipe data kan wees,
int char of 'n ander data

54
00:02:35,180 --> 00:02:37,080
tik jy voorheen geskep.

55
00:02:37,080 --> 00:02:39,861
So ons het 'n verskeidenheid van grootte kapasiteit.

56
00:02:39,861 --> 00:02:44,010
Kapasiteit om 'n pond gedefinieer konstante,
dalk iewers anders in ons lêer.

57
00:02:44,010 --> 00:02:47,550
So sien reeds met hierdie
implementering ons jaag

58
00:02:47,550 --> 00:02:49,800
onsself as tipies was
die geval met die skikkings,

59
00:02:49,800 --> 00:02:53,170
wat ons nie kan dinamies verander,
waar daar 'n sekere aantal

60
00:02:53,170 --> 00:02:55,450
maksimum elemente wat
ons kan in ons stapel.

61
00:02:55,450 --> 00:02:57,930
In hierdie geval is dit kapasiteit elemente.

62
00:02:57,930 --> 00:03:00,310
>> Ons hou ook rekord van
die top van die stapel.

63
00:03:00,310 --> 00:03:04,350
Wat is die mees element
onlangs by die stapel?

64
00:03:04,350 --> 00:03:07,470
En so hou ons op hoogte van wat
in 'n top veranderlike genoem.

65
00:03:07,470 --> 00:03:11,692
En dit alles kry saam toegedraai
in 'n nuwe soort data genoem 'n stapel.

66
00:03:11,692 --> 00:03:13,400
En sodra ons geskep
hierdie nuwe tipe data

67
00:03:13,400 --> 00:03:15,410
ons kan dit behandel soos
enige ander tipe data.

68
00:03:15,410 --> 00:03:20,970
Ons kan verklaar stapel s, net soos
ons kon int x, of char y te doen.

69
00:03:20,970 --> 00:03:22,990
En wanneer ons sê stapel
s, goed wat gebeur

70
00:03:22,990 --> 00:03:26,420
is ons kry 'n stel van
geheue opsy gesit vir ons.

71
00:03:26,420 --> 00:03:28,770
>> In hierdie geval kapasiteit
Ek het blykbaar besluit

72
00:03:28,770 --> 00:03:33,470
10 want ek het
enkele veranderlike van tipe stapel

73
00:03:33,470 --> 00:03:35,320
wat bestaan ​​uit twee velde te onthou.

74
00:03:35,320 --> 00:03:38,330
'N skikking, in hierdie geval gaan
om 'n verskeidenheid van heelgetalle wees

75
00:03:38,330 --> 00:03:40,440
soos die geval is in die meeste van my voorbeelde.

76
00:03:40,440 --> 00:03:43,996
En 'n ander heelgetalveranderlike
kan stoor die top,

77
00:03:43,996 --> 00:03:45,870
die mees onlangs bygevoeg
element van die stapel.

78
00:03:45,870 --> 00:03:50,290
So 'n enkele stapel van wat ons
net gedefinieer lyk.

79
00:03:50,290 --> 00:03:53,190
Dit is 'n boks met
'n verskeidenheid van 10 wat

80
00:03:53,190 --> 00:03:57,280
sal wees heelgetalle in hierdie geval en
'n ander heelgetalveranderlike daar in die groen

81
00:03:57,280 --> 00:04:00,010
na die top van die stapel te dui.

82
00:04:00,010 --> 00:04:02,600
>> Na die top van die stel
stapel ons net s.top sê.

83
00:04:02,600 --> 00:04:04,890
Dit is hoe ons toegang tot 'n
gebied van 'n struktuur herroep.

84
00:04:04,890 --> 00:04:10,460
s.top gelyk 0 effektief
doen dit om ons stapel.

85
00:04:10,460 --> 00:04:12,960
So weer het ons twee operasies
dat ons nou kan doen.

86
00:04:12,960 --> 00:04:14,270
Ons kan stoot en ons kan pop.

87
00:04:14,270 --> 00:04:15,635
Kom ons begin met die druk.

88
00:04:15,635 --> 00:04:18,260
Weer, stoot is die toevoeging van 'n nuwe
element na die top van die stapel.

89
00:04:18,260 --> 00:04:21,460
>> So, wat moet ons doen om te doen in
hierdie verskeidenheid gebaseer implementering?

90
00:04:21,460 --> 00:04:23,210
Wel, in die algemeen is die
druk funksie gaan

91
00:04:23,210 --> 00:04:26,160
nodig om 'n te aanvaar
wyser na die stapel.

92
00:04:26,160 --> 00:04:28,610
Neem nou 'n tweede en daaroor dink.

93
00:04:28,610 --> 00:04:32,840
Hoekom sal ons wil aanvaar
'n verwysing na die stapel?

94
00:04:32,840 --> 00:04:36,830
Onthou van die vorige video's op
veranderlike omvang en wysers,

95
00:04:36,830 --> 00:04:42,350
wat sou gebeur as ons net gestuur
stapel, is eerder as 'n parameter?

96
00:04:42,350 --> 00:04:45,770
Wat sou eintlik geslaag word daar?

97
00:04:45,770 --> 00:04:49,430
Onthou ons is die skep van 'n afskrif
wanneer ons dit slaag om 'n funksie

98
00:04:49,430 --> 00:04:51,160
tensy ons gebruik wenke.

99
00:04:51,160 --> 00:04:55,380
En so hierdie funksie te stoot behoeftes
om 'n wyser na die stapel te aanvaar

100
00:04:55,380 --> 00:04:59,160
sodat ons eintlik verander
die stapel ons beoog om te verander.

101
00:04:59,160 --> 00:05:03,060
>> Die ander ding druk waarskynlik wil
aanvaar is 'n data element van die tipe waarde.

102
00:05:03,060 --> 00:05:06,970
In hierdie geval, weer, 'n heelgetal wat
ons gaan om te voeg by die top van stapel.

103
00:05:06,970 --> 00:05:08,680
So ons het ons twee parameters.

104
00:05:08,680 --> 00:05:11,310
Wat gaan ons
nou binnekant van druk?

105
00:05:11,310 --> 00:05:14,860
Wel, eenvoudig, ons gaan net om by te voeg
daardie element na die top van die stapel

106
00:05:14,860 --> 00:05:22,860
en dan verander waar die top van
die stapel is, dat is dot top waarde.

107
00:05:22,860 --> 00:05:25,639
So dit is wat 'n funksie
verklaring vir druk

108
00:05:25,639 --> 00:05:27,680
kan lyk in 'n
skikking gebaseer implementering.

109
00:05:27,680 --> 00:05:30,967
>> Weereens is dit nie 'n vaste reël
dat jy dit kan verander en

110
00:05:30,967 --> 00:05:32,050
dit wissel in verskillende maniere.

111
00:05:32,050 --> 00:05:33,840
Miskien s is globaal verklaar.

112
00:05:33,840 --> 00:05:36,180
En so het jy nie eens nodig
om te slaag is dit as 'n parameter.

113
00:05:36,180 --> 00:05:39,125
Dit is weer net 'n
algemene geval vir stoot.

114
00:05:39,125 --> 00:05:41,000
En daar is verskillende
maniere om dit te implementeer.

115
00:05:41,000 --> 00:05:42,810
Maar in hierdie geval ons
druk gaan neem

116
00:05:42,810 --> 00:05:48,540
twee argumente, 'n verwysing na 'n stapel en
'n data element van die tipe waarde heelgetal

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

118
00:05:49,840 --> 00:05:52,100
>> Sodat ons verklaar s, ons
gesê s.top gelyk 0.

119
00:05:52,100 --> 00:05:55,969
Nou laat druk die
getal 28 op die stapel.

120
00:05:55,969 --> 00:05:57,010
Wel, wat beteken dit?

121
00:05:57,010 --> 00:05:59,600
Wel tans die
top van die stapel is 0.

122
00:05:59,600 --> 00:06:01,350
En so wat is basies
gaan gebeur is

123
00:06:01,350 --> 00:06:05,820
ons gaan die aantal vashou
28 in verskeidenheid ligging 0.

124
00:06:05,820 --> 00:06:09,540
Redelik eenvoudig, reg, wat
was die top en nou is ons goed om te gaan.

125
00:06:09,540 --> 00:06:12,910
En dan moet ons wat verander
die top van die stapel sal wees.

126
00:06:12,910 --> 00:06:15,130
Sodat die volgende keer
Ons stoot 'n element in,

127
00:06:15,130 --> 00:06:18,017
ons gaan om dit te stoor in
array plek, waarskynlik nie 0.

128
00:06:18,017 --> 00:06:20,100
Ons wil nie oorskryf
wat ons daar sit net.

129
00:06:20,100 --> 00:06:23,510
En so sal ons net beweeg die top 1.

130
00:06:23,510 --> 00:06:24,890
Dit maak waarskynlik sin.

131
00:06:24,890 --> 00:06:28,940
>> Nou as ons wil 'n ander element sit
op die stapel, sê ons wil stoot 33,

132
00:06:28,940 --> 00:06:33,190
nou goed ons net gaan neem 33
en sit dit op array plek getal

133
00:06:33,190 --> 00:06:37,580
1, en dan verander die top van ons
stapel te array plek nommer twee wees.

134
00:06:37,580 --> 00:06:40,650
So as die volgende keer wat ons wil
stoot 'n element op die stapel,

135
00:06:40,650 --> 00:06:43,087
dit sal opgestel ligging 2 word.

136
00:06:43,087 --> 00:06:44,420
En laat ons doen wat 'n mens meer tyd.

137
00:06:44,420 --> 00:06:45,753
Ons sal stoot 19 af van die stapels.

138
00:06:45,753 --> 00:06:48,940
Ons sal 19 opgestel ligging 2 sit
en verander die top van ons stapel

139
00:06:48,940 --> 00:06:51,220
om array plek 3 wees
so as die volgende keer wat ons

140
00:06:51,220 --> 00:06:54,780
nodig om 'n druk ons ​​goed om te gaan maak.

141
00:06:54,780 --> 00:06:56,980
>> OK, so dit is stoot in 'n neutedop.

142
00:06:56,980 --> 00:06:57,830
Wat van die knal?

143
00:06:57,830 --> 00:07:00,240
So knal is die soort van
eweknie stoot.

144
00:07:00,240 --> 00:07:02,720
Dit is hoe ons die data van die stapel te verwyder.

145
00:07:02,720 --> 00:07:04,610
En in die algemeen pop behoeftes
om die volgende te doen.

146
00:07:04,610 --> 00:07:07,600
Dit moet 'n verwysing na die aanvaar
stapel weer in die algemene geval.

147
00:07:07,600 --> 00:07:10,480
In 'n ander geval jy dalk
het die stapel globaal verklaar,

148
00:07:10,480 --> 00:07:13,910
in welke geval jy nie nodig het om dit te slaag
in, want dit het reeds toegang tot dit

149
00:07:13,910 --> 00:07:15,541
as 'n globale veranderlike.

150
00:07:15,541 --> 00:07:17,040
Maar wat anders om te doen wat ons moet doen?

151
00:07:17,040 --> 00:07:21,000
Wel, ons is die verhoog
die top van die stapel in stoot,

152
00:07:21,000 --> 00:07:24,050
so ons is waarskynlik gaan om te wil
na die top van die stapel decrement

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

154
00:07:25,009 --> 00:07:26,800
En dan natuurlik
Ons gaan ook om te wil

155
00:07:26,800 --> 00:07:29,240
om die waarde wat ons verwyder terugkeer.

156
00:07:29,240 --> 00:07:32,125
As ons die toevoeging van elemente, ons wil
elemente uit later te kry,

157
00:07:32,125 --> 00:07:34,000
ons waarskynlik eintlik
hulle wil, sodat ons stoor

158
00:07:34,000 --> 00:07:36,490
nie net hulle verwyder uit die
stapel en dan niks doen nie met hulle.

159
00:07:36,490 --> 00:07:38,500
Algemeen as ons
stoot en hier knal

160
00:07:38,500 --> 00:07:41,250
Ons wil hierdie berg
inligting in 'n sinvolle manier

161
00:07:41,250 --> 00:07:43,250
en so is dit nie maak
sin om net weggooi nie.

162
00:07:43,250 --> 00:07:46,380
So Hierdie funksie moet
waarskynlik 'n waarde terug te keer na ons.

163
00:07:46,380 --> 00:07:51,040
>> So dit is wat 'n verklaring vir die pop
kan lyk asof daar by die top links.

164
00:07:51,040 --> 00:07:53,870
Hierdie funksie opbrengste
data van die tipe waarde.

165
00:07:53,870 --> 00:07:56,320
Weereens het ons met behulp van al
heelgetalle regdeur.

166
00:07:56,320 --> 00:08:01,916
En dit 'n verwysing na 'n stapel soos aanvaar
sy uitsluitlike argument of enigste parameter.

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

168
00:08:03,040 --> 00:08:07,990
Kom ons sê ons wil nou
pop 'n element af van s.

169
00:08:07,990 --> 00:08:14,000
So onthou ek het gesê dat stapels is verlede
in, eerste uit, LIEU data strukture.

170
00:08:14,000 --> 00:08:17,855
Watter element gaan
uit die stapel verwyder?

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

172
00:08:21,780 --> 00:08:24,150
Het jy dink 19?

173
00:08:24,150 --> 00:08:25,290
Omdat jy reg sou wees.

174
00:08:25,290 --> 00:08:28,836
19 was die laaste element wat ons by die
stapel toe ons stoot elemente,

175
00:08:28,836 --> 00:08:31,210
en so gaan dit die eerste
element wat kry verwyder.

176
00:08:31,210 --> 00:08:34,780
Dit is asof ons sê 28, en
dan sit ons 33 op die top van dit,

177
00:08:34,780 --> 00:08:36,659
en ons het 19 op die top van dit.

178
00:08:36,659 --> 00:08:40,650
Die enigste element kan ons af te neem is 19.

179
00:08:40,650 --> 00:08:45,019
>> Nou in die diagram hier wat ek gedoen het
is 'n soort van geskrap 19 van die skikking.

180
00:08:45,019 --> 00:08:46,810
Dit is nie eintlik
wat ons gaan doen.

181
00:08:46,810 --> 00:08:48,934
Ons is net gaan om te soort
van voorgee dit is nie daar nie.

182
00:08:48,934 --> 00:08:51,441
Dit is nog steeds daar in
dat die geheue plek,

183
00:08:51,441 --> 00:08:54,190
maar ons gaan net om dit te ignoreer
deur die verandering van die top van ons stapel

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

185
00:08:56,080 --> 00:08:58,720
So as ons nou stoot
'n ander element op die stapel,

186
00:08:58,720 --> 00:09:00,720
dit sou oor skryf 19.

187
00:09:00,720 --> 00:09:03,990
>> Maar laat ons nie te gaan deur die moeite
van die verwydering van 19 uit die stapel.

188
00:09:03,990 --> 00:09:05,830
Ons kan net voorgee dit is nie daar nie.

189
00:09:05,830 --> 00:09:11,107
Vir die doeleindes van die stapel dit is weg as
ons verander die top te wees in plaas van 2 3.

190
00:09:11,107 --> 00:09:12,690
Alle reg, so dit was pretty much dit.

191
00:09:12,690 --> 00:09:15,080
Dit is al wat ons nodig het om te doen
om 'n element pop af.

192
00:09:15,080 --> 00:09:16,090
Kom ons doen dit weer.

193
00:09:16,090 --> 00:09:18,610
So ek het dit in rooi uitgelig hier om
dui ons nog 'n oproep maak.

194
00:09:18,610 --> 00:09:19,720
Ons gaan na dieselfde ding te doen.

195
00:09:19,720 --> 00:09:20,803
>> So, wat gaan gebeur?

196
00:09:20,803 --> 00:09:23,670
Wel, ons gaan om te slaan
33 in x en ons gaan

197
00:09:23,670 --> 00:09:26,217
na die top van die stapel te verander na 1.

198
00:09:26,217 --> 00:09:29,050
Sodat as ons nou 'n stoot
element in die stapel wat ons

199
00:09:29,050 --> 00:09:31,610
gaan nou te doen,
wat gaan gebeur

200
00:09:31,610 --> 00:09:36,367
is ons gaan oorskryf
verskeidenheid ligging nommer 1.

201
00:09:36,367 --> 00:09:38,950
Sodat 33 dat die soort van gelaat
agter dat ons net voorgegee

202
00:09:38,950 --> 00:09:44,390
nie daar is nie, is ons net gaan
om dit afranselen en sit 40 daar plaas.

203
00:09:44,390 --> 00:09:46,290
En dan natuurlik,
aangesien ons het 'n stoot,

204
00:09:46,290 --> 00:09:48,780
ons gaan die inkrementeer
top van die stapel 1-2

205
00:09:48,780 --> 00:09:50,950
sodat as ons nou voeg
'n ander element Dit sal

206
00:09:50,950 --> 00:09:54,700
gaan in verskeidenheid ligging nommer twee.

207
00:09:54,700 --> 00:09:57,590
>> Nou gekoppel lyste is 'n ander
manier om stapels implementeer.

208
00:09:57,590 --> 00:10:01,210
En as hierdie definisie op die
skerm hier lyk bekend vir julle,

209
00:10:01,210 --> 00:10:04,260
dit is omdat dit lyk amper
presies dieselfde, in werklikheid,

210
00:10:04,260 --> 00:10:07,790
dit pretty much presies
dieselfde as 'n enkel gekoppel lys

211
00:10:07,790 --> 00:10:11,990
As jy onthou van ons bespreking van
enkel geskakelde lyste in 'n ander video.

212
00:10:11,990 --> 00:10:15,510
Die enigste beperking hier
is vir ons as programmeerders,

213
00:10:15,510 --> 00:10:17,900
ons is nie toegelaat om
voeg of te verwyder lukraak

214
00:10:17,900 --> 00:10:20,620
uit die enkel geskakelde lys
wat ons voorheen kon doen nie.

215
00:10:20,620 --> 00:10:25,820
Ons kan nou eers in te voeg en te verwyder van
die voorkant of die top van die gekoppelde

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

217
00:10:26,320 --> 00:10:28,028
Dit is regtig die enigste
verskil egter.

218
00:10:28,028 --> 00:10:29,700
Dit is andersins 'n enkel geskakelde lys.

219
00:10:29,700 --> 00:10:32,060
Dit is net die beperking
vervang op onsself

220
00:10:32,060 --> 00:10:35,770
as programmeerders wat
verander dit in 'n stapel.

221
00:10:35,770 --> 00:10:39,280
>> Die reël hier is om altyd handhaaf 'n
wyser na die hoof van 'n geskakelde lys.

222
00:10:39,280 --> 00:10:41,520
Dit is natuurlik 'n algemeen
belangrike reël eerste.

223
00:10:41,520 --> 00:10:44,260
Vir enkel geskakelde lys in elk geval wat jy
net 'n wyser na die hoof

224
00:10:44,260 --> 00:10:46,160
om daardie
ketting in staat wees om te verwys

225
00:10:46,160 --> 00:10:48,596
elke ander element
in die geskakelde lys.

226
00:10:48,596 --> 00:10:50,470
Maar dit is veral
belangrik om met 'n stapel.

227
00:10:50,470 --> 00:10:52,386
En so algemeen is jy
gaan eintlik wil

228
00:10:52,386 --> 00:10:54,090
hierdie wyser na 'n globale veranderlike.

229
00:10:54,090 --> 00:10:56,574
Dit is waarskynlik gaan om
selfs makliker manier.

230
00:10:56,574 --> 00:10:58,240
So, wat is die analoë van druk en pop?

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

232
00:10:58,740 --> 00:11:01,812
So weer stoot is die toevoeging
'n nuwe element tot die stapel.

233
00:11:01,812 --> 00:11:03,770
In 'n geskakelde lys wat
beteken dat ons gaan hê

234
00:11:03,770 --> 00:11:07,770
om 'n nuwe node dat ons skep
gaan voeg in die geskakelde lys,

235
00:11:07,770 --> 00:11:10,500
en dan volg die stappe versigtig
dat ons voorheen uiteengesit

236
00:11:10,500 --> 00:11:16,050
in enkel geskakelde lyste te voeg tot
die ketting sonder om te breek die ketting

237
00:11:16,050 --> 00:11:18,900
en verloor of enige orphaning
elemente van die geskakelde lys.

238
00:11:18,900 --> 00:11:21,820
En dit is basies wat dit
bietjie blob van die teks is daar 'n opsomming.

239
00:11:21,820 --> 00:11:23,740
En laat ons 'n blik
dit as 'n diagram.

240
00:11:23,740 --> 00:11:24,823
>> So hier is ons geskakelde lys.

241
00:11:24,823 --> 00:11:26,620
Dit bevat gelyktydig vier elemente.

242
00:11:26,620 --> 00:11:30,420
En meer perfek hier is ons
stapel met vier elemente.

243
00:11:30,420 --> 00:11:36,030
En laat ons sê ons wil nou
druk 'n nuwe item op die stapel.

244
00:11:36,030 --> 00:11:39,792
En ons wil 'n nuwe druk
item wie data waarde is 12.

245
00:11:39,792 --> 00:11:41,000
Wel, wat gaan ons doen?

246
00:11:41,000 --> 00:11:43,420
Wel in die eerste gaan ons
malloc ruimte, dinamiese

247
00:11:43,420 --> 00:11:45,411
toeken ruimte vir 'n nuwe knoop.

248
00:11:45,411 --> 00:11:48,160
En natuurlik onmiddellik na
Ons maak 'n oproep om altyd malloc ons

249
00:11:48,160 --> 00:11:52,989
maak seker dat jy check for null,
want as ons het null terug

250
00:11:52,989 --> 00:11:54,280
daar was 'n soort van probleem.

251
00:11:54,280 --> 00:11:57,570
Ons wil nie dereference dat null
wyser, of jy sal 'n seg skuld ly.

252
00:11:57,570 --> 00:11:58,510
Dit is nie goed nie.

253
00:11:58,510 --> 00:11:59,760
Dus het ons malloced van die knoop.

254
00:11:59,760 --> 00:12:01,260
Ons sal ons aanvaar het sukses hier gehad het.

255
00:12:01,260 --> 00:12:06,090
Ons gaan sit in 12
die veld data van daardie knoop.

256
00:12:06,090 --> 00:12:11,570
Nou onthou jy wat van ons wenke
beweeg langs sodat ons nie breek die ketting?

257
00:12:11,570 --> 00:12:15,100
Ons het 'n paar van die opsies hier, maar
die enigste een wat gaan om veilig te wees

258
00:12:15,100 --> 00:12:19,330
is om die nuus volgende wyser te stel
punt na die ou hoof van die lys

259
00:12:19,330 --> 00:12:21,360
of wat sal binnekort die
ou hoof van die lys.

260
00:12:21,360 --> 00:12:23,610
En nou dat almal van ons
elemente saam vasgeketting,

261
00:12:23,610 --> 00:12:27,370
kan ons net beweeg lys te wys
na dieselfde plek dat die nuwe werk.

262
00:12:27,370 --> 00:12:33,550
En ons het nou effektief gestoot n
nuwe element op die voorkant van die stapel.

263
00:12:33,550 --> 00:12:36,420
>> Pop ons wil net
verwyder die eerste element.

264
00:12:36,420 --> 00:12:38,150
En so basies wat
ons het hier te doen,

265
00:12:38,150 --> 00:12:40,050
Wel, ons het na die tweede element te vind.

266
00:12:40,050 --> 00:12:43,540
Uiteindelik sal die nuut geword
kop nadat ons die eerste een te verwyder.

267
00:12:43,540 --> 00:12:47,300
So ons moet net om te begin van
die begin, skuif een vorentoe.

268
00:12:47,300 --> 00:12:50,340
Sodra ons het 'n houvas op die een
vorentoe van waar ons tans

269
00:12:50,340 --> 00:12:53,850
is ons die eerste een veilig verwyder
en dan kan ons net beweeg die hoof

270
00:12:53,850 --> 00:12:57,150
om te verwys na wat was die
tweede kwartaal en dan nou

271
00:12:57,150 --> 00:12:59,170
is die eerste daarna
node is verwyder.

272
00:12:59,170 --> 00:13:01,160
>> So weer, neem 'n blik
dit as 'n diagram ons

273
00:13:01,160 --> 00:13:05,022
nou wil pop 'n
element af van hierdie stapel.

274
00:13:05,022 --> 00:13:05,730
So, wat doen ons?

275
00:13:05,730 --> 00:13:08,188
Wel ons eerste gaan skep
'n nuwe wyser wat gaan

276
00:13:08,188 --> 00:13:10,940
om te verwys na dieselfde plek as die hoof.

277
00:13:10,940 --> 00:13:13,790
Ons gaan dit een posisie beweeg
vorentoe deur te sê trav gelykes

278
00:13:13,790 --> 00:13:17,510
Trav volgende byvoorbeeld, wat
sou die trav wyser een bevorder

279
00:13:17,510 --> 00:13:19,324
posisie vorentoe.

280
00:13:19,324 --> 00:13:21,240
Nou dat ons het 'n
hou op die eerste element

281
00:13:21,240 --> 00:13:24,573
deur die wyser genoem lys en die
tweede element deur 'n wyser genoem

282
00:13:24,573 --> 00:13:28,692
trav, kan ons veilig verwyder wat
eerste element van die stapel

283
00:13:28,692 --> 00:13:30,650
sonder dat die res
van die ketting, want ons

284
00:13:30,650 --> 00:13:32,358
het 'n manier om te verwys
na die tweede element

285
00:13:32,358 --> 00:13:34,780
stuur deur middel van die
wyser genoem trav.

286
00:13:34,780 --> 00:13:37,100
>> So nou kan ons daardie knoop.

287
00:13:37,100 --> 00:13:38,404
Ons kan bevry lys.

288
00:13:38,404 --> 00:13:41,320
En dan sal al ons nou moet doen, is om
lys te skuif na punt na dieselfde plek

289
00:13:41,320 --> 00:13:44,482
wat trav doen, en ons is soort van terug
waar ons begin het voordat ons gestoot 12

290
00:13:44,482 --> 00:13:45,690
in die eerste plek, reg.

291
00:13:45,690 --> 00:13:46,940
Dit is presies waar ons was.

292
00:13:46,940 --> 00:13:48,840
Ons het hierdie vier element stapel.

293
00:13:48,840 --> 00:13:49,690
Ons het 'n vyfde plek.

294
00:13:49,690 --> 00:13:51,910
Ons gestoot 'n vyfde
element op, en dan sal ons

295
00:13:51,910 --> 00:13:55,980
inloer wat mees onlangs
back off bygevoeg element.

296
00:13:55,980 --> 00:13:58,816
>> Dit is regtig baie mooi
al wat daar is om stapels.

297
00:13:58,816 --> 00:14:00,190
Jy kan dit te implementeer as skikkings.

298
00:14:00,190 --> 00:14:01,815
Jy kan dit te implementeer as geskakelde lyste.

299
00:14:01,815 --> 00:14:04,810
Daar is natuurlik ander
maniere om dit te implementeer as well.

300
00:14:04,810 --> 00:14:09,060
Basies die rede waarom ons sou gebruik
stapels is om data in so 'n manier te handhaaf

301
00:14:09,060 --> 00:14:12,090
dat die mees onlangs bygevoeg
element is die eerste ding wat ons

302
00:14:12,090 --> 00:14:14,980
gaan wil terug te kry.

303
00:14:14,980 --> 00:14:17,900
Ek is Doug Lloyd, dit is cs50.

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