1
00:00:00,000 --> 00:00:05,204

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Do se vi havas
spektis la videon sur pilo,

3
00:00:07,370 --> 00:00:09,870
Tio estas verŝajne iranta senti
kiel iomete de deja vu.

4
00:00:09,870 --> 00:00:13,850
Ĝi tuj tre simila koncepto,
nur kun eta tordaĵo sur ĝi.

5
00:00:13,850 --> 00:00:15,530
Ni tuj parolos nun pri atendovicoj.

6
00:00:15,530 --> 00:00:19,350
Do atendovico, simila al pilo,
Estas alia speco de datumstrukturo

7
00:00:19,350 --> 00:00:22,412
ke ni povas uzi por subteni
datumoj en organizita maniero.

8
00:00:22,412 --> 00:00:24,120
Similaj al pilo,
ĝi povas esti realigita

9
00:00:24,120 --> 00:00:27,000
kiel tabelo aŭ ligillisto.

10
00:00:27,000 --> 00:00:30,320
Kontraste stako, la reguloj
ke ni uzos por determini

11
00:00:30,320 --> 00:00:34,210
kiam aĵoj get aldonis kaj forigis de
atendovico estas iomete malsamaj.

12
00:00:34,210 --> 00:00:36,590
>> Kontraste pilo, kiu
Estas LIFO strukturo,

13
00:00:36,590 --> 00:00:45,610
daŭri en, unue eksteren, atendovico estas FIFO
strukturo, FIFO, unua en, unua el.

14
00:00:45,610 --> 00:00:49,320
Nun vostoj, vi probable
havas analogion al atendovicoj.

15
00:00:49,320 --> 00:00:52,820
Se vi iam estis en linio je
amuzparko aŭ ĉe banko,

16
00:00:52,820 --> 00:00:56,430
ekzistas ia justeco
efektivigado strukturo.

17
00:00:56,430 --> 00:00:59,160
La unua persono en linio je
la banko estas la unua persono

18
00:00:59,160 --> 00:01:00,760
Kiu akiras paroli al la kasisto.

19
00:01:00,760 --> 00:01:03,522
>> Estus ia raso
al la fundo, se la sola maniero

20
00:01:03,522 --> 00:01:06,730
vi devas paroli al la kasisto ĉe la
banko estis esti la lasta persono en linio.

21
00:01:06,730 --> 00:01:09,146
Cxiuj estus ĉiam volas
esti la lasta persono en linio,

22
00:01:09,146 --> 00:01:12,580
kaj la persono kiu estis tie unua
kiu estis atendante por momento,

23
00:01:12,580 --> 00:01:14,715
povus esti tie por horoj,
kaj horoj kaj horoj

24
00:01:14,715 --> 00:01:17,590
antaŭ ol ili havas ŝancon reale
retiri monon en la banko.

25
00:01:17,590 --> 00:01:22,510
Kaj tiel vostoj estas ia la
justeco efektivigado strukturo.

26
00:01:22,510 --> 00:01:25,780
Sed tio ne nepre signifas
ke stakoj estas malbona afero, nur

27
00:01:25,780 --> 00:01:28,160
ke vostoj estas alia maniero por fari ĝin.

28
00:01:28,160 --> 00:01:32,420
Do denove atendovico estas unua en, unua
eksteren, kontre pilo kiu daŭras en,

29
00:01:32,420 --> 00:01:34,440
unua el.

30
00:01:34,440 --> 00:01:36,190
Similaj al pilo,
ni havos du operacioj

31
00:01:36,190 --> 00:01:38,470
ke ni povas realigi sur vostoj.

32
00:01:38,470 --> 00:01:43,910
La nomoj estas enqueue, kiu estas aldoni
nova elemento al la fino de la vico,

33
00:01:43,910 --> 00:01:47,330
kaj dequeue, kiu estas
forigi la malnova

34
00:01:47,330 --> 00:01:49,670
elemento de la fronto de la atendovico.

35
00:01:49,670 --> 00:01:53,600
Do ni tuj aldonu elementoj
sur la fino de la vico,

36
00:01:53,600 --> 00:01:57,220
kaj ni tuj forigos elementoj
de la fronto de la atendovico.

37
00:01:57,220 --> 00:02:00,790
Denove kun la pilo, ni estis aldono
elementoj al la supro de la stako

38
00:02:00,790 --> 00:02:03,380
kaj forigado elementoj
De la supro de la stako.

39
00:02:03,380 --> 00:02:07,570
Do kun enqueue, ĝi estas aldono al
Fine apartigu el la fronto.

