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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Nii et kui olete
vaatasin videot korstnat,

3
00:00:07,370 --> 00:00:09,870
see on ilmselt läheb tunda
nagu natuke deja vu.

4
00:00:09,870 --> 00:00:13,850
See läheb väga sarnane kontseptsioon,
lihtsalt kerge väänata seda.

5
00:00:13,850 --> 00:00:15,530
Me läheme praegu rääkida umbes järjekorrad.

6
00:00:15,530 --> 00:00:19,350
Nii järjekorras, mis on sarnane pinu
on teine ​​selline andmestruktuur

7
00:00:19,350 --> 00:00:22,412
et saame kasutada, et säilitada
andmed organiseeritud viisil.

8
00:00:22,412 --> 00:00:24,120
Sarnaselt korstna
seda saab rakendada

9
00:00:24,120 --> 00:00:27,000
massiiv või ahelloend.

10
00:00:27,000 --> 00:00:30,320
Erinevalt korstna reeglid
mida me kasutame, et teha kindlaks

11
00:00:30,320 --> 00:00:34,210
siis, kui asjad lisada ja eemaldada
järjekorras on natuke erinev.

12
00:00:34,210 --> 00:00:36,590
>> Erinevalt virna, mis
on LIFO struktuuri,

13
00:00:36,590 --> 00:00:45,610
kesta sisse, esimesena välja, järjekord on FIFO
struktuuri, FIFO, esimene, esimene välja.

14
00:00:45,610 --> 00:00:49,320
Nüüd järjekorrad, siis ilmselt
on analoogia järjekorrad.

15
00:00:49,320 --> 00:00:52,820
Kui sa oled kunagi olnud joone
lõbustuspargi või pangas,

16
00:00:52,820 --> 00:00:56,430
seal on omamoodi õigluse
rakendamise struktuur.

17
00:00:56,430 --> 00:00:59,160
Esimene inimene joone
pank on esimene inimene

18
00:00:59,160 --> 00:01:00,760
kes saab rääkida teller.

19
00:01:00,760 --> 00:01:03,522
>> Oleks omamoodi võidujooks
põhja kui ainus võimalus

20
00:01:03,522 --> 00:01:06,730
sul rääkida teller juures
pank pidi olema viimane inimene line.

21
00:01:06,730 --> 00:01:09,146
Igaüks oleks alati tahtnud
olema viimane inimene line,

22
00:01:09,146 --> 00:01:12,580
ja inimene, kes oli seal esimene
kes on oodanud juba mõnda aega,

23
00:01:12,580 --> 00:01:14,715
võiks seal olla mitu tundi,
ja tunni ja tunni

24
00:01:14,715 --> 00:01:17,590
enne kui nad on võimalus tegelikult
tühista raha pangas.

25
00:01:17,590 --> 00:01:22,510
Ja nii järjekorrad on omamoodi
õigluse rakendamise struktuur.

26
00:01:22,510 --> 00:01:25,780
Aga see ei tähenda tingimata
et korstnad on halb, lihtsalt

27
00:01:25,780 --> 00:01:28,160
et järjekorrad on üks võimalus seda teha.

28
00:01:28,160 --> 00:01:32,420
Nii jälle järjekord on esimene, esimene
välja, võrreldes virna, mis kestab aasta,

29
00:01:32,420 --> 00:01:34,440
Esimene välja.

30
00:01:34,440 --> 00:01:36,190
Sarnaselt korstna
meil on kaks tegevust

31
00:01:36,190 --> 00:01:38,470
et me ei tegutse järjekorrad.

32
00:01:38,470 --> 00:01:43,910
Nimed on Lisa järjekorda, mida on lisada
uus element lõpuni järjekorda,

33
00:01:43,910 --> 00:01:47,330
ja dequeue, mis on
kustutada vanim

34
00:01:47,330 --> 00:01:49,670
elemendi ees järjekorda.

35
00:01:49,670 --> 00:01:53,600
Nii et me läheme lisada elemente
koridori lõpus järjekorda,

36
00:01:53,600 --> 00:01:57,220
ja me ei kavatse eemaldada elemendid
esiosast järjekorda.

37
00:01:57,220 --> 00:02:00,790
Jällegi on virnas, olime lisades
elemente riidale

38
00:02:00,790 --> 00:02:03,380
ja eemaldamist elemendid
alates ülemisest lehest.

39
00:02:03,380 --> 00:02:07,570
Nii Lisa järjekorda, see on lisades
Lõpuks eemaldamist ees.

40
00:02:07,570 --> 00:02:10,639
Nii vanim asi seal
Alati on järgmine asi

41
00:02:10,639 --> 00:02:13,620
välja tulema, kui me püüame
ja dequeue midagi.

42
00:02:13,620 --> 00:02:18,330
>> Nii jälle koos järjekorrad, saame
massiivi põhinev rakendused

43
00:02:18,330 --> 00:02:20,110
ja seotud põhineva nimekirja rakendusi.

44
00:02:20,110 --> 00:02:24,620
Hakkame jälle
massiivi baasil rakendusi.

45
00:02:24,620 --> 00:02:27,070
Struktuuri määratlemine
tundub päris sarnased.

46
00:02:27,070 --> 00:02:30,720
Meil on veel hulgaliselt
seal andmete tüübi väärtus,

47
00:02:30,720 --> 00:02:32,690
nii et see võib olla meelevaldne andmetüüpe.

48
00:02:32,690 --> 00:02:35,570
Me jälle kavatse kasutada
täisarvud selles näites.

49
00:02:35,570 --> 00:02:39,830
>> Ja just nagu meie
massiivi põhinev stack rakendamist,

50
00:02:39,830 --> 00:02:42,340
sest me oleme kasutades
massiiv, me tingimata

51
00:02:42,340 --> 00:02:46,850
on see piirang, et C tüüpi
ning jõustab meile, mis on meie

52
00:02:46,850 --> 00:02:51,670
ei ole mingit dünaamikat meie
võime kasvada ja kahaneb massiivi.

53
00:02:51,670 --> 00:02:55,710
Peame otsustama alguses
Mis on maksimaalne arv asju

54
00:02:55,710 --> 00:02:59,300
et saame panna selle
järjekorda, ja sel juhul,

55
00:02:59,300 --> 00:03:02,070
võimsus peaks olema mingi nael
määratletud pidevat meie koodi.

56
00:03:02,070 --> 00:03:05,430
Ja Käesolevas
video, võimsus saab olema 10.

57
00:03:05,430 --> 00:03:07,690
>> Meil on vaja jälgida
ees järjekorda

58
00:03:07,690 --> 00:03:11,160
nii et me teame, mis element
tahame dequeue,

59
00:03:11,160 --> 00:03:15,070
ja me peame ka jälgida
midagi else-- elementide arv

60
00:03:15,070 --> 00:03:16,690
et meil on meie järjekorda.

61
00:03:16,690 --> 00:03:19,360
Pange tähele, et me ei jälgimine
lõpu järjekorda, vaid

62
00:03:19,360 --> 00:03:21,150
suuruse järjekorda.

63
00:03:21,150 --> 00:03:24,310
Ja põhjus, et loodetavasti
saada natuke selgem kohe.

64
00:03:24,310 --> 00:03:26,143
Kui oleme valmis
Seda tüüpi määratlust,

65
00:03:26,143 --> 00:03:29,080
meil on uus andmetüüp
nimetatakse järjekorda, mida me saame nüüd

66
00:03:29,080 --> 00:03:30,630
Kinnitan muutujaid, et andmete tüübi.

67
00:03:30,630 --> 00:03:35,350
Ja mõneti eksitavalt, ma olen otsustanud
nimetame seda järjekorda q täht

68
00:03:35,350 --> 00:03:38,090
q asemel andmetüüpi q.

69
00:03:38,090 --> 00:03:39,600
>> Nii et siin on meie järjekorda.

70
00:03:39,600 --> 00:03:40,700
See on struktuur.

71
00:03:40,700 --> 00:03:45,730
See sisaldab kolm liiget või kolm
valdkondades, massiivi suurus võimsust.

72
00:03:45,730 --> 00:03:47,340
Sel juhul võimsus on 10.

73
00:03:47,340 --> 00:03:49,580
Ja see rida on
läheb hoidke täisarvud.

74
00:03:49,580 --> 00:03:55,240
Green on ees meie järjekorda, siis
Järgmine element, mis tuleb eemaldada, ja punane

75
00:03:55,240 --> 00:03:58,610
saab suuruse järjekorras,
kui palju elemente on praegu

76
00:03:58,610 --> 00:04:01,190
olemasolevate järjekorras.

77
00:04:01,190 --> 00:04:05,300
Nii et kui me ütleme q.front võrdsete
0, ja q.size suurus võrdub 0--

78
00:04:05,300 --> 00:04:07,120
me panna 0. neile väljadele.

79
00:04:07,120 --> 00:04:11,070
Ja sel hetkel, me oleme päris palju
valmis alustama tööd oma järjekorda.

80
00:04:11,070 --> 00:04:14,140
>> Nii et esimene operatsioon saame
täita on Lisa järjekorda midagi,

81
00:04:14,140 --> 00:04:16,860
lisada uus element
lõppu järjekorda.

82
00:04:16,860 --> 00:04:19,089
Noh, mida me peame
teha üldise puhul?

83
00:04:19,089 --> 00:04:23,690
Noh see funktsioon Lisa järjekorda vajadustele
aktsepteerima viit meie järjekorda.

84
00:04:23,690 --> 00:04:26,370
Jällegi, kui me oleksime deklareeritud
Meie järjekorda maailmas,

85
00:04:26,370 --> 00:04:29,490
me ei vaja seda teha
tingimata, kuid üldiselt on meil

86
00:04:29,490 --> 00:04:32,330
tuleb leppida viiteid
to andmestruktuuride

87
00:04:32,330 --> 00:04:35,040
niimoodi, sest teisiti,
me mööda value-- me oleme

88
00:04:35,040 --> 00:04:38,140
kulgeb koopiad järjekorda,
ja nii me tegelikult ei muutuvas

89
00:04:38,140 --> 00:04:41,050
järjekorras, et me kavatseme muuta.

90
00:04:41,050 --> 00:04:44,860
>> Teine asi, mida ta vajab, et teha on nõus
andmeelemendis vajalikku tüüpi.

91
00:04:44,860 --> 00:04:46,818
Ka sellisel juhul on see
saab olema täisarvud,

92
00:04:46,818 --> 00:04:49,330
aga sa võiks meelevaldselt
Kinnitan andmete liiki kui väärtus

93
00:04:49,330 --> 00:04:51,160
ja kasutada seda üldisemalt.

94
00:04:51,160 --> 00:04:56,030
See on element tahame Lisa järjekorda,
tahame lisada lõpus järjekorda.

95
00:04:56,030 --> 00:04:58,573
Siis me tegelikult tahame
pange need andmed järjekorda.

96
00:04:58,573 --> 00:05:01,490
Sel juhul pannes selle
õigesse meie massiiv,

97
00:05:01,490 --> 00:05:05,040
ja siis me tahame muuta suurust
järjekorra, kui palju elemente me

98
00:05:05,040 --> 00:05:07,050
praegu on.

99
00:05:07,050 --> 00:05:07,990
>> Nii alustame.

100
00:05:07,990 --> 00:05:10,890
Siin on jällegi, et üldiselt
kujul funktsiooni deklaratsioon

101
00:05:10,890 --> 00:05:13,980
mida Lisa järjekorda tunduda.

102
00:05:13,980 --> 00:05:14,910
Ja siin me läheme.

103
00:05:14,910 --> 00:05:18,335
Olgem Lisa järjekorda arv
28 järjekorda.

104
00:05:18,335 --> 00:05:19,460
Mida me siis teeme?

105
00:05:19,460 --> 00:05:23,390
Noh, ees meie järjekord
temperatuuril 0 ja suurus meie järjekorda

106
00:05:23,390 --> 00:05:29,680
on 0, ja nii me ilmselt tahan panna
arvu 28 massiivi element number

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

108
00:05:31,124 --> 00:05:32,540
Nii et me oleme nüüd panna, et seal.

109
00:05:32,540 --> 00:05:34,820
Nüüd, mida me peame muutma?

110
00:05:34,820 --> 00:05:37,090
Me ei taha, et muuta
ees järjekorras,

111
00:05:37,090 --> 00:05:40,850
sest me tahame teada, milline element
võiks olla vaja dequeue hiljem.

112
00:05:40,850 --> 00:05:44,020
Nii et põhjus on meil ees on
on omamoodi indikaator, mis on

113
00:05:44,020 --> 00:05:46,439
vanimaid asi massiivi.

114
00:05:46,439 --> 00:05:49,730
Noh vanim asi array-- sisse
Tegelikult ainus asi massiivi õigus

115
00:05:49,730 --> 00:05:53,540
now-- on 28, mis on
kell massiivi 0.

116
00:05:53,540 --> 00:05:56,160
Nii et me ei taha
muuta, et roheline number,

117
00:05:56,160 --> 00:05:57,910
sest see on vanim element.

118
00:05:57,910 --> 00:06:00,510
Pigem soovime suurust muuta.

119
00:06:00,510 --> 00:06:04,110
Nii et kui, siis me
juurdekasvu suurus 1.

120
00:06:04,110 --> 00:06:08,430
>> Nüüd üldine omamoodi idee, kus
Järgmine element on minemas järjekorras

121
00:06:08,430 --> 00:06:12,310
on lisada need kaks numbrit
kokku, ees ja suurus,

122
00:06:12,310 --> 00:06:16,390
ja et ütlen teile, kus järgmise
element järjekorras on minemas.

123
00:06:16,390 --> 00:06:18,130
Nüüd oletame Lisa järjekorda teisele numbrile.

124
00:06:18,130 --> 00:06:20,250
Olgem Lisa järjekorda 33.

125
00:06:20,250 --> 00:06:24,480
Nii 33 läheb minema
massiivi asukoha 0 pluss 1.

126
00:06:24,480 --> 00:06:26,840
Nii et sel juhul läheb
minema massiivi asukohta 1

127
00:06:26,840 --> 00:06:29,500
ja nüüd suurus meie järjekord on 2.

128
00:06:29,500 --> 00:06:31,840
>> Jällegi, me ei muutu
ees meie järjekorda,

129
00:06:31,840 --> 00:06:34,730
sest 28 on ikka
Vanim element, ja me

130
00:06:34,730 --> 00:06:38,220
tahan mina-- kui me lõpuks saada
to dequeuing, eemaldades elemendid

131
00:06:38,220 --> 00:06:43,300
Sellest järjekorda, me tahame teada,
kus vanim element on.

132
00:06:43,300 --> 00:06:48,620
Ja nii on meil alati vaja säilitada
mõned näitaja, kui see on.

133
00:06:48,620 --> 00:06:50,410
Nii see on, mida 0 on seal.

134
00:06:50,410 --> 00:06:52,910
Seda ees on seal.

135
00:06:52,910 --> 00:06:55,022
>> Lähme sisse Lisa järjekorda veel üks element, 19.

136
00:06:55,022 --> 00:06:56,980
Ma olen kindel, et te võite arvata
kus 19 on minemas.

137
00:06:56,980 --> 00:06:59,860
See lähe
massiivi asukoha number 2.

138
00:06:59,860 --> 00:07:01,570
Ongi 0 + 2.

139
00:07:01,570 --> 00:07:03,199
Ja nüüd suurus meie järjekord on 3.

140
00:07:03,199 --> 00:07:04,240
Meil on 3 elemente.

141
00:07:04,240 --> 00:07:08,490
Nii et kui me olime, ja me ei kavatse
et just nüüd, Lisa järjekorda teise element,

142
00:07:08,490 --> 00:07:11,370
see läheks massiivi asukohta
number 3 ja suurus meie järjekorda

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

144
00:07:13,160 --> 00:07:15,279
Nii oleme enqueued mitmest elemendist nüüd.

145
00:07:15,279 --> 00:07:16,570
Nüüd alustame nende kõrvaldamiseks.

146
00:07:16,570 --> 00:07:19,450
Olgem dequeue neid järjekorda.

147
00:07:19,450 --> 00:07:23,340
>> Nii sarnaneb pop, mis on omamoodi
analoogsignaali käesoleva virnade,

148
00:07:23,340 --> 00:07:26,180
dequeue peab aktsepteerima
kursor queue-- uuesti,

149
00:07:26,180 --> 00:07:28,140
kui see on ülemaailmselt kuulutatud.

150
00:07:28,140 --> 00:07:31,610
Nüüd tahame asukohta muuta
selle ees järjekorda.

151
00:07:31,610 --> 00:07:35,050
See on koht, kus see omamoodi kaasas
mängu, et ees muutuja,

152
00:07:35,050 --> 00:07:37,310
sest kui me eemaldada
element, me tahame

153
00:07:37,310 --> 00:07:40,720
liikuda selle järgmisele vanim element.

154
00:07:40,720 --> 00:07:44,180
>> Siis me tahame vähendada
suuruse järjekorras,

155
00:07:44,180 --> 00:07:47,130
ja siis me tahame naasta väärtus
mis eemaldati järjekorda.

156
00:07:47,130 --> 00:07:48,921
Jällegi, me ei taha lihtsalt loobuda.

157
00:07:48,921 --> 00:07:51,170
Me ilmselt ei kaevandavad
see alates queue-- me oleme

158
00:07:51,170 --> 00:07:54,170
dequeuing, sest me hoolime sellest.

159
00:07:54,170 --> 00:08:01,080
Nii et me tahame seda funktsiooni tagasi
andmeelemendis tüüpi väärtuse.

160
00:08:01,080 --> 00:08:04,360
Ka sellisel juhul väärtus ei täisarv.

161
00:08:04,360 --> 00:08:05,670
>> Vaatame nüüd dequeue midagi.

162
00:08:05,670 --> 00:08:09,310
Olgem mõne elemendi eemaldamiseks järjekorda.

163
00:08:09,310 --> 00:08:15,970
Kui me ütleme, int x võrdub & q, ampersand q--
jälle see kursor sellele q andmeid

164
00:08:15,970 --> 00:08:20,177
structure-- mida element
läheb dequeued?

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

166
00:08:23,840 --> 00:08:29,480
Sel juhul, kuna see on esimene
aastal, esimene välja andmestruktuur, FIFO,

167
00:08:29,480 --> 00:08:33,690
esimene asi, mida me panna see
järjekorras oli 28, ja nii sel juhul,

168
00:08:33,690 --> 00:08:37,245
me läheme 28 välja
järjekorras, mitte 19, mis on see, mida

169
00:08:37,245 --> 00:08:38,870
me oleks teinud, kui see oli pakk.

170
00:08:38,870 --> 00:08:42,220
Me läheme 28 out of järjekorda.

171
00:08:42,220 --> 00:08:44,960
>> Sarnaselt mida tegime
virna, me ei ole tegelikult

172
00:08:44,960 --> 00:08:47,345
kustutamas 28
järjekorrast ise,

173
00:08:47,345 --> 00:08:49,470
me lihtsalt läheb selline
on teeselda seda seal ei ole.

174
00:08:49,470 --> 00:08:51,678
Nii see läheb sinna jääda
mälu, kuid me oleme lihtsalt

175
00:08:51,678 --> 00:08:57,820
läheb selline ignoreerida liigutades
Teised kaks suunda meie q andmeid

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

177
00:08:58,830 --> 00:09:00,230
Me läheme muuta ees.

178
00:09:00,230 --> 00:09:04,290
Q.front nüüd lähen
olla 1, sest see on nüüd

179
00:09:04,290 --> 00:09:07,740
vanim element oleme meie
järjekorda, sest me oleme juba eemaldatud 28,

180
00:09:07,740 --> 00:09:10,460
mis oli endise vanim element.

181
00:09:10,460 --> 00:09:13,540
>> Ja nüüd, me tahame muuta
suuruse järjekorras

182
00:09:13,540 --> 00:09:15,780
kahest osast kolme asemel.

183
00:09:15,780 --> 00:09:20,450
Nüüd mäletan varem ütlesin, kui me
tahan lisada elemente järjekorda,

184
00:09:20,450 --> 00:09:26,000
paneme selle massiivi asukohta
mis on summa ees ja suurus.

185
00:09:26,000 --> 00:09:29,050
Nii et kui me ikka panna
see, järgmise elemendi järjekorras,

186
00:09:29,050 --> 00:09:33,360
arvesse massiivi asukohast 3, ja
Me näeme, et teist.

187
00:09:33,360 --> 00:09:35,730
>> Nii et me oleme nüüd dequeued meie
Esimene element järjekorrast.

188
00:09:35,730 --> 00:09:36,480
Teeme seda uuesti.

189
00:09:36,480 --> 00:09:38,696
Olgem eemaldada teise
element järjekorrast.

190
00:09:38,696 --> 00:09:42,400
Juhul, praegune vanim
element on hulgaliselt kohale 1.

191
00:09:42,400 --> 00:09:44,220
Seda q.front ütleb.

192
00:09:44,220 --> 00:09:46,980
See roheline kast ütleb meile, et
see on vanim element.

193
00:09:46,980 --> 00:09:49,310
Ja nii, x muutub 33.

194
00:09:49,310 --> 00:09:52,130
Me lihtsalt selline unustada
et 33 on olemas massiiv,

195
00:09:52,130 --> 00:09:55,100
ja me öelda, et nüüd on
Uue vanim element järjekorras

196
00:09:55,100 --> 00:09:58,900
on massiivi asukoha 2 ja suurus
järjekorra, elementide arv

197
00:09:58,900 --> 00:10:02,152
meil sabas, on 1.

198
00:10:02,152 --> 00:10:05,110
Nüüd Lisa järjekorda midagi, ja ma
omamoodi andis selle ära teise tagasi

199
00:10:05,110 --> 00:10:10,340
aga kui me tahame panna 40 sisse
järjekorda, kus on 40 kavatse minna?

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

201
00:10:12,880 --> 00:10:17,730
Noh me oleme hakanud seda
in q.front pluss järjekorda suurus,

202
00:10:17,730 --> 00:10:20,850
ja nii on mõistlik
tegelikult panna 40 siin.

203
00:10:20,850 --> 00:10:22,840
Nüüd märkate, et
Mingil hetkel, me ei kavatse

204
00:10:22,840 --> 00:10:27,980
saada lõpuks
meie massiivi sees q,

205
00:10:27,980 --> 00:10:32,010
kuid pleekinud välja 28 ja 33--
nad tegelikult tehniliselt

206
00:10:32,010 --> 00:10:33,300
avatud ruumi, eks?

207
00:10:33,300 --> 00:10:36,040
Ja nii me eventually--
Selle reegli lisamise

208
00:10:36,040 --> 00:10:40,390
Nende kahe together-- meil võib lõpuks
vaja mod suurusest võimsusega

209
00:10:40,390 --> 00:10:41,410
et saaksime ümbritsev.

210
00:10:41,410 --> 00:10:43,620
>> Nii et kui me saame element
number 10, kui me oleme

211
00:10:43,620 --> 00:10:48,790
asendades selle elemendi number 10, olime
tegelikult panin selle massiivi 0.

212
00:10:48,790 --> 00:10:50,997
Ja kui me ei kavatse
massiivi location-- vabandage,

213
00:10:50,997 --> 00:10:53,080
kui lisasime neid koos,
ja saime number

214
00:10:53,080 --> 00:10:56,330
11 oleks, kui meil oleks panna
see, mida ei eksisteeri selles array--

215
00:10:56,330 --> 00:10:58,200
see läheb auti.

216
00:10:58,200 --> 00:11:03,367
Võiksime mod 10 ja panna
see massiiv asukohta 1.

217
00:11:03,367 --> 00:11:04,450
Nii see on, kuidas järjekorrad tööta.

218
00:11:04,450 --> 00:11:08,540
Nad alati saab minna vasakule
paremale ja võimalusel ümbritsev.

219
00:11:08,540 --> 00:11:11,280
Ja sa tead, et nad on
täis kui suurus, mis punase kasti,

220
00:11:11,280 --> 00:11:13,710
muutub võrdne võimsus.

221
00:11:13,710 --> 00:11:16,720
Ja nii pärast oleme lisanud 40 kuni
järjekorda, hästi, mida me peame tegema?

222
00:11:16,720 --> 00:11:19,890
Noh, vanim element
Järjekorras on veel 19,

223
00:11:19,890 --> 00:11:21,990
nii et me ei taha muuta
ees järjekorras,

224
00:11:21,990 --> 00:11:23,820
kuid nüüd on meil kaks
elementide järjekorda,

225
00:11:23,820 --> 00:11:28,710
ja nii me tahame suurendada
meie suuruste 1-2.

226
00:11:28,710 --> 00:11:31,820
>> See on päris palju seda
töötavad massiivi põhinev järjekorrad

227
00:11:31,820 --> 00:11:33,630
jms korstnat,
seal on ka viis

228
00:11:33,630 --> 00:11:36,450
rakendada järjekorda ahelloend.

229
00:11:36,450 --> 00:11:40,150
Nüüd, kui need andmed struktuuritüüpidest
tundub tuttav, siis on.

230
00:11:40,150 --> 00:11:43,780
See ei ole üksi seotud nimekirja,
see on kahekordselt seotud nimekirja.

231
00:11:43,780 --> 00:11:46,790
Ja nüüd, kui kõrvale on
tegelikult võimalik rakendada

232
00:11:46,790 --> 00:11:50,160
järjekorras kui üksikult seotud nimekirja, kuid
Ma arvan, et nii visualiseerimine,

233
00:11:50,160 --> 00:11:53,350
tegelikult võib aidata näha
seda kui kahekordselt seotud nimekirja.

234
00:11:53,350 --> 00:11:56,850
Aga see on kindlasti võimalik
seda teha nii ühekaupa seotud nimekirja.

235
00:11:56,850 --> 00:12:00,110
>> Nii saab tutvuda
mida see tunduda.

236
00:12:00,110 --> 00:12:02,750
Kui me tahame enquue--
nii et nüüd jälle oleme

237
00:12:02,750 --> 00:12:05,360
üleminek on seotud nimekiri
mudelit siin.

238
00:12:05,360 --> 00:12:08,420
Kui me tahame Lisa järjekorda, me tahame
lisada uus element, samuti

239
00:12:08,420 --> 00:12:09,730
Mida me peame tegema?

240
00:12:09,730 --> 00:12:12,770
Well, kõigepealt sellepärast
lisame lõpuni

241
00:12:12,770 --> 00:12:15,520
ja eemaldamist
Alguses me ilmselt

242
00:12:15,520 --> 00:12:20,050
tahame säilitada viiteid nii
pea ja saba seotud nimekirja?

243
00:12:20,050 --> 00:12:22,660
Saba on teine ​​termin
lõppu ahelloendid,

244
00:12:22,660 --> 00:12:24,496
Viimase element seotud nimekirja.

245
00:12:24,496 --> 00:12:26,620
Ja need ilmselt,
jälle olla kasulik meile

246
00:12:26,620 --> 00:12:28,477
kui nad on globaalmuutujad.

247
00:12:28,477 --> 00:12:31,060
Aga nüüd, kui me tahame, et lisada uus
element, mida me peame tegema?

248
00:12:31,060 --> 00:12:35,262
Mida me lihtsalt [? malak?] või dünaamiliselt
eraldada meie uus sõlm ise.

249
00:12:35,262 --> 00:12:38,220
Ja siis, just nagu siis, kui me lisada
element kahekordselt ahelloendid me,

250
00:12:38,220 --> 00:12:40,410
lihtsalt sorteerida of--
need viimased kolm sammud siin

251
00:12:40,410 --> 00:12:43,330
on lihtsalt kõike liigutades
osuti on õigesti

252
00:12:43,330 --> 00:12:46,710
nii et element saab lisada
kett lõhkumata kett

253
00:12:46,710 --> 00:12:49,580
või teha mingi viga
või on mingi õnnetus

254
00:12:49,580 --> 00:12:54,505
juhtuda, millega me kogemata
harva mõned elemendid meie järjekorda.

255
00:12:54,505 --> 00:12:55,880
Siin on, mida see võib tunduda.

256
00:12:55,880 --> 00:13:00,980
Me tahame, et lisada element
10 lõpuni seda järjekorda.

257
00:13:00,980 --> 00:13:03,380
Nii vanim element siin
on esindatud pea.

258
00:13:03,380 --> 00:13:06,800
See on esimene asi, mida me panna
sellesse hüpoteetiline järjekorda siin.

259
00:13:06,800 --> 00:13:10,430
Ja saba, 13, on kõige
viimati lisatud element.

260
00:13:10,430 --> 00:13:17,030
Ja kui me tahame Lisa järjekorda 10 sisse
Selles järjekorras, me tahame panna selle pärast 13.

261
00:13:17,030 --> 00:13:19,860
Ja nii me läheme dünaamiliselt
eraldada ruumi uue tipu

262
00:13:19,860 --> 00:13:23,280
ja kontrollida null veenduda
meil ei ole mälu rike.

263
00:13:23,280 --> 00:13:27,040
Siis me ei kavatse
pane 10 sinna sõlme,

264
00:13:27,040 --> 00:13:30,030
ja nüüd me peame olema ettevaatlikud
kuidas me korraldame viiteid

265
00:13:30,030 --> 00:13:32,180
nii et me ei riku kett.

266
00:13:32,180 --> 00:13:38,910
>> Meil on võimalik valida 10 eelmise valdkonnas
punkti tagasi vana saba,

267
00:13:38,910 --> 00:13:41,620
ja kuna '10 saab
uue saba mingil hetkel

268
00:13:41,620 --> 00:13:44,459
selleks ajaks kõik need
ketid on ühendatud,

269
00:13:44,459 --> 00:13:46,250
midagi on tulemas
Pärast 10 kohe.

270
00:13:46,250 --> 00:13:49,880
Ja nii 10 järgmise pointer
toob välja tühjaks,

271
00:13:49,880 --> 00:13:53,580
ja siis pärast me seda teeme, kui me oleme
ühendatud 10 tahapoole kett,

272
00:13:53,580 --> 00:13:57,780
saame vana head, või, vabandust
mind, vana saba järjekorda.

273
00:13:57,780 --> 00:14:02,980
Vana lõpus järjekorda,
13, ja teha seda punkti 10.

274
00:14:02,980 --> 00:14:08,220
Ja nüüd, sel hetkel, on meil
enqueued arv 10 sellesse järjekorda.

275
00:14:08,220 --> 00:14:14,740
Kõik me peame tegema nüüd on siis liiguta
saba punkti 10 asemel 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing on tegelikult
väga sarnane popping

277
00:14:17,630 --> 00:14:21,710
korstnatest, mis on
rakendatakse ahelloend

278
00:14:21,710 --> 00:14:24,040
Kui olete näinud korstnad video.

279
00:14:24,040 --> 00:14:27,280
Kõik me peame tegema, on alustada juures
hakanud, leida teine ​​element,

280
00:14:27,280 --> 00:14:30,480
tasuta esimene element,
ja seejärel liikuda juht

281
00:14:30,480 --> 00:14:32,930
osutada teine ​​element.

282
00:14:32,930 --> 00:14:37,920
Tõenäoliselt parem visualiseerida seda
lihtsalt olla eriti selge see.

283
00:14:37,920 --> 00:14:39,230
Nii et siin on meie järjekorda uuesti.

284
00:14:39,230 --> 00:14:42,600
12 on vanim element
meie järjekorda juht.

285
00:14:42,600 --> 00:14:46,210
10 on uusim element
meie järjekorda, meie saba.

286
00:14:46,210 --> 00:14:49,310
>> Ja nii, kui me tahame
to dequeue element,

287
00:14:49,310 --> 00:14:52,202
Me tahame, et eemaldada vanim element.

288
00:14:52,202 --> 00:14:52,910
Mida me siis teeme?

289
00:14:52,910 --> 00:14:55,243
Noh seadsime läbipääsusüsteemid pointer
mis algab pea,

290
00:14:55,243 --> 00:14:57,840
ja me liikuda nii, et see
juhib teise elemendi

291
00:14:57,840 --> 00:15:02,290
Selle queue-- midagi öelda trav
võrdub trav noolt, näiteks

292
00:15:02,290 --> 00:15:07,170
oleks liikuda trav seal käsk
15, mis pärast me dequeue 12,

293
00:15:07,170 --> 00:15:13,030
või pärast me eemaldada 12, tahe
saada siis vanim element.

294
00:15:13,030 --> 00:15:16,360
>> Nüüd on meil kinni esimene
element kaudu pointer juht

295
00:15:16,360 --> 00:15:19,440
ja teine ​​element
kaudu pointer matk.

296
00:15:19,440 --> 00:15:25,170
Nüüd on võimalik tasuta peas, ja siis saame
Rääkimata tuleb enne 15 enam.

297
00:15:25,170 --> 00:15:29,990
Nii saame muuta 15 senine
kursor punkti tühjaks,

298
00:15:29,990 --> 00:15:31,874
ja me lihtsalt liigutada pea üle.

299
00:15:31,874 --> 00:15:32,540
Ja me läheme.

300
00:15:32,540 --> 00:15:35,840
Nüüd on meil edukalt
dequeued 12, ja nüüd me

301
00:15:35,840 --> 00:15:39,180
on teise järjekorda 4 elementi.

302
00:15:39,180 --> 00:15:41,700
See on päris palju kõik
seal on järjekorrad,

303
00:15:41,700 --> 00:15:45,810
nii massiivi põhinev ja seotud põhineva nimekirja.

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

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

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