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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Bone,
tiel per tiu punkto vi estas

3
00:00:05,990 --> 00:00:09,020
verŝajne bela familiara
kun tabeloj kaj ligitaj listoj

4
00:00:09,020 --> 00:00:10,950
kiu estas la du primaraj
datumstrukturoj ni havas

5
00:00:10,950 --> 00:00:16,810
parolis por konservanta aroj de
datumoj de simila datumtipoj organizita.

6
00:00:16,810 --> 00:00:19,080
>> Nun ni iras por paroli
pri kelkaj variadoj

7
00:00:19,080 --> 00:00:20,330
sur tabeloj kaj ligitaj listoj.

8
00:00:20,330 --> 00:00:22,362
En ĉi tiu video ni iras
paroli pri stakoj.

9
00:00:22,362 --> 00:00:25,320
Specife ni tuj paroli
pri datumstrukturo nomata stako.

10
00:00:25,320 --> 00:00:28,510
Revokon de antaŭaj diskutoj
pri punteros kaj memoro,

11
00:00:28,510 --> 00:00:32,060
ke la pilo estas ankaŭ la
nomo por segmento de memoro

12
00:00:32,060 --> 00:00:34,980
kie statike deklaris
memory-- memoro kiun vi

13
00:00:34,980 --> 00:00:38,730
citi, variabloj kiujn vi nomas, et
cetera kaj funkcio kadroj kiujn ni ankaux

14
00:00:38,730 --> 00:00:41,000
alvoko pilo kadroj ekzistas.

15
00:00:41,000 --> 00:00:45,421
Do tiu estas pilo datumstrukturo
Ne stako segmento de memoro.

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

17
00:00:45,920 --> 00:00:46,890
>> Sed kio estas stako?

18
00:00:46,890 --> 00:00:49,220
Do estas preskaux nur
Speciala speco de strukturo

19
00:00:49,220 --> 00:00:51,190
kiu subtenas datumoj en organizita maniero.

20
00:00:51,190 --> 00:00:53,760
Kaj estas du tre
komunaj manieroj efektivigi

21
00:00:53,760 --> 00:00:57,380
stakigas uzante du datumstrukturoj
ke ni estas jam konata kun,

22
00:00:57,380 --> 00:01:00,340
arrays kaj ligitaj listoj.

23
00:01:00,340 --> 00:01:04,430
Kio faras speciala estas la pilo
maniero en kiu ni metas informo

24
00:01:04,430 --> 00:01:08,200
en la pilo, kaj la maniero ni
forigi informojn el la stako.

25
00:01:08,200 --> 00:01:11,600
Aparte kun stakoj
la regulo estas nur la plej

26
00:01:11,600 --> 00:01:15,830
ĵus aldonita elemento povas esti forigitaj.

27
00:01:15,830 --> 00:01:17,660
>> Do pensu pri ĝi kvazaŭ ĝi estas pilo.

28
00:01:17,660 --> 00:01:21,170
Ni amasiĝas informo
aldone mem,

29
00:01:21,170 --> 00:01:24,271
kaj nur la afero ĉe la supro
de la stako povas esti forigitaj.

30
00:01:24,271 --> 00:01:27,020
Ni ne povas forigi la aferon sub
ĉar ĉio alia volus

31
00:01:27,020 --> 00:01:28,020
kolapsi kaj fali super.

32
00:01:28,020 --> 00:01:32,580
Do ni vere konstruas stako ke
ni tiam devas forigi pecon post peco.

33
00:01:32,580 --> 00:01:36,590
Pro tio ni komune raporti
al stako kiel LIFO strukturo,

34
00:01:36,590 --> 00:01:38,940
daŭri en, unua el.

35
00:01:38,940 --> 00:01:42,290
LIFO, daŭri en, unua el.

36
00:01:42,290 --> 00:01:45,635
>> Do pro tiu limigo sur
kiom informo povas esti aldonita

37
00:01:45,635 --> 00:01:49,080
kaj forigis el stako, estas vere
nur du aferoj ni povas fari kun stako.

38
00:01:49,080 --> 00:01:52,010
Ni povas puŝi, kiu estas la
terminon ni uzu por aldonanta

39
00:01:52,010 --> 00:01:55,130
nova elemento al la supro de la
pilo, aŭ se la pilo ne ekzistas

40
00:01:55,130 --> 00:01:58,550
kaj ni kreas ĝin de nulo,
kreante la stako en la unua loko

41
00:01:58,550 --> 00:02:00,110
estus puŝas.

42
00:02:00,110 --> 00:02:04,990
Kaj tiam krevas, jen la speco de CS
terminon ni uzu por forigi la plej laste

43
00:02:04,990 --> 00:02:08,330
aldonis elemento de la supro de la stako.

44
00:02:08,330 --> 00:02:11,130
>> Do ni tuj rigardi ambaŭ
implementaciones, ambaŭ bazitaj tabelo

45
00:02:11,130 --> 00:02:13,120
kaj ligillisto bazita.

46
00:02:13,120 --> 00:02:14,870
Kaj ni tuj
starti kun tabelo bazita.

47
00:02:14,870 --> 00:02:19,990
Do jen la baza ideo de kio
la tabelo bazita stako datumstrukturo

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

49
00:02:21,140 --> 00:02:23,740
Ni havas tajpita difino tie.

50
00:02:23,740 --> 00:02:27,790
Ene de tiu ni havas du membroj
aŭ kampoj de la strukturo.

51
00:02:27,790 --> 00:02:29,880
Ni havas tabelo.

52
00:02:29,880 --> 00:02:32,400
Kaj denove mi uzas la
arbitra datumtipo valoro.

53
00:02:32,400 --> 00:02:35,180
>> Do tiu povus esti ajna datumtipo,
int char aŭ alian datumon

54
00:02:35,180 --> 00:02:37,080
tajpu vi antaŭe kreitaj.

55
00:02:37,080 --> 00:02:39,861
Do ni havas aron de grandeco kapablo.

56
00:02:39,861 --> 00:02:44,010
Kapablo estanta funton difinita konstanto,
eble aliloken en nia dosiero.

57
00:02:44,010 --> 00:02:47,550
Do rimarki jam kun tiu aparta
efektivigo ni saltadi

58
00:02:47,550 --> 00:02:49,800
nin kiel estis tipe
la kazo kun sensilo,

59
00:02:49,800 --> 00:02:53,170
kiun ni ne povas dinamike regrandigi,
kie estas tute certa nombro

60
00:02:53,170 --> 00:02:55,450
de elementoj maksimuma ke
ni povas meti en nia stako.

61
00:02:55,450 --> 00:02:57,930
En tiu kazo ĝi estas kapablo elementoj.

62
00:02:57,930 --> 00:03:00,310
>> Ni ankaŭ sekvigi
la supro de la stako.

63
00:03:00,310 --> 00:03:04,350
Kio elemento estas la plej
ĵus aldonita al la pilo?

64
00:03:04,350 --> 00:03:07,470
Kaj tiel ni sekvigi ke
en variablo nomata pinto.

65
00:03:07,470 --> 00:03:11,692
Kaj ĉio ĉi gets enpakita kune
en novan datumtipo nomata stako.

66
00:03:11,692 --> 00:03:13,400
Kaj unufoje ni kreis
tiu nova datumtipo

67
00:03:13,400 --> 00:03:15,410
ni povas trakti ĝin kiel
ajna alia datumtipo.

68
00:03:15,410 --> 00:03:20,970
Ni povas deklari pilo j, samkiel
ni povus fari int x, aŭ char y.

69
00:03:20,970 --> 00:03:22,990
Kaj kiam ni diras pilo
s, bone kio okazas

70
00:03:22,990 --> 00:03:26,420
Estas ni akiras aron de
memoro flankenmetis por ni.

71
00:03:26,420 --> 00:03:28,770
>> Tiukaze kapablo
Mi ŝajne decidis

72
00:03:28,770 --> 00:03:33,470
Estas 10 ĉar mi havas
sola variablo de tipo pilo

73
00:03:33,470 --> 00:03:35,320
kiu enhavas du kampojn memoras.

74
00:03:35,320 --> 00:03:38,330
Tabelo, tiukaze tuj
estos tabelo de entjeroj

75
00:03:38,330 --> 00:03:40,440
kiel estas la kazo en la plej multaj el miaj ekzemploj.

76
00:03:40,440 --> 00:03:43,996
Kaj alia entjera variablo
kapabla de stoki la supro,

77
00:03:43,996 --> 00:03:45,870
la plej ĵuse aldonita
elemento al la stako.

78
00:03:45,870 --> 00:03:50,290
Do unu ununura stako de kion ni
nur difinita aspektas kiel ĉi.

79
00:03:50,290 --> 00:03:53,190
Estas skatolo enhavanta
tabelo de 10 kion

80
00:03:53,190 --> 00:03:57,280
Estos entjeroj en tiu kazo kaj
alia entjera variablo tie en verda

81
00:03:57,280 --> 00:04:00,010
indiki la supro de la stako.

82
00:04:00,010 --> 00:04:02,600
>> Por agordi la supro de la
pilo ni nur diru s.top.

83
00:04:02,600 --> 00:04:04,890
Tiel estas kiel ni aliras al
kampo de strukturo revokon.

84
00:04:04,890 --> 00:04:10,460
s.top egalas 0 efike
faras tion por nia stako.

85
00:04:10,460 --> 00:04:12,960
Do denove ni havas du operacioj
ke ni povas elfari nun.

86
00:04:12,960 --> 00:04:14,270
Ni povas puŝi kaj ni povas krevi.

87
00:04:14,270 --> 00:04:15,635
Komencu kun puŝo.

88
00:04:15,635 --> 00:04:18,260
Denove, puŝante estas aldonanta novajn
elemento al la supro de la stako.

89
00:04:18,260 --> 00:04:21,460
>> Do kion ni devas fari en
tiu tabelo bazita efektivigo?

90
00:04:21,460 --> 00:04:23,210
Nu ĝenerale la
puŝo funkcio tuj

91
00:04:23,210 --> 00:04:26,160
bezonas akcepti
sagon al la stako.

92
00:04:26,160 --> 00:04:28,610
Nun prenu la duan kaj pensi pri ĝi.

93
00:04:28,610 --> 00:04:32,840
Kial ni volas akcepti
montrilo al la pilo?

94
00:04:32,840 --> 00:04:36,830
Revokon de antaŭaj videos en
ŝanĝiĝema amplekso kaj punteros,

95
00:04:36,830 --> 00:04:42,350
kio okazus se ni ĵus sendis
pilo, s prefere en kiel parametro?

96
00:04:42,350 --> 00:04:45,770
Kio devus reale esti pasis en tie?

97
00:04:45,770 --> 00:04:49,430
Memoru ni kreas kopion
kiam ni pasas ŝin al funkcio

98
00:04:49,430 --> 00:04:51,160
krom se ni uzas punteros.

99
00:04:51,160 --> 00:04:55,380
Kaj do ĉi tiu funkcio puŝi bezonoj
akcepti puntero al la stako

100
00:04:55,380 --> 00:04:59,160
por ke ni vere ŝanĝi
la stako ni intencas ŝanĝi.

101
00:04:59,160 --> 00:05:03,060
>> La alia afero puŝo probable volas
akcepti estas datumo elemento de tipo valoro.

102
00:05:03,060 --> 00:05:06,970
En tiu kazo, denove, entjero ke
Ni tuj aldonos al la supro de stako.

103
00:05:06,970 --> 00:05:08,680
Do ni havas nian du parametrojn.

104
00:05:08,680 --> 00:05:11,310
Kio estas ni iranta
nun fari ene de puŝo?

105
00:05:11,310 --> 00:05:14,860
Nu, simple, ni ĵus tuj aldoni
ke elemento al la supro de la stako

106
00:05:14,860 --> 00:05:22,860
kaj tiam ŝanĝu kie la supro de
la pilo estas, ke s dot supro valoro.

107
00:05:22,860 --> 00:05:25,639
Do jen kion funkcio
deklaro por puŝo

108
00:05:25,639 --> 00:05:27,680
povus rigardi kiel en
tabelo-bazita efektivigo.

109
00:05:27,680 --> 00:05:30,967
>> Denove ĉi tiu ne estas malmola kaj rapida regulo
ke vi povus ŝanĝi tion kaj havas

110
00:05:30,967 --> 00:05:32,050
ĝi varias en malsamaj manieroj.

111
00:05:32,050 --> 00:05:33,840
Eble s estas deklarita tutmonde.

112
00:05:33,840 --> 00:05:36,180
Kaj tial vi eĉ ne bezonas
pasi ĝin kiel parametro.

113
00:05:36,180 --> 00:05:39,125
Jen denove nur
ĝenerala kazo por puŝo.

114
00:05:39,125 --> 00:05:41,000
Kaj ekzistas diverseco
manierojn por apliki ĝin.

115
00:05:41,000 --> 00:05:42,810
Sed tiukaze nia
puŝo tuj prenos

116
00:05:42,810 --> 00:05:48,540
du argumentoj, puntero al stako kaj
datuma elemento de tipo valoro, entjero

117
00:05:48,540 --> 00:05:49,840
en tiu kazo.

118
00:05:49,840 --> 00:05:52,100
>> Do ni deklaris s, ni
diris s.top egalas 0.

119
00:05:52,100 --> 00:05:55,969
Nun ni puŝi la
numero 28 sur la pilo.

120
00:05:55,969 --> 00:05:57,010
Nu kion tio signifas?

121
00:05:57,010 --> 00:05:59,600
Nu nuntempe la
pinto de la stako estas 0.

122
00:05:59,600 --> 00:06:01,350
Do kio estas esence
okazos estas

123
00:06:01,350 --> 00:06:05,820
ni tuj algluita la nombro
28 en tabelo ĉelo 0.

124
00:06:05,820 --> 00:06:09,540
Bela simpla, justa, ke
estis la supro kaj nun ni estas bone iri.

125
00:06:09,540 --> 00:06:12,910
Kaj tiam ni bezonas ŝanĝi kion
la supro de la stako estos.

126
00:06:12,910 --> 00:06:15,130
Por ke la venontan fojon
ni puŝi ero en,

127
00:06:15,130 --> 00:06:18,017
ni iras por stoki ĝin en
tabelo situon, probable ne 0.

128
00:06:18,017 --> 00:06:20,100
Ni ne volas anstataŭigi
kion ni ĵus metis tie.

129
00:06:20,100 --> 00:06:23,510
Kaj tiel ni simple movi la supro al 1.

130
00:06:23,510 --> 00:06:24,890
Ke probable havas sencon.

131
00:06:24,890 --> 00:06:28,940
>> Nun se ni volas meti alia elemento
sur la pilo, ke ni volas puŝi 33,

132
00:06:28,940 --> 00:06:33,190
bone nun ni nur tuj prenos 33
kaj metis gxin antaux tabelo situon nombro

133
00:06:33,190 --> 00:06:37,580
1, kaj tiam ŝanĝi la supro de nia
pilo esti tabelo situon numero du.

134
00:06:37,580 --> 00:06:40,650
Do se la sekva tempo ni volas
puŝi ero sur la pilo,

135
00:06:40,650 --> 00:06:43,087
ĝi devos esti metita en tabelo 2 situon.

136
00:06:43,087 --> 00:06:44,420
Kaj ni faru ke unu pli fojon.

137
00:06:44,420 --> 00:06:45,753
Ni puŝas 19 for de la stakoj.

138
00:06:45,753 --> 00:06:48,940
Ni metos 19 en tabelo situon 2
kaj ŝanĝi la supro de nia stako

139
00:06:48,940 --> 00:06:51,220
esti tabelo situon 3
do se la sekva tempo ni

140
00:06:51,220 --> 00:06:54,780
bezonos fari puŝo ni estas bone iri.

141
00:06:54,780 --> 00:06:56,980
>> OK, Do jen puŝante en malmultaj vortoj.

142
00:06:56,980 --> 00:06:57,830
Kio pri krevanta?

143
00:06:57,830 --> 00:07:00,240
Do popping estas la speco de
contraparte al puŝanta.

144
00:07:00,240 --> 00:07:02,720
Ĝi estas kiel ni forigi datumojn de la stako.

145
00:07:02,720 --> 00:07:04,610
Kaj ĝenerale popo bezonoj
fari la sekvan.

146
00:07:04,610 --> 00:07:07,600
Ĝi bezonas akcepti puntero al la
pilo, denove en la ĝenerala kazo.

147
00:07:07,600 --> 00:07:10,480
En iuj aliaj kazo vi povus
deklaris la stako tutmonde,

148
00:07:10,480 --> 00:07:13,910
en kiu kazo vi ne bezonas por pasi ĝin
en ĉar ĝi jam havas aliron al ĝi

149
00:07:13,910 --> 00:07:15,541
kiel tutmonda variablo.

150
00:07:15,541 --> 00:07:17,040
Sed tiam kion alian ni devas fari?

151
00:07:17,040 --> 00:07:21,000
Nu ni pliigante
la supro de la stako en puŝo,

152
00:07:21,000 --> 00:07:24,050
do ni probable tuj volas
al dekremento la supro de la stako

153
00:07:24,050 --> 00:07:25,009
en popmuziko, dekstra?

154
00:07:25,009 --> 00:07:26,800
Kaj tiam kompreneble
ni ankaŭ tuj volas

155
00:07:26,800 --> 00:07:29,240
redoni la valoron ke ni forigu.

156
00:07:29,240 --> 00:07:32,125
Se ni aldonas elementojn, ni volas
akiri elementojn el pli poste,

157
00:07:32,125 --> 00:07:34,000
ni probable reale
volas konservi ilin tiel ni

158
00:07:34,000 --> 00:07:36,490
ne nur forigi ilin de la
pilo kaj tiam fari nenion kun ili.

159
00:07:36,490 --> 00:07:38,500
Ĝenerale, se ni estos
puŝanta kaj krevanta ĉi tie

160
00:07:38,500 --> 00:07:41,250
ni volas konservi tiun
informo en signfa vojo

161
00:07:41,250 --> 00:07:43,250
kaj do ĝi ne faros
sencon nur forĵeti ŝin.

162
00:07:43,250 --> 00:07:46,380
Do tiu funkcio devas
verŝajne resendas valoron por ni.

163
00:07:46,380 --> 00:07:51,040
>> Do jen kion deklaro por popmuziko
povus aspekti tie supre maldekstre.

164
00:07:51,040 --> 00:07:53,870
Tiu funkcio redonas
datumoj de tipo valoro.

165
00:07:53,870 --> 00:07:56,320
Denove ni estis uzante
entjeroj dum.

166
00:07:56,320 --> 00:08:01,916
Kaj ŝi akceptas puntero al stako kiel
ĝia sola argumento aŭ soleo parametro.

167
00:08:01,916 --> 00:08:03,040
Do kio estas popmuziko faros?

168
00:08:03,040 --> 00:08:07,990
Supozu ke ni volas nun
pop elementon de de s.

169
00:08:07,990 --> 00:08:14,000
Do memoru Mi diris ke stakoj estas lastaj
en, unue eksteren, LIFO datumstrukturoj.

170
00:08:14,000 --> 00:08:17,855
Kiu elemento tuj
esti forigita de la stako?

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

172
00:08:21,780 --> 00:08:24,150
Ĉu vi povas diveni 19?

173
00:08:24,150 --> 00:08:25,290
Ĉar vi estus prava.

174
00:08:25,290 --> 00:08:28,836
19 estis la lasta elemento ni aldonis al la
pilo kiam ni puŝas elementoj sur,

175
00:08:28,836 --> 00:08:31,210
kaj tiel ĝi tuj la unua
elemento kiu akiras forigita.

176
00:08:31,210 --> 00:08:34,780
Estas kvazaŭ ni diris 28, kaj
tiam ni metis 33 sur supro,

177
00:08:34,780 --> 00:08:36,659
kaj ni metis 19 Aldonigxis.

178
00:08:36,659 --> 00:08:40,650
La sola elemento ni povas despegar estas 19.

179
00:08:40,650 --> 00:08:45,019
>> Nun en la diagramo ĉi tie kion mi faris
estas ia forviŝita 19 de la tabelo.

180
00:08:45,019 --> 00:08:46,810
Tio ne reale
kion ni tuj faros.

181
00:08:46,810 --> 00:08:48,934
Ni nur tuj speco
de ŝajnigi ke gxi mankas.

182
00:08:48,934 --> 00:08:51,441
Ĝi estas ankoraŭ tie en
tiu memoro loko,

183
00:08:51,441 --> 00:08:54,190
sed ni simple tuj ignori ĝin
ŝanĝante la supro de nia stako

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

185
00:08:56,080 --> 00:08:58,720
Do se ni nun puŝi
alia elemento sur la pilo,

186
00:08:58,720 --> 00:09:00,720
estus super skribi 19.

187
00:09:00,720 --> 00:09:03,990
>> Sed ni ne iros tra la problemo
forigi 19 de la stako.

188
00:09:03,990 --> 00:09:05,830
Ni povas simple ŝajnigi ke gxi mankas.

189
00:09:05,830 --> 00:09:11,107
Por celoj de la stako ĝi estas irita se
ni ŝanĝas la supron esti 2 anstataŭ 3.

190
00:09:11,107 --> 00:09:12,690
Bone, tiel ke estis bele multe ĝi.

191
00:09:12,690 --> 00:09:15,080
Jen ĉio ni devas fari
krevi ero de.

192
00:09:15,080 --> 00:09:16,090
Ni faru tion denove.

193
00:09:16,090 --> 00:09:18,610
Do mi reliefigis ĝin en ruĝa tie
indiki ni fari alian alvokon.

194
00:09:18,610 --> 00:09:19,720
Ni tuj faros la samon.

195
00:09:19,720 --> 00:09:20,803
>> Do kio okazos?

196
00:09:20,803 --> 00:09:23,670
Nu, ni tuj stoki
33 en x kaj ni tuj

197
00:09:23,670 --> 00:09:26,217
ŝanĝi la supro de la stako al 1.

198
00:09:26,217 --> 00:09:29,050
Tiel ke se ni nun al peli
elemento en la stako kiu ni estas

199
00:09:29,050 --> 00:09:31,610
faros nun,
kio okazos

200
00:09:31,610 --> 00:09:36,367
Estas ni iras anstataŭigi
tabelo situon numero 1.

201
00:09:36,367 --> 00:09:38,950
Tiel ke 33 ke estis speco de maldekstra
malantaŭ ni nur ŝajnigis

202
00:09:38,950 --> 00:09:44,390
ne ekzistas plu, ni ĵus tuj
al clobber ĝin kaj metis 40 tie anstataŭe.

203
00:09:44,390 --> 00:09:46,290
Kaj tiam kompreneble
ĉar ni faris puŝon,

204
00:09:46,290 --> 00:09:48,780
ni tuj pliigo la
pinto de la stako de 1 al 2

205
00:09:48,780 --> 00:09:50,950
tiel ke se ni nun aldonu
alia elemento ĝi malebligos

206
00:09:50,950 --> 00:09:54,700
iri en tabelo situon numero du.

207
00:09:54,700 --> 00:09:57,590
>> Nun ligitaj listoj estas alia
maniero implementar stakoj.

208
00:09:57,590 --> 00:10:01,210
Kaj se tiu difino sur la
ekrano tie aspektas familiaraj al vi,

209
00:10:01,210 --> 00:10:04,260
ĝi estas ĉar ĝi aspektas preskaŭ
precize samaj, fakte,

210
00:10:04,260 --> 00:10:07,790
ĝi bele multe estas ekzakte la
sama kiel unuope ligillisto,

211
00:10:07,790 --> 00:10:11,990
se vi memoras el nia diskuto de
unuope ligitaj listoj en alia video.

212
00:10:11,990 --> 00:10:15,510
La sola limigo ĉi tie
estas por ni kiel programistoj,

213
00:10:15,510 --> 00:10:17,900
ni ne rajtas
enmeti aŭ forigi hazarde

214
00:10:17,900 --> 00:10:20,620
el la unuope ligita listo
kion ni povus fari antaŭe.

215
00:10:20,620 --> 00:10:25,820
Ni povas nur nun enmeti kaj forigi el
la fronto aŭ la supro de la ligitaj

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

217
00:10:26,320 --> 00:10:28,028
Tio estas vere la sola
diferenco tamen.

218
00:10:28,028 --> 00:10:29,700
Tiu estas alia maniero unuope ligita listo.

219
00:10:29,700 --> 00:10:32,060
Ĝi estas nur la limigo
anstataŭante sur nin

220
00:10:32,060 --> 00:10:35,770
kiel programistoj kiuj
ŝanĝas ĝin en stako.

221
00:10:35,770 --> 00:10:39,280
>> La regulo ĉi tie estas ĉiam subteni
sagon al la kapo de ligitaj listo.

222
00:10:39,280 --> 00:10:41,520
Tiu estas kompreneble ĝenerale
grava regulo unue.

223
00:10:41,520 --> 00:10:44,260
Por unuope ligita listo ĉiuokaze vi
nur bezonos montrilon al la kapo

224
00:10:44,260 --> 00:10:46,160
por havi tiun
ĉeno povos rilati

225
00:10:46,160 --> 00:10:48,596
al ĉiu alia elemento
en la ligitaj listo.

226
00:10:48,596 --> 00:10:50,470
Sed estas aparte
grava kun stako.

227
00:10:50,470 --> 00:10:52,386
Kaj do ĝenerale vi estas
tuj reale volas

228
00:10:52,386 --> 00:10:54,090
ĉi puntero esti tutmonda variablo.

229
00:10:54,090 --> 00:10:56,574
Ĝi estas probable tuj
estu plifacile tiel.

230
00:10:56,574 --> 00:10:58,240
Do kio estas la analogoj de puŝo kaj popo?

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

232
00:10:58,740 --> 00:11:01,812
Do puŝas denove aldonas
nova elemento al la stako.

233
00:11:01,812 --> 00:11:03,770
En ligillisto ke
Do oni tuj devas

234
00:11:03,770 --> 00:11:07,770
krei novajn nodo ke ni estas
tuj aldoni en la ligillisto,

235
00:11:07,770 --> 00:11:10,500
kaj tiam sekvas la zorgema paŝoj
ke ni skizis antaŭe

236
00:11:10,500 --> 00:11:16,050
en unuope ligitaj listoj aldoni ĝin al
la ĉeno sen rompi la ĉenon

237
00:11:16,050 --> 00:11:18,900
kaj perdante aŭ orphaning ajnan
elementoj de la ligitaj listo.

238
00:11:18,900 --> 00:11:21,820
Kaj tio estas esence kion tio
iom blob de teksto tie resumas.

239
00:11:21,820 --> 00:11:23,740
Kaj ni rigardu
ĉe ĝi kiel diagramo.

240
00:11:23,740 --> 00:11:24,823
>> Do jen nia ligillisto.

241
00:11:24,823 --> 00:11:26,620
Ĝi samtempe enhavas kvar elementoj.

242
00:11:26,620 --> 00:11:30,420
Kaj pli perfekte jen nia
pilo enhavanta kvar elementoj.

243
00:11:30,420 --> 00:11:36,030
Kaj diru ni nun volas
puŝi novan eron sur tiu stako.

244
00:11:36,030 --> 00:11:39,792
Kaj ni volas puŝi nova
elementon kies datumoj valoro estas 12.

245
00:11:39,792 --> 00:11:41,000
Nu kion ni faros?

246
00:11:41,000 --> 00:11:43,420
Nu unuan ni tuj
malloc spaco, dinamike

247
00:11:43,420 --> 00:11:45,411
destini spaco por nova nodo.

248
00:11:45,411 --> 00:11:48,160
Kaj kompreneble tuj post
ni faras alvokon al malloc ni ĉiam

249
00:11:48,160 --> 00:11:52,989
certigi por kontroli nula,
ĉar se ni akiris nula reen

250
00:11:52,989 --> 00:11:54,280
estis ia problemo.

251
00:11:54,280 --> 00:11:57,570
Ni ne volas dereference ke nula
montrilo aŭ vi suferos seg kulpo.

252
00:11:57,570 --> 00:11:58,510
Tio ne bona.

253
00:11:58,510 --> 00:11:59,760
Do ni malloced de la nodo.

254
00:11:59,760 --> 00:12:01,260
Ni supozu ni havis sukceson tie.

255
00:12:01,260 --> 00:12:06,090
Ni tuj metos 12 en
la datumoj de kampo de tiu nodo.

256
00:12:06,090 --> 00:12:11,570
Nun cxu vi memoras, kiu el niaj punteros
movas sekva tial ni ne rompi la ĉenon?

257
00:12:11,570 --> 00:12:15,100
Ni havas paron de ebloj tie sed
la sola kiu tuj estos al savas

258
00:12:15,100 --> 00:12:19,330
estas fiksi novaĵoj sekva puntero
punkton al la maljuna kapo de la listo

259
00:12:19,330 --> 00:12:21,360
aŭ kio baldaŭ estos la
malnova kapo de la listo.

260
00:12:21,360 --> 00:12:23,610
Kaj nun ke ĉiuj niaj
elementoj estas ĉenitaj kune,

261
00:12:23,610 --> 00:12:27,370
ni povas nur movi listo atentigi
al la sama loko kiu nova faras.

262
00:12:27,370 --> 00:12:33,550
Kaj ni nun efike puŝis
nova elemento sur la fronto de la stako.

263
00:12:33,550 --> 00:12:36,420
>> Krevi ni nur volas
forviŝi tiun unuan elementon.

264
00:12:36,420 --> 00:12:38,150
Kaj do esence kion
ni devas fari ĉi tie,

265
00:12:38,150 --> 00:12:40,050
bone ni devas trovi la dua elemento.

266
00:12:40,050 --> 00:12:43,540
Eventuale kiu igos la novan
kapo post ni forviŝi la unua unu.

267
00:12:43,540 --> 00:12:47,300
Do ni nur devas komenci de
la komenco, movi unu antaŭen.

268
00:12:47,300 --> 00:12:50,340
Iam ni trafis sur unu
antaŭen de kie ni nuntempe

269
00:12:50,340 --> 00:12:53,850
ni povas forviŝi la unua sekure
kaj tiam ni povas nur movi la kapon

270
00:12:53,850 --> 00:12:57,150
atentigi al kio estis la
dua oficperiodo kaj tiam nun

271
00:12:57,150 --> 00:12:59,170
estas la unua post tiu
nodo estis forigita.

272
00:12:59,170 --> 00:13:01,160
>> Do denove, prenante rigardu
ĉe ĝi kiel diagramo ni

273
00:13:01,160 --> 00:13:05,022
volas nun pop an
elementon de de tiu stako.

274
00:13:05,022 --> 00:13:05,730
Do kion ni faru?

275
00:13:05,730 --> 00:13:08,188
Nu ni unue tuj kreos
nova puntero ke tuj

276
00:13:08,188 --> 00:13:10,940
atentigi al la sama loko kiel la kapo.

277
00:13:10,940 --> 00:13:13,790
Ni tuj movi ĝin unu pozicion
antaŭen dirante trav egaluloj

278
00:13:13,790 --> 00:13:17,510
Trav sekva ekzemple, kiu
antaŭus la trav montrilo unu

279
00:13:17,510 --> 00:13:19,324
pozicio antaŭen.

280
00:13:19,324 --> 00:13:21,240
Nun ke ni havas
tenadi la unua elemento

281
00:13:21,240 --> 00:13:24,573
tra la puntero nomis lerta, kaj la
dua elemento tra puntero nomita

282
00:13:24,573 --> 00:13:28,692
trav, ni povas sekure forigi ke
unua elemento de la stako

283
00:13:28,692 --> 00:13:30,650
sen perdi la reston
de la ĉeno ĉar ni

284
00:13:30,650 --> 00:13:32,358
havi manieron rilati
al la dua ero

285
00:13:32,358 --> 00:13:34,780
plusendu tra la
puntero nomita trav.

286
00:13:34,780 --> 00:13:37,100
>> Do nun ni povas liberigi tiu nodo.

287
00:13:37,100 --> 00:13:38,404
Ni povas liberigi listo.

288
00:13:38,404 --> 00:13:41,320
Kaj tiam ĉiuj ni devas fari nun estas
movi listo atentigi al la sama loko

289
00:13:41,320 --> 00:13:44,482
ke trav faras, kaj ni estas speco de reen
kie ni komencis antaŭ ni puŝis 12

290
00:13:44,482 --> 00:13:45,690
sur la unua loko, dekstre.

291
00:13:45,690 --> 00:13:46,940
Tiu estas ĝuste kie ni estis.

292
00:13:46,940 --> 00:13:48,840
Ni havis ĉi kvar elemento pilo.

293
00:13:48,840 --> 00:13:49,690
Ni aldonis kvinan.

294
00:13:49,690 --> 00:13:51,910
Ni puŝis kvina
elementon, kaj poste ni

295
00:13:51,910 --> 00:13:55,980
krevita ke plej laste
aldonita elemento reen for.

296
00:13:55,980 --> 00:13:58,816
>> Tio estas vere bela multe
ĉiuj estas al stakoj.

297
00:13:58,816 --> 00:14:00,190
Vi povas apliki ilin kiel arrays.

298
00:14:00,190 --> 00:14:01,815
Vi povas apliki ilin kiel ligitaj listoj.

299
00:14:01,815 --> 00:14:04,810
Ekzistas, kompreneble, aliaj
manierojn apliki ilin ankaŭ.

300
00:14:04,810 --> 00:14:09,060
Esence la kialo ni uzus
stakoj estas subteni datumojn tiel

301
00:14:09,060 --> 00:14:12,090
ke la plej ĵuse aldonita
elemento estas la unua afero ni estas

302
00:14:12,090 --> 00:14:14,980
tuj volas reiri.

303
00:14:14,980 --> 00:14:17,900
Mi Doug Lloyd, tiu estas CS50.

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