40
00:02:07,570 --> 00:02:10,639
Do la plej malnova afero tien
estas ĉiam la sekva afero

41
00:02:10,639 --> 00:02:13,620
eliri se ni provas
kaj dequeue ion.

42
00:02:13,620 --> 00:02:18,330
>> Do denove, kun vostoj, ni povas
tabelo-bazita implementaciones

43
00:02:18,330 --> 00:02:20,110
kaj ligitaj listo bazita implementaciones.

44
00:02:20,110 --> 00:02:24,620
Ni komencu denove kun
tabelo-bazita implementaciones.

45
00:02:24,620 --> 00:02:27,070
La strukturo difino
aspektas sufiĉe simila.

46
00:02:27,070 --> 00:02:30,720
Ni havas alian tabelo
tie de datumtipo valoro,

47
00:02:30,720 --> 00:02:32,690
do ĝi povas teni arbitra datumtipoj.

48
00:02:32,690 --> 00:02:35,570
Ni denove uzos
entjeroj en tiu ekzemplo.

49
00:02:35,570 --> 00:02:39,830
>> Kaj ĝuste kiel kun niaj
tabelo-bazita pilo efektivigo,

50
00:02:39,830 --> 00:02:42,340
ĉar ni uzas la
tabelo, ni nepre

51
00:02:42,340 --> 00:02:46,850
havas tiun limigon ke C speco
de efikigas sur nin, kio estas ni

52
00:02:46,850 --> 00:02:51,670
ne havas dinamismo en nia
kapablo kreski kaj ŝrumpi la tabelo.

53
00:02:51,670 --> 00:02:55,710
Ni devas decidi komence
kio estas la maksimuma nombro de aferoj

54
00:02:55,710 --> 00:02:59,300
ke ni povas meti en tiun
atendovico, kaj en tiu kazo,

55
00:02:59,300 --> 00:03:02,070
kapablo estus iu funto
difinita konstanto en nia kodo.

56
00:03:02,070 --> 00:03:05,430
Kaj por la celoj de ĉi tiu
vídeo, kapablo tuj estos 10.

57
00:03:05,430 --> 00:03:07,690
>> Ni devas sekvigi
la fronto de la atendovico

58
00:03:07,690 --> 00:03:11,160
tial ni scias ke elemento
ni volas dequeue,

59
00:03:11,160 --> 00:03:15,070
kaj ni ankaŭ devas teni trako de
io else-- la nombro de elementoj

60
00:03:15,070 --> 00:03:16,690
ke ni havas en nia vosto.

61
00:03:16,690 --> 00:03:19,360
Rimarku ni ne konservanta trako
de la fino de la vosto, same

62
00:03:19,360 --> 00:03:21,150
la grandeco de la vosto.

63
00:03:21,150 --> 00:03:24,310
Kaj la kialo por ke espereble
fariĝis iom pli klara en momento.

64
00:03:24,310 --> 00:03:26,143
Unufoje ni kompletigis
tiu tipo difino,

65
00:03:26,143 --> 00:03:29,080
ni havas novan datumtipo
nomata vosto, kiun ni povas nun

66
00:03:29,080 --> 00:03:30,630
deklari variablojn de tiu datumtipo.

67
00:03:30,630 --> 00:03:35,350
Kaj iom konfuze, mi decidis
nomi tiun atendovico q, la letero

68
00:03:35,350 --> 00:03:38,090
q anstataŭ la datumtipo q.

69
00:03:38,090 --> 00:03:39,600
>> Do tie estas nia vico.

70
00:03:39,600 --> 00:03:40,700
Estas strukturo.

71
00:03:40,700 --> 00:03:45,730
Ĝi enhavas tri membroj aŭ tri
kampoj, tabelo de grandeco kapablo.

72
00:03:45,730 --> 00:03:47,340
En tiu kazo, kapablo estas 10.

73
00:03:47,340 --> 00:03:49,580
Kaj ĉi tabelo estas
tenos entjeroj.

74
00:03:49,580 --> 00:03:55,240
Verde estas la fronto de niaj vosto, la
sekva elemento esti forigita, kaj en ruĝa

75
00:03:55,240 --> 00:03:58,610
estos la grandeco de la vosto,
kiom da elementoj nuntempe

76
00:03:58,610 --> 00:04:01,190
ekzistantaj en la vico.

77
00:04:01,190 --> 00:04:05,300
Do se ni diras q.front egaluloj
0, kaj q.size grandeco egalas 0--

78
00:04:05,300 --> 00:04:07,120
ni metante _0s_ en tiuj kampoj.

79
00:04:07,120 --> 00:04:11,070
Kaj je tiu punkto, ni estas preskaux
pretas komenci laboranta kun niaj vosto.

80
00:04:11,070 --> 00:04:14,140
>> Do la unua operacio eblan
elfari estas enqueue ion,

81
00:04:14,140 --> 00:04:16,860
aldoni novan elementon al
la fino de la vico.

82
00:04:16,860 --> 00:04:19,089
Nu kion ni bezonas
plenumi en la ĝenerala kazo?

83
00:04:19,089 --> 00:04:23,690
Nu tiu funkcio enqueue bezonoj
akcepti puntero al nia vosto.

84
00:04:23,690 --> 00:04:26,370
Denove, se ni klariginte
nia vico tutmonde,

85
00:04:26,370 --> 00:04:29,490
ni ne bezonas fari tion
nepre, sed en ĝenerala, ni

86
00:04:29,490 --> 00:04:32,330
bezonas akcepti punteros
al datumstrukturoj

87
00:04:32,330 --> 00:04:35,040
tiel, ĉar alie,
ni preteriras value-- ni estas

88
00:04:35,040 --> 00:04:38,140
pasante en kopioj de la atendovico,
kaj do ni ne efektive ŝanĝanta

89
00:04:38,140 --> 00:04:41,050
la vosto kiu ni intencas ŝanĝi.

90
00:04:41,050 --> 00:04:44,860
>> La alia afero bezonas fari estas akcepti
datuma elemento de la konvena tipo.

91
00:04:44,860 --> 00:04:46,818
Denove, en tiu kazo, ĝi estas
tuj estos entjeroj,

92
00:04:46,818 --> 00:04:49,330
sed vi povus arbitre
deklari la datumtipo kiel valoro

93
00:04:49,330 --> 00:04:51,160
kaj uzi tiun pli ĝenerale.

94
00:04:51,160 --> 00:04:56,030
Tio estas la elemento ni volas enqueue,
Ni volas aldoni al la fino de la vico.

95
00:04:56,030 --> 00:04:58,573
Tiam ni efektive volas
meti ke datumoj en la vico.

96
00:04:58,573 --> 00:05:01,490
En tiu kazo, metante ĝin en la
korekta loko de nia tabelo,

97
00:05:01,490 --> 00:05:05,040
kaj tiam ni volas ŝanĝi la grandecon
de la atendovico, kiom da eroj ni

98
00:05:05,040 --> 00:05:07,050
aktuale havas.

99
00:05:07,050 --> 00:05:07,990
>> Do ni komencu.

100
00:05:07,990 --> 00:05:10,890
Jen, denove, ke ĝenerala
formo funkcio deklaro

101
00:05:10,890 --> 00:05:13,980
por kio enqueue povus aspekti.

102
00:05:13,980 --> 00:05:14,910
Kaj tie ni iru.

103
00:05:14,910 --> 00:05:18,335
Ni enqueue la nombro
28 en la vico.

104
00:05:18,335 --> 00:05:19,460
Do kion ni faros?

105
00:05:19,460 --> 00:05:23,390
Nu, la fronto de niaj atendovico estas
je 0, kaj la grandeco de nia atendovico

106
00:05:23,390 --> 00:05:29,680
estas je 0, kaj tial ni probable volas meti
la numero 28 en tabelo elemento nombro

107
00:05:29,680 --> 00:05:31,124
0, dekstra?

108
00:05:31,124 --> 00:05:32,540
Do ni nun metis tiun en tie.

109
00:05:32,540 --> 00:05:34,820
Do nun kion ni devas ŝanĝi?

110
00:05:34,820 --> 00:05:37,090
Ni ne volas ŝanĝi
la fronto de la atendovico,

111
00:05:37,090 --> 00:05:40,850
ĉar ni deziras scii kion elemento
Ni eble bezonas dequeue poste.

112
00:05:40,850 --> 00:05:44,020
Do la kialo ni havas antaux tie
estas ia indikilo de kio estas

113
00:05:44,020 --> 00:05:46,439
la plej malnova aĵo en la tabelo.

114
00:05:46,439 --> 00:05:49,730
Nu la plej malnova aĵo en la tabelo en
Fakte, la sola afero en la tabelo dekstra

115
00:05:49,730 --> 00:05:53,540
now-- estas 28, kiu estas
ĉe tabelo ĉelo 0.

116
00:05:53,540 --> 00:05:56,160
Do ni ne volas
ŝanĝi tiun verdan numeron,

117
00:05:56,160 --> 00:05:57,910
ĉar tio estas la plej malnova elemento.

118
00:05:57,910 --> 00:06:00,510
Prefere, ni volas ŝanĝi la grandecon.

119
00:06:00,510 --> 00:06:04,110
Do en ĉi tiu kazo, ni devos
pliigo grandeco al 1.

120
00:06:04,110 --> 00:06:08,430
>> Nun ĝeneralan ian ideon de kie la
sekva elemento tuj iros en atendovico

121
00:06:08,430 --> 00:06:12,310
estas aldoni tiujn du nombroj
kune, fronto kaj grandeco,

122
00:06:12,310 --> 00:06:16,390
kaj tio diros al vi kie la sekva
elemento en la vico tuj iros.

123
00:06:16,390 --> 00:06:18,130
Do nun ni enqueue alian numeron.

124
00:06:18,130 --> 00:06:20,250
Ni enqueue 33.

125
00:06:20,250 --> 00:06:24,480
Do 33 tuj iri en
tabelo ĉelo 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Do en ĉi tiu kazo, ĝi tuj
enirontajn en tabelo situon 1,

127
00:06:26,840 --> 00:06:29,500
kaj nun la grandecon de nia vosto estas 2.

128
00:06:29,500 --> 00:06:31,840
>> Denove, ni ne ŝanĝas
la fronto de niaj vosto,

129
00:06:31,840 --> 00:06:34,730
ĉar 28 estas ankoraŭ la
malnova elemento, kaj ni

130
00:06:34,730 --> 00:06:38,220
volas to-- kiam ni eventuale akiri
al dequeuing, forigante elementojn

131
00:06:38,220 --> 00:06:43,300
de tiu vosto, ni volas scii
kie la plej malnova elemento estas.

132
00:06:43,300 --> 00:06:48,620
Kaj do ni ĉiam devas subteni
iu indikilo de kie tiu estas.

133
00:06:48,620 --> 00:06:50,410
Do jen kion la 0 estas tie por.

134
00:06:50,410 --> 00:06:52,910
Tion fronto estas tie por.

135
00:06:52,910 --> 00:06:55,022
>> Ni en enqueue pli elemento, 19.

136
00:06:55,022 --> 00:06:56,980
Mi certas ke vi povas diveni
kie 19 estas iranta iri.

137
00:06:56,980 --> 00:06:59,860
Ĝi tuj iri en
tabelo situon numero 2.

138
00:06:59,860 --> 00:07:01,570
Tio 0 plus 2.

139
00:07:01,570 --> 00:07:03,199
Kaj nun la grandecon de nia vosto estas 3.

140
00:07:03,199 --> 00:07:04,240
Ni havas 3 elementojn en ĝi.

141
00:07:04,240 --> 00:07:08,490
Do se ni estis, kaj ni ne tuj
por nun, enqueue alia elemento,

142
00:07:08,490 --> 00:07:11,370
ĝi irus en tabelo location
numero 3, kaj la grandeco de nia atendovico

143
00:07:11,370 --> 00:07:13,160
estus 4.

144
00:07:13,160 --> 00:07:15,279
Do ni enqueued pluraj elementoj nun.

145
00:07:15,279 --> 00:07:16,570
Nun ni komencu forigi ilin.

146
00:07:16,570 --> 00:07:19,450
Ni dequeue ilin de atendovico.

147
00:07:19,450 --> 00:07:23,340
>> Do simila al popmuziko, kiu estas speco
de la analoga de tiu por stakoj,

148
00:07:23,340 --> 00:07:26,180
dequeue bezonas akcepti
sagon al la queue-- denove,

149
00:07:26,180 --> 00:07:28,140
krom se ĝi estas tutmonde deklaris.

150
00:07:28,140 --> 00:07:31,610
Nun ni volas ŝanĝi la lokon
de la fronto de la atendovico.

151
00:07:31,610 --> 00:07:35,050
Jen kie ia venas
en ludon, tiu fronto ŝanĝiĝema,

152
00:07:35,050 --> 00:07:37,310
ĉar iam ni forigu
ero, ni volas

153
00:07:37,310 --> 00:07:40,720
movi ĝin al la venonta plej malnova elemento.

154
00:07:40,720 --> 00:07:44,180
>> Tiam ni volas malpliigi
la grandeco de la vosto,

155
00:07:44,180 --> 00:07:47,130
kaj tiam ni volas reveni al la valoro
kiu estis forigita de la atendovico.

156
00:07:47,130 --> 00:07:48,921
Denove, ni ne volas simple forĵeti ĝin.

157
00:07:48,921 --> 00:07:51,170
Ni supozeble ankaŭ ĉerpas
ĝin de la queue-- ni estas

158
00:07:51,170 --> 00:07:54,170
dequeuing ĝin ĉar ni zorgas pri ĝi.

159
00:07:54,170 --> 00:08:01,080
Do ni volas tiun funkcion reveni
datuma elemento de tipo valoro.

160
00:08:01,080 --> 00:08:04,360
Denove, en tiu kazo, valoro estas entjero.

161
00:08:04,360 --> 00:08:05,670
>> Do nun ni dequeue ion.

162
00:08:05,670 --> 00:08:09,310
Ni forigu ero de la vico.

163
00:08:09,310 --> 00:08:15,970
Se ni diras int x egalas & q, ampersand q--
denove jen puntero al tiu q datumoj

164
00:08:15,970 --> 00:08:20,177
structure-- kion elemento
tuj estos dequeued?

165
00:08:20,177 --> 00:08:23,840

166
00:08:23,840 --> 00:08:29,480
En tiu kazo, ĉar ĝi estas unua
en, unua el datumstrukturo, FIFO,

167
00:08:29,480 --> 00:08:33,690
ni unue metas en tiun
atendovico estis 28, kaj tiel en tiu kazo,

168
00:08:33,690 --> 00:08:37,245
ni iras preni 28 el
la vosto, ne 19, kion estas kio

169
00:08:37,245 --> 00:08:38,870
ni estus farinta se tiu estis stako.

170
00:08:38,870 --> 00:08:42,220
Ni iras preni 28 el la vico.

171
00:08:42,220 --> 00:08:44,960
>> Similaj al kion ni faris kun
pilo, ni ne vere

172
00:08:44,960 --> 00:08:47,345
tuj forviŝi 28
el la vosto mem,

173
00:08:47,345 --> 00:08:49,470
ni nur tuj speco
de ŝajnigi ke gxi mankas.

174
00:08:49,470 --> 00:08:51,678
Do ĝi estas tuj restos tie
en memoro, sed ni estas nur

175
00:08:51,678 --> 00:08:57,820
tuj speco de ignori ĝin movante
la aliaj du kampoj de nia q datumoj

176
00:08:57,820 --> 00:08:58,830
strukturo.

177
00:08:58,830 --> 00:09:00,230
Ni tuj ŝanĝos la fronton.

178
00:09:00,230 --> 00:09:04,290
Q.front nun tuj
esti 1, pro tio estas nun

179
00:09:04,290 --> 00:09:07,740
la plej malnova elemento kiun ni havas en nia
atendovico, ĉar ni jam forigis 28

180
00:09:07,740 --> 00:09:10,460
kiu estis la iama plej malnova elemento.

181
00:09:10,460 --> 00:09:13,540
>> Kaj nun, ni volas ŝanĝi
la grandeco de la vosto

182
00:09:13,540 --> 00:09:15,780
por du elementoj anstataŭ tri.

183
00:09:15,780 --> 00:09:20,450
Nun memoru frue mi diris, kiam ni
volas aldoni elementojn al la atendovico,

184
00:09:20,450 --> 00:09:26,000
ni metu ĝin en tabelo location
kiu estas la sumo de fronto kaj grandeco.

185
00:09:26,000 --> 00:09:29,050
Do en ĉi tiu kazo, ni ankoraŭ metante
ĝi, la sekvanta elemento en la vico,

186
00:09:29,050 --> 00:09:33,360
en tabelo loko 3, kaj
Ni vidos ke en dua.

187
00:09:33,360 --> 00:09:35,730
>> Do ni nun dequeued nia
unua elemento de la vico.

188
00:09:35,730 --> 00:09:36,480
Ni faru tion denove.

189
00:09:36,480 --> 00:09:38,696
Ni forigu alian
elemento de la vico.

190
00:09:38,696 --> 00:09:42,400
En la kazo, la nuna malnova
elemento estas tabelo situon 1.

191
00:09:42,400 --> 00:09:44,220
Tion q.front diras ni.

192
00:09:44,220 --> 00:09:46,980
Ke verda skatolo nin diras ke
tio estas la plej malnova elemento.

193
00:09:46,980 --> 00:09:49,310
Kaj do, x fariĝos 33.

194
00:09:49,310 --> 00:09:52,130
Ni nur ia forgesas
ke 33 ekzistas en la tabelo,

195
00:09:52,130 --> 00:09:55,100
kaj ni diru, ke nun, la
novajn plej malnova ero en la atendovico

196
00:09:55,100 --> 00:09:58,900
estas ĉe tabelo loko 2, kaj la grandeco
de la atendovico, la nombro de elementoj

197
00:09:58,900 --> 00:10:02,152
ni havas en la vosto, estas 1.

198
00:10:02,152 --> 00:10:05,110
Nun ni enqueue io, kaj mi
ia donis tiun for sekundo antaŭ,

199
00:10:05,110 --> 00:10:10,340
sed se ni volas meti 40 en la
atendovico, kie estas 40 tuj iros?

200
00:10:10,340 --> 00:10:12,880

201
00:10:12,880 --> 00:10:17,730
Nu ni estis metante gxin
en q.front plus atendovico grandeco,

202
00:10:17,730 --> 00:10:20,850
kaj tiel ĝi havas sencon
reale meti 40 tie.

203
00:10:20,850 --> 00:10:22,840
Nun rimarkas ke ĉe
iu punkto, ni tuj

204
00:10:22,840 --> 00:10:27,980
akiri al la fino de
nia tabelo interne de q,

205
00:10:27,980 --> 00:10:32,010
sed ke elsenkoloriĝis 28 kaj 33--
ili estas reale, teknike

206
00:10:32,010 --> 00:10:33,300
malferma spacoj, dekstra?

207
00:10:33,300 --> 00:10:36,040
Kaj tiel, ni eventually--
regulon de aldonado

208
00:10:36,040 --> 00:10:40,390
tiuj du together-- ni povas eventuale
bezonas mod per la grandeco de kapacito

209
00:10:40,390 --> 00:10:41,410
tiel ni povas envolvi ĉirkaŭe.

210
00:10:41,410 --> 00:10:43,620
>> Do se ni atingos elemento
numero 10, se ni estas

211
00:10:43,620 --> 00:10:48,790
anstataŭante ĝin elemento numero 10, ni preferus
efektive metis ĝin en tabelo ĉelo 0.

212
00:10:48,790 --> 00:10:50,997
Kaj se ni iris al
tabelo location-- pardonu,

213
00:10:50,997 --> 00:10:53,080
se ni aldonas ilin kune,
kaj ni atingis numeron

214
00:10:53,080 --> 00:10:56,330
11 estus kie ni devus meti
ĝin, kiu ne ekzistas en tiu tabelo

215
00:10:56,330 --> 00:10:58,200
ĝi estus iranta el baroj.

216
00:10:58,200 --> 00:11:03,367
Ni povis mod per 10 kaj metis
ĝi pafu situon 1.

217
00:11:03,367 --> 00:11:04,450
Do jen kiel vostoj labori.

218
00:11:04,450 --> 00:11:08,540
Ili estas ĉiam iranta iri de maldekstra
dekstren kaj eble envolvi ĉirkaŭe.

219
00:11:08,540 --> 00:11:11,280
Kaj vi scias, ke ili estas
plena se grandeco, ke ruĝa skatolo,

220
00:11:11,280 --> 00:11:13,710
iĝas egala al kapacito.

221
00:11:13,710 --> 00:11:16,720
Kaj do post ni aldonis 40 por la
atendovico, bone kion ni devas fari?

222
00:11:16,720 --> 00:11:19,890
Nu, la plej malnova elemento
en la atendovico estas ankoraŭ 19,

223
00:11:19,890 --> 00:11:21,990
tial ni ne volas ŝanĝi
la fronto de la atendovico,

224
00:11:21,990 --> 00:11:23,820
sed nun ni havas du
elementoj en la vosto,

225
00:11:23,820 --> 00:11:28,710
kaj tiel ni volas pliigi
nia grando el 1 al 2.

226
00:11:28,710 --> 00:11:31,820
>> Tio estas sufiĉe multe ĝin kun
laborante kun tabelo-bazita atendovicoj,

227
00:11:31,820 --> 00:11:33,630
kaj simila al pilo,
ekzistas ankaŭ vojo

228
00:11:33,630 --> 00:11:36,450
implementar atendovico kiel ligillisto.

229
00:11:36,450 --> 00:11:40,150
Nun se tiu datumstrukturo tipo
aspektas familiaraj al vi, ĝi estas.

230
00:11:40,150 --> 00:11:43,780
Ĝi ne estas unuope ligillisto,
ĝi estas duoble ligitaj listo.

231
00:11:43,780 --> 00:11:46,790
Kaj nun, kiel flanken, estas
fakte eblas apliki

232
00:11:46,790 --> 00:11:50,160
atendovico kiel unuope ligita listo, sed
Mi pensas en terminoj de visualización,

233
00:11:50,160 --> 00:11:53,350
ĝi efektive povus helpi al vidi
tion kiel duoble ligita listo.

234
00:11:53,350 --> 00:11:56,850
Sed estas sendube ebla
faras tion kiel unuope ligita listo.

235
00:11:56,850 --> 00:12:00,110
>> Do ni havas rigardi
kion tio povus aspekti.

236
00:12:00,110 --> 00:12:02,750
Se ni volas enquue--
tial nun, denove ni estas

237
00:12:02,750 --> 00:12:05,360
ŝaltanta al kunligita-listo
bazita modelo tie.

238
00:12:05,360 --> 00:12:08,420
Se ni volas enqueue, ni volas
aldoni novan elementon, bone

239
00:12:08,420 --> 00:12:09,730
kion ni devas fari?

240
00:12:09,730 --> 00:12:12,770
Nu, unue, ĉar
ni aldonante al la fino

241
00:12:12,770 --> 00:12:15,520
forigo de la
komencante, ni probable

242
00:12:15,520 --> 00:12:20,050
volas subteni punteros al ambaŭ la
kapo kaj la vosto de la ligitaj listo?

243
00:12:20,050 --> 00:12:22,660
Vosto esti alia termino por
la fino de la ligillisto,

244
00:12:22,660 --> 00:12:24,496
la lasta elemento en la ligitaj listo.

245
00:12:24,496 --> 00:12:26,620
Kaj tiuj verŝajne,
denove, esti utila al ni

246
00:12:26,620 --> 00:12:28,477
se ili estas tutmonda variabloj.

247
00:12:28,477 --> 00:12:31,060
Sed nun se ni volas aldoni novan
elemento kion ni devas fari?

248
00:12:31,060 --> 00:12:35,262
Kion ni ĵus [? Malak?] aŭ dinamike
asigni nia nova nodo por ni mem.

249
00:12:35,262 --> 00:12:38,220
Kaj tiam, ĝuste kiel kiam ni aldonas neniun
elemento al duoble ligillisto ni,

250
00:12:38,220 --> 00:12:40,410
nur devi ordigi of--
tiuj lastaj tri paŝojn tie

251
00:12:40,410 --> 00:12:43,330
estas nur ĉio pri movanta la
punteros en la korekta maniero

252
00:12:43,330 --> 00:12:46,710
por ke la elemento gets aldonita al
la ĉeno sen rompi la ĉenon

253
00:12:46,710 --> 00:12:49,580
aŭ farante ian eraro
aŭ havantaj iun specon de akcidento

254
00:12:49,580 --> 00:12:54,505
okazi per kiu ni hazarde
Orfino iuj elementoj de nia vico.

255
00:12:54,505 --> 00:12:55,880
Jen kion ĉi povus aspekti.

256
00:12:55,880 --> 00:13:00,980
Ni volas aldoni la elementon
10 al la fino de tiu vico.

257
00:13:00,980 --> 00:13:03,380
Do la plej malnova elemento tie
estas reprezentita de kapo.

258
00:13:03,380 --> 00:13:06,800
Tio estas la unua afero ni metu
en tiu hipotético atendovico tie.

259
00:13:06,800 --> 00:13:10,430
Kaj vosto, 13, estas la plej
ĵus aldonita elemento.

260
00:13:10,430 --> 00:13:17,030
Kaj do se ni volas enqueue 10 en
tiu vosto, ni volas meti ĝin post 13.

261
00:13:17,030 --> 00:13:19,860
Kaj do ni tuj dinamike
destini spaco por nova nodo

262
00:13:19,860 --> 00:13:23,280
kaj kontroli por nula certigi
ni ne havas memoron fiasko.

263
00:13:23,280 --> 00:13:27,040
Tiam ni tuj
meti 10 en tiu nodo,

264
00:13:27,040 --> 00:13:30,030
kaj nun ni devas atenti
pri kiel ni organizi punteros

265
00:13:30,030 --> 00:13:32,180
do ni ne rompi la ĉenon.

266
00:13:32,180 --> 00:13:38,910
>> Ni povas agordi 10 la antaŭa kampo
atentigi reen al la malnova vosto,

267
00:13:38,910 --> 00:13:41,620
kaj ekde '10 estos la
novajn vosto en iu punkto

268
00:13:41,620 --> 00:13:44,459
por kiam ĉiuj tiuj
ĉenoj estas konektitaj,

269
00:13:44,459 --> 00:13:46,250
nenio tuj venu
post 10 nun.

270
00:13:46,250 --> 00:13:49,880
Kaj do 10 la sekvanta puntero
indikos al nula,

271
00:13:49,880 --> 00:13:53,580
kaj tiam post ni fari tion, ni ja
konektita 10 malantaŭen al la ĉeno,

272
00:13:53,580 --> 00:13:57,780
ni povas preni la malnova kapo, aŭ, senkulpigo
Mi, la malnova vosto de la vosto.

273
00:13:57,780 --> 00:14:02,980
La malnova fino de la vico,
13 kaj faru por ĝi indikas 10.

274
00:14:02,980 --> 00:14:08,220
Kaj nun, je ĉi tiu punkto, ni havas
enqueued la numero 10 en tiu vico.

275
00:14:08,220 --> 00:14:14,740
Ĉiuj ni devas fari nun estas simple movi la
voston por indiki al 10 anstataŭ 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing estas reale
tre simila al krevanta

277
00:14:17,630 --> 00:14:21,710
el stako kiu estas
implementados kiel ligillisto

278
00:14:21,710 --> 00:14:24,040
se vi vidos la stakoj vídeo.

279
00:14:24,040 --> 00:14:27,280
Ĉiuj ni devas fari estas komenci ĉe la
komencante, trovi la dua elemento,

280
00:14:27,280 --> 00:14:30,480
liberigi la unua elemento,
kaj tiam movi la kapon

281
00:14:30,480 --> 00:14:32,930
atentigi al la dua elemento.

282
00:14:32,930 --> 00:14:37,920
Probable pli bone bildigi ĝi
Nur esti kroma klara pri tio.

283
00:14:37,920 --> 00:14:39,230
Do jen nia vosto denove.

284
00:14:39,230 --> 00:14:42,600
12 estas la plej malnova elemento
en nia vosto, la kapo.

285
00:14:42,600 --> 00:14:46,210
10 estas la plej nova elemento
en nia vosto, nia vosto.

286
00:14:46,210 --> 00:14:49,310
>> Kaj tial kiam ni volas
al dequeue ero,

287
00:14:49,310 --> 00:14:52,202
ni deziras forigi la plej malnova elemento.

288
00:14:52,202 --> 00:14:52,910
Do kion ni faru?

289
00:14:52,910 --> 00:14:55,243
Nu ni aperigos trairado montrilon
kiu komenciĝas ĉe la kapo,

290
00:14:55,243 --> 00:14:57,840
kaj ni movas ŝin por ke ĝi
montras al la dua ero

291
00:14:57,840 --> 00:15:02,290
de tiu queue-- ion dirante trav
egalas trav arrow sekva, ekzemple,

292
00:15:02,290 --> 00:15:07,170
movus trav tie atentigi al
15, kiuj, post ni dequeue 12

293
00:15:07,170 --> 00:15:13,030
aŭ post ni forpreni 12, volo
fariĝis la tiama plej malnova elemento.

294
00:15:13,030 --> 00:15:16,360
>> Nun ni havas tenon sur la unua
elemento tra la montrilon kapo

295
00:15:16,360 --> 00:15:19,440
kaj la dua elemento
tra la montrilon trav.

296
00:15:19,440 --> 00:15:25,170
Ni povas nun libera kapon, kaj tiam ni povas
diru nenion venas antaŭ 15 anymore.

297
00:15:25,170 --> 00:15:29,990
Do ni povas ŝanĝi 15 la antaŭa
puntero atentigi al nula,

298
00:15:29,990 --> 00:15:31,874
kaj ni simple movi la kapon super.

299
00:15:31,874 --> 00:15:32,540
Kaj tie ni iru.

300
00:15:32,540 --> 00:15:35,840
Nun ni havas sukcese
dequeued 12, kaj nun ni

301
00:15:35,840 --> 00:15:39,180
havas alian atendovico de 4 elementoj.

302
00:15:39,180 --> 00:15:41,700
Tio estas sufiĉe multe ĉiuj
oni devas atendovicoj,

303
00:15:41,700 --> 00:15:45,810
ambaŭ tabelo-bazita kaj ligitaj listo bazita.

304
00:15:45,810 --> 00:15:46,860
Mi Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Jen CS 50.

306
00:15:49,100 --> 00:15:50,763