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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Takže, ak ste
sledoval video na zásobníku,

3
00:00:07,370 --> 00:00:09,870
je to pravdepodobne bude cítiť
ako trochou déjà vu.

4
00:00:09,870 --> 00:00:13,850
Bude to veľmi podobným konceptom,
len s miernym twist na to.

5
00:00:13,850 --> 00:00:15,530
Budeme hovoriť teraz o frontoch.

6
00:00:15,530 --> 00:00:19,350
Takže front, podobne ako zásobníka,
je ďalší druh dátové štruktúry

7
00:00:19,350 --> 00:00:22,412
že môžeme použiť na udržanie
Dáta v organizovaným spôsobom.

8
00:00:22,412 --> 00:00:24,120
Podobne ako stack,
aby mohol byť zavedený

9
00:00:24,120 --> 00:00:27,000
ako pole alebo prepojenom zoznamu.

10
00:00:27,000 --> 00:00:30,320
Na rozdiel od zásobníka, pravidlá
že sme sa použiť na určenie

11
00:00:30,320 --> 00:00:34,210
keď sa veci dostať pridané a odstránený z
front je trochu inak.

12
00:00:34,210 --> 00:00:36,590
>> Na rozdiel od stohu, ktorý je
je štruktúra LIFO,

13
00:00:36,590 --> 00:00:45,610
posledný dnu, prvý von, front je FIFO
Štruktúra, FIFO, prvý dovnútra, prvý von.

14
00:00:45,610 --> 00:00:49,320
Teraz fronty, budete pravdepodobne
majú analógiu k front.

15
00:00:49,320 --> 00:00:52,820
Ak ste niekedy boli v rade na
zábavný park, alebo v banke,

16
00:00:52,820 --> 00:00:56,430
je tu akýsi spravodlivosti
vykonávacie štruktúru.

17
00:00:56,430 --> 00:00:59,160
Prvá osoba vo fronte u
banka je prvou osobou,

18
00:00:59,160 --> 00:01:00,760
kto dostane hovoriť s prepážke.

19
00:01:00,760 --> 00:01:03,522
>> Bolo by to akýsi závod
do spodnej časti v prípade, že jediným spôsobom, ako

20
00:01:03,522 --> 00:01:06,730
musíš hovoriť s Teller At The
Banka mala byť posledná, kto v rade.

21
00:01:06,730 --> 00:01:09,146
Každý by vždycky chcú
byť posledný, kto v rade,

22
00:01:09,146 --> 00:01:12,580
a osoba, ktorá tam bol ako prvý
ktorý bol čakal na chvíľu,

23
00:01:12,580 --> 00:01:14,715
by mohlo byť celé hodiny,
a hodiny a hodiny

24
00:01:14,715 --> 00:01:17,590
pred tým, než majú šancu skutočne
stiahnuť nejaké peniaze v banke.

25
00:01:17,590 --> 00:01:22,510
A tak fronty sú hornín
spravodlivosť vykonávacie štruktúru.

26
00:01:22,510 --> 00:01:25,780
Ale to nemusí nutne znamenať,
že komíny sú zlá vec, len

27
00:01:25,780 --> 00:01:28,160
že fronty sú ďalším spôsobom, ako to urobiť.

28
00:01:28,160 --> 00:01:32,420
Takže opäť frontu je prvý, najprv
out, proti stohu, ktorý ako posledný,

29
00:01:32,420 --> 00:01:34,440
first out.

30
00:01:34,440 --> 00:01:36,190
Podobne ako stack,
Máme dve operácie

31
00:01:36,190 --> 00:01:38,470
že môžeme hrať na frontoch.

32
00:01:38,470 --> 00:01:43,910
Mená sú Enqueue, čo je pridanie
nový prvok na koniec frontu,

33
00:01:43,910 --> 00:01:47,330
a dequeue, ktorý je
na odstránenie najstaršie

34
00:01:47,330 --> 00:01:49,670
element z frontu.

35
00:01:49,670 --> 00:01:53,600
Takže budeme pridávať prvky
na konci fronty,

36
00:01:53,600 --> 00:01:57,220
a budeme odstrániť prvky
z frontu.

37
00:01:57,220 --> 00:02:00,790
Opäť platí, že sa v zásobníku, sme pridávali
prvky na vrchol stohu

38
00:02:00,790 --> 00:02:03,380
a odoberanie prvkov
z vrcholu zásobníka.

39
00:02:03,380 --> 00:02:07,570
Tak s Zaradí, je to pridaním
koniec, vybratí z prednej strany.

40
00:02:07,570 --> 00:02:10,639
A tak najstarší vec v tú
je vždy ďalšia vec,

41
00:02:10,639 --> 00:02:13,620
vyjsť von, keď sa pokúsime
a dequeue niečo.

42
00:02:13,620 --> 00:02:18,330
>> Takže znova, s frontami, môžeme
implementácia založená na poli

43
00:02:18,330 --> 00:02:20,110
a spojený-list na základe implementácie.

44
00:02:20,110 --> 00:02:24,620
Začneme znovu s
implementácia založená na poli.

45
00:02:24,620 --> 00:02:27,070
Definícia štruktúra
Vyzerá dosť podobné.

46
00:02:27,070 --> 00:02:30,720
Máme ďalšie pole
tam typu dátové hodnoty,

47
00:02:30,720 --> 00:02:32,690
takže to môže držať ľubovoľné dátové typy.

48
00:02:32,690 --> 00:02:35,570
Máme ísť znova na použitie
celé čísla v tomto príklade.

49
00:02:35,570 --> 00:02:39,830
>> A rovnako ako s našimi
Implementácia zásobníka založená na poli,

50
00:02:39,830 --> 00:02:42,340
preto, že sme za použitia
poľa, sme nutne

51
00:02:42,340 --> 00:02:46,850
má toto obmedzenie, že C druh
z vynucuje na nás, čo je, že sme

52
00:02:46,850 --> 00:02:51,670
nemajú žiadnu dynamiku v našej
schopnosť rásť a zmenšiť pole.

53
00:02:51,670 --> 00:02:55,710
Musíme sa rozhodnúť, na začiatku
aká je maximálny počet vecí

54
00:02:55,710 --> 00:02:59,300
že môžeme dať do toho
front, a v tomto prípade,

55
00:02:59,300 --> 00:03:02,070
kapacita by mala byť asi libra
definovaná konštantou nášho kódu.

56
00:03:02,070 --> 00:03:05,430
A na účely tohto
video, kapacita bude 10.

57
00:03:05,430 --> 00:03:07,690
>> Musíme sledovať
predné fronty

58
00:03:07,690 --> 00:03:11,160
takže vieme, ktoré element
chceme dequeue,

59
00:03:11,160 --> 00:03:15,070
a musíme tiež sledovať
niečo else-- počet prvkov

60
00:03:15,070 --> 00:03:16,690
že máme v našej fronte.

61
00:03:16,690 --> 00:03:19,360
Všimnite si, nie sme sledovanie
na konci fronty, len

62
00:03:19,360 --> 00:03:21,150
veľkosť fronty.

63
00:03:21,150 --> 00:03:24,310
A dôvod pre to, dúfajme,
stať sa trochu jasnejšie za chvíľu.

64
00:03:24,310 --> 00:03:26,143
Potom, čo sme dokončili
táto definícia typu,

65
00:03:26,143 --> 00:03:29,080
máme nový dátový typ
volal fronta, ktorú môžeme teraz

66
00:03:29,080 --> 00:03:30,630
deklarovať premenné tohto typu dát.

67
00:03:30,630 --> 00:03:35,350
A trochu mätúci, rozhodol som sa
volať tento fronty Q, písmeno

68
00:03:35,350 --> 00:03:38,090
Q namiesto dátového typu q.

69
00:03:38,090 --> 00:03:39,600
>> Takže tu je naša fronta.

70
00:03:39,600 --> 00:03:40,700
Jedná sa o štruktúru.

71
00:03:40,700 --> 00:03:45,730
Obsahuje tri členmi alebo tri
pole, pole kapacity veľkosti.

72
00:03:45,730 --> 00:03:47,340
V tomto prípade, kapacita je 10.

73
00:03:47,340 --> 00:03:49,580
A toto pole je
bude držať celé čísla.

74
00:03:49,580 --> 00:03:55,240
V zelenom je predná časť našej frontu,
Ďalším prvkom, ktorý bude odobratý, a v červenej

75
00:03:55,240 --> 00:03:58,610
bude veľkosť frontu,
koľko prvky sú v súčasnej dobe

76
00:03:58,610 --> 00:04:01,190
existujúci vo fronte.

77
00:04:01,190 --> 00:04:05,300
Takže keď povieme q.front rovní
0, a veľkosť q.size rovná 0--

78
00:04:05,300 --> 00:04:07,120
Dávame 0s do týchto polí.

79
00:04:07,120 --> 00:04:11,070
A v tomto bode, sme celkom veľa
pripravení začať pracovať s naším fronty.

80
00:04:11,070 --> 00:04:14,140
>> Takže prvé operácie môžeme
vykonajte je Zaradí niečo,

81
00:04:14,140 --> 00:04:16,860
pridať nový prvok
koniec fronty.

82
00:04:16,860 --> 00:04:19,089
No čo potrebujeme
robiť vo všeobecnom prípade?

83
00:04:19,089 --> 00:04:23,690
No to funkcia Zaradí potreby
na prijatie ukazovateľa na našej fronty.

84
00:04:23,690 --> 00:04:26,370
Opäť platí, že ak by sme vyhlásil
naše front globálne,

85
00:04:26,370 --> 00:04:29,490
nebudeme potrebovať to urobiť
nutne, ale všeobecne, sme

86
00:04:29,490 --> 00:04:32,330
je potrebné prijať ukazovatele
do dátových štruktúr

87
00:04:32,330 --> 00:04:35,040
ako je tento, pretože inak,
sme okolo value-- sme

88
00:04:35,040 --> 00:04:38,140
odovzdaním kópie fronte,
a preto nie sme skutočne mení,

89
00:04:38,140 --> 00:04:41,050
fronta, že máme v úmysle zmeniť.

90
00:04:41,050 --> 00:04:44,860
>> Ďalšia vec, ktorú treba urobiť, je prijať
dátový prvok príslušného typu.

91
00:04:44,860 --> 00:04:46,818
Opäť platí, že v tomto prípade je to
bude celé čísla,

92
00:04:46,818 --> 00:04:49,330
ale môžete ľubovoľne
deklarovať dátový typ ako hodnotu

93
00:04:49,330 --> 00:04:51,160
a použiť všeobecnejšie.

94
00:04:51,160 --> 00:04:56,030
To je prvok, chceme Zaradí,
chceme pridať na koniec fronty.

95
00:04:56,030 --> 00:04:58,573
Potom sme sa skutočne chcú
umiestniť tieto dáta vo fronte.

96
00:04:58,573 --> 00:05:01,490
V tomto prípade, umiestnenie do
Správne umiestnenie nášho poľa,

97
00:05:01,490 --> 00:05:05,040
a potom chceme zmeniť veľkosť
frontu, koľko prvkov sme

98
00:05:05,040 --> 00:05:07,050
V súčasnej dobe máme.

99
00:05:07,050 --> 00:05:07,990
>> Tak poďme začať.

100
00:05:07,990 --> 00:05:10,890
Tu je, opäť, že všeobecná
deklarácia funkcie forma

101
00:05:10,890 --> 00:05:13,980
za to, čo Enqueue by mohol vyzerať.

102
00:05:13,980 --> 00:05:14,910
A je to tu.

103
00:05:14,910 --> 00:05:18,335
Poďme Zaradí číslo
28 do fronty.

104
00:05:18,335 --> 00:05:19,460
Tak čo budeme robiť?

105
00:05:19,460 --> 00:05:23,390
No, pred našou fronte
pri 0 ° C, a veľkosti nášho fronty

106
00:05:23,390 --> 00:05:29,680
je 0, a tak sme asi chcete dať
číslo 28 v poli číslo prvku

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

108
00:05:31,124 --> 00:05:32,540
Takže sme teraz umiestnené tak, aby sa tam.

109
00:05:32,540 --> 00:05:34,820
Takže teraz čo musíme zmeniť?

110
00:05:34,820 --> 00:05:37,090
Nechceme meniť
predné frontu,

111
00:05:37,090 --> 00:05:40,850
pretože chceme vedieť, aký prvok
by sme mohli potrebovať, aby dequeue neskôr.

112
00:05:40,850 --> 00:05:44,020
Takže dôvod, prečo sme tam front
je akýmsi ukazovateľom toho, čo je

113
00:05:44,020 --> 00:05:46,439
najstaršia vec na poli.

114
00:05:46,439 --> 00:05:49,730
No najstaršia vec na array-- v
Skutočnosť, jediná vec, v poli vpravo

115
00:05:49,730 --> 00:05:53,540
now-- je 28, ktorý je
v mieste poľa 0.

116
00:05:53,540 --> 00:05:56,160
Takže nechceme, aby
zmeniť túto zelenú linku,

117
00:05:56,160 --> 00:05:57,910
pretože to je najstarší element.

118
00:05:57,910 --> 00:06:00,510
Skôr chceme zmeniť veľkosť.

119
00:06:00,510 --> 00:06:04,110
Takže v tomto prípade, budeme
zvýšiť veľkosť na 1.

120
00:06:04,110 --> 00:06:08,430
>> Teraz všeobecný akúsi myšlienkou, kde sa
ďalší prvok sa chystá ísť vo fronte

121
00:06:08,430 --> 00:06:12,310
je pridať týchto dvoch čísel
spolu, predné a veľkosť,

122
00:06:12,310 --> 00:06:16,390
a že ťa kde rozprávať ďalšie
prvok vo fronte sa chystá ísť.

123
00:06:16,390 --> 00:06:18,130
Takže teraz poďme Zaradí iné číslo.

124
00:06:18,130 --> 00:06:20,250
Poďme Zaradí 33.

125
00:06:20,250 --> 00:06:24,480
Takže 33 sa chystá ísť do
Poloha poľa 0 a 1.

126
00:06:24,480 --> 00:06:26,840
Takže v tomto prípade, bude to
ísť do umiestnenia poľa 1,

127
00:06:26,840 --> 00:06:29,500
a teraz veľkosť našej frontu je 2.

128
00:06:29,500 --> 00:06:31,840
>> Opäť platí, že nie sme mení
predná časť našej frontu,

129
00:06:31,840 --> 00:06:34,730
28, pretože je stále
najstarší element, a my

130
00:06:34,730 --> 00:06:38,220
Ak to-- keď sa nakoniec dostal
na dequeuing, odoberanie prvkov

131
00:06:38,220 --> 00:06:43,300
z tejto fronty, chceme vedieť
kde je najstarší element.

132
00:06:43,300 --> 00:06:48,620
A tak sme vždy je potrebné zachovať
niektoré ukazovateľ, kde to je.

133
00:06:48,620 --> 00:06:50,410
Takže to je to, čo je tu pre 0.

134
00:06:50,410 --> 00:06:52,910
To je to, čo prednej strane je tam.

135
00:06:52,910 --> 00:06:55,022
>> Poďme v Zaradí ešte jeden prvok, 19.

136
00:06:55,022 --> 00:06:56,980
Som si istý, môžete hádať,
kde 19 sa chystá ísť.

137
00:06:56,980 --> 00:06:59,860
Bude to ísť do
poľa číslo umiestnenia 2.

138
00:06:59,860 --> 00:07:01,570
To je 0 a 2.

139
00:07:01,570 --> 00:07:03,199
A teraz je veľkosť našej frontu je 3.

140
00:07:03,199 --> 00:07:04,240
Máme 3 elementy v tom.

141
00:07:04,240 --> 00:07:08,490
Takže ak sme mali, a nebudeme
práve teraz, Zaradí ďalší prvok,

142
00:07:08,490 --> 00:07:11,370
to by ísť do miesta poľa
číslo 3, a veľkosť našej fronty

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

144
00:07:13,160 --> 00:07:15,279
Preto sme enqueued niekoľko prvkov teraz.

145
00:07:15,279 --> 00:07:16,570
Teraz začnime na ich odstránenie.

146
00:07:16,570 --> 00:07:19,450
Poďme dequeue z frontu.

147
00:07:19,450 --> 00:07:23,340
>> Takže podobne ako pop, ktorý je trochu
analógu tohto pre komíny,

148
00:07:23,340 --> 00:07:26,180
dequeue treba akceptovať
Ukazovateľ na queue-- znovu

149
00:07:26,180 --> 00:07:28,140
ak je to v celosvetovom meradle deklarovaná.

150
00:07:28,140 --> 00:07:31,610
Teraz chceme zmeniť umiestnenie
z frontu.

151
00:07:31,610 --> 00:07:35,050
To je miesto, kde to tak nejako príde
do hry, že predné variabilné,

152
00:07:35,050 --> 00:07:37,310
pretože akonáhle sme sa odstrániť
prvok, chceme

153
00:07:37,310 --> 00:07:40,720
presunúť do ďalšieho najstarší prvok.

154
00:07:40,720 --> 00:07:44,180
>> Potom chceme znížiť
veľkosť frontu,

155
00:07:44,180 --> 00:07:47,130
a potom sme sa chcete vrátiť hodnotu
, Ktorý bol odobratý z frontu.

156
00:07:47,130 --> 00:07:48,921
Opäť platí, že nechceme, aby jednoducho odhodiť to.

157
00:07:48,921 --> 00:07:51,170
Sme pravdepodobne extrahujete
to z queue-- ktorom sme

158
00:07:51,170 --> 00:07:54,170
dequeuing to, pretože nám záleží na tom.

159
00:07:54,170 --> 00:08:01,080
Takže chceme, aby táto funkcia sa vrátiť
dátový prvok typu hodnoty.

160
00:08:01,080 --> 00:08:04,360
Opäť platí, že v tomto prípade, že hodnota je celé číslo.

161
00:08:04,360 --> 00:08:05,670
>> Takže teraz poďme dequeue niečo.

162
00:08:05,670 --> 00:08:09,310
Poďme odstrániť prvok z fronty.

163
00:08:09,310 --> 00:08:15,970
Ak hovoríme, int x rovná & q, ampersand q--
Znovu to je ukazovateľ na tento q dát

164
00:08:15,970 --> 00:08:20,177
structure-- čo element
sa bude dequeued?

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

166
00:08:23,840 --> 00:08:29,480
V tomto prípade, pretože sa jedná o prvom
in, first out dátové štruktúry, FIFO,

167
00:08:29,480 --> 00:08:33,690
Prvá vec, ktorú sme sa dať do toho
fronta bola 28, a teda v tomto prípade,

168
00:08:33,690 --> 00:08:37,245
budeme brať 28 z
frontu, nie 19, ktorý je čo

169
00:08:37,245 --> 00:08:38,870
by sme urobili, či to bola hromada.

170
00:08:38,870 --> 00:08:42,220
Chystáme sa prijať 28 z frontu.

171
00:08:42,220 --> 00:08:44,960
>> Podobne k tomu, čo sme to urobili s
stoh, nie sme v skutočnosti

172
00:08:44,960 --> 00:08:47,345
chystá vymazať 28
z frontu samotnej,

173
00:08:47,345 --> 00:08:49,470
my len tak druhu
z predstierať, že tam nie je.

174
00:08:49,470 --> 00:08:51,678
Takže to bude tam zostať
v pamäti, ale my sme jednoducho

175
00:08:51,678 --> 00:08:57,820
bude druh ignorovať pohybom
ďalšie dve polia našej q dát

176
00:08:57,820 --> 00:08:58,830
štruktúra.

177
00:08:58,830 --> 00:09:00,230
Chystáme sa zmeniť front.

178
00:09:00,230 --> 00:09:04,290
Q.front sa teraz chystá
byť 1, pretože to je teraz

179
00:09:04,290 --> 00:09:07,740
najstarší prvok máme v našej
front, pretože sme už odstránené 28,

180
00:09:07,740 --> 00:09:10,460
čo bol bývalý najstarší element.

181
00:09:10,460 --> 00:09:13,540
>> A teraz, chceme zmeniť
veľkosť fronty

182
00:09:13,540 --> 00:09:15,780
na dva prvky namiesto troch.

183
00:09:15,780 --> 00:09:20,450
Teraz pamätať predtým som povedal, keď sme
Chcete pridať prvky do fronty,

184
00:09:20,450 --> 00:09:26,000
dáme to v mieste poľa
ktorý je súčtom predné a veľkosti.

185
00:09:26,000 --> 00:09:29,050
Takže v tomto prípade, sme stále uvedenie
to, ďalší element vo fronte,

186
00:09:29,050 --> 00:09:33,360
do umiestnenia poľa 3, a
budeme vidieť, že v druhom.

187
00:09:33,360 --> 00:09:35,730
>> Preto sme teraz naše dequeued
Prvý element z frontu.

188
00:09:35,730 --> 00:09:36,480
Urobme to znova.

189
00:09:36,480 --> 00:09:38,696
Poďme odstrániť ďalšie
element z frontu.

190
00:09:38,696 --> 00:09:42,400
V prípade, aktuálny najstaršie
prvkom je umiestnenie poľa 1.

191
00:09:42,400 --> 00:09:44,220
To je to, čo nám hovorí q.front.

192
00:09:44,220 --> 00:09:46,980
To zelené polia nám hovorí, že
že je to najstaršie element.

193
00:09:46,980 --> 00:09:49,310
A tak, x sa stane 33.

194
00:09:49,310 --> 00:09:52,130
Budeme tak nejako zabudol
33, že existuje v poli,

195
00:09:52,130 --> 00:09:55,100
a budeme hovoriť, že teraz,
Nový najstaršie element vo fronte

196
00:09:55,100 --> 00:09:58,900
je v mieste poľa 2 a veľkosť
fronty, počet prvkov

197
00:09:58,900 --> 00:10:02,152
máme vo fronte, je 1.

198
00:10:02,152 --> 00:10:05,110
Teraz poďme Zaradí niečo, a ja
nejako dal to preč pred sekundou,

199
00:10:05,110 --> 00:10:10,340
ale ak chceme dať 40 do
front, kde je 40 ísť?

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

201
00:10:12,880 --> 00:10:17,730
Dobre sme sa ho uvedenia
v q.front a fronty veľkosti,

202
00:10:17,730 --> 00:10:20,850
a tak to dáva zmysel, aby
skutočne dať 40 sem.

203
00:10:20,850 --> 00:10:22,840
Teraz si všimnite, že v
nejaký bod, ideme

204
00:10:22,840 --> 00:10:27,980
sa dostať do konca roka
Naše pole vnútri q,

205
00:10:27,980 --> 00:10:32,010
ale že vybledla 28 a 33--
sú to v skutočnosti, technicky

206
00:10:32,010 --> 00:10:33,300
otvorené priestory, je to tak?

207
00:10:33,300 --> 00:10:36,040
A tak môžeme eventually--
že pravidlo pridania

208
00:10:36,040 --> 00:10:40,390
tí dvaja together-- sme môže nakoniec
treba mod podľa veľkosti kapacity

209
00:10:40,390 --> 00:10:41,410
takže môžeme zabaliť okolo.

210
00:10:41,410 --> 00:10:43,620
>> Takže ak sa dostaneme do prvku
číslo 10, keď sme

211
00:10:43,620 --> 00:10:48,790
nahradí ju v elemente číslo 10, mali by sme
skutočne dať do lokalite poľa 0.

212
00:10:48,790 --> 00:10:50,997
A keď sme sa chystali
array ma location-- ospravedlňte,

213
00:10:50,997 --> 00:10:53,080
ak sme pridali je spolu,
a dostali sme sa na číslo

214
00:10:53,080 --> 00:10:56,330
11 z nich by byť tam, kde by sme dať
to, ktorá neexistuje v tomto array--

215
00:10:56,330 --> 00:10:58,200
to by mal ísť mimo hraciu plochu.

216
00:10:58,200 --> 00:11:03,367
Mohli by sme mod o 10 a dal
že v mieste poľa 1.

217
00:11:03,367 --> 00:11:04,450
Tak to je, ako fungujú fronty.

218
00:11:04,450 --> 00:11:08,540
Vždycky ísť zľava
doprava a prípadne zábal okolo.

219
00:11:08,540 --> 00:11:11,280
A viete, že sú
plnej výške, ak veľkosť, že červené pole,

220
00:11:11,280 --> 00:11:13,710
stáva rovnakú kapacitu.

221
00:11:13,710 --> 00:11:16,720
A tak potom, čo sme pridali 40 do
front, no čo musíme urobiť?

222
00:11:16,720 --> 00:11:19,890
No, najstarší element
vo fronte je stále 19,

223
00:11:19,890 --> 00:11:21,990
takže nechceme meniť
predné frontu,

224
00:11:21,990 --> 00:11:23,820
ale teraz máme dve
prvky vo fronte,

225
00:11:23,820 --> 00:11:28,710
a tak chceme zvýšiť
našej veľkosti od 1 do 2.

226
00:11:28,710 --> 00:11:31,820
>> To je celkom veľa to s
pracovať s front založená na poli,

227
00:11:31,820 --> 00:11:33,630
a podobne ako komín,
tam je tiež spôsob,

228
00:11:33,630 --> 00:11:36,450
realizovať fronty ako Google zoznamu.

229
00:11:36,450 --> 00:11:40,150
Teraz, ak tento typ štruktúra dát
vyzerá povedome vám, to je.

230
00:11:40,150 --> 00:11:43,780
Nie je to jednotlivo spájať zoznam,
je to dvojnásobne previazaný zoznam.

231
00:11:43,780 --> 00:11:46,790
A teraz, ako stranou, to je
v skutočnosti je to možné realizovať

232
00:11:46,790 --> 00:11:50,160
front ako jednotlivo spájať zoznam, ale
Myslím si, že pokiaľ ide o vizualizáciu,

233
00:11:50,160 --> 00:11:53,350
to vlastne mohlo pomôcť k zobrazenie
to ako dvojnásobne Google zoznamu.

234
00:11:53,350 --> 00:11:56,850
Ale je to určite možné
robiť to ako single previazaný zoznam.

235
00:11:56,850 --> 00:12:00,110
>> Takže poďme sa pozrieť na
čo by to mohlo vyzerať.

236
00:12:00,110 --> 00:12:02,750
Ak chceme, aby enquue--
takže teraz, opäť sme

237
00:12:02,750 --> 00:12:05,360
prepnutie na Google-list
na základe modelu tu.

238
00:12:05,360 --> 00:12:08,420
Ak chceme, aby Zaradí, chceme
pridať nový prvok, dobre

239
00:12:08,420 --> 00:12:09,730
Čo musíme urobiť?

240
00:12:09,730 --> 00:12:12,770
No, v prvom rade, pretože
budeme pridávať na koniec

241
00:12:12,770 --> 00:12:15,520
a odstránenie z
Spočiatku sme pravdepodobne

242
00:12:15,520 --> 00:12:20,050
chcú zachovať odkazy na oba
hlava a chvost Google zoznamu?

243
00:12:20,050 --> 00:12:22,660
Chvost je ďalší termín pre
koniec zoznamu Google,

244
00:12:22,660 --> 00:12:24,496
posledný prvok v pripojenom zozname.

245
00:12:24,496 --> 00:12:26,620
A to bude asi,
opäť, byť prospešné pre nás

246
00:12:26,620 --> 00:12:28,477
ak sú globálne premenné.

247
00:12:28,477 --> 00:12:31,060
Ale teraz, keď chceme pridať nový
prvok čo musíme urobiť?

248
00:12:31,060 --> 00:12:35,262
To, čo sme práve [? Malak?], Alebo dynamicky
prideliť náš nový uzol pre seba.

249
00:12:35,262 --> 00:12:38,220
A potom, ako keď sme sa pridať niektorý
prvok do dvojnásobne Google zoznamu my,

250
00:12:38,220 --> 00:12:40,410
jednoducho musí triediť of--
tie posledné tri kroky tu

251
00:12:40,410 --> 00:12:43,330
sú všetko len o presunutie
ukazovatele v správnym spôsobom

252
00:12:43,330 --> 00:12:46,710
tak, že prvok dostane pridaný do
reťaz bez prerušenia reťazca

253
00:12:46,710 --> 00:12:49,580
alebo robiť nejaký chyby
alebo má nejaký nehody

254
00:12:49,580 --> 00:12:54,505
štát, v ktorom by sme náhodou
orphan niektoré prvky našej fronty.

255
00:12:54,505 --> 00:12:55,880
Tu je to, čo by to mohlo vyzerať.

256
00:12:55,880 --> 00:13:00,980
Chceme pridať prvok
10 na konci tejto fronty.

257
00:13:00,980 --> 00:13:03,380
Takže najstarší prvok tu
je reprezentovaný hlavy.

258
00:13:03,380 --> 00:13:06,800
To je prvá vec, ktorú kladieme
do tohto hypotetického frontu tu.

259
00:13:06,800 --> 00:13:10,430
A chvost, 13, je najviac
nedávno pridal prvok.

260
00:13:10,430 --> 00:13:17,030
A tak, ak chceme, aby do 10 Zaradí
Táto fronta, chceme, aby to po 13.

261
00:13:17,030 --> 00:13:19,860
A tak budeme dynamicky
prideliť priestor pre nový uzol

262
00:13:19,860 --> 00:13:23,280
a skontrolujte, či null, aby sa uistil
nemáme zlyhanie pamäte.

263
00:13:23,280 --> 00:13:27,040
Potom sme sa chystáte
miesto 10 do tohto uzla,

264
00:13:27,040 --> 00:13:30,030
a teraz musíme byť opatrní
o tom, ako organizovať ukazovatele

265
00:13:30,030 --> 00:13:32,180
takže neporušujú reťaz.

266
00:13:32,180 --> 00:13:38,910
>> Môžeme nastaviť 10 je predchádzajúca pole
poukázať späť do starého chvosta

267
00:13:38,910 --> 00:13:41,620
a pretože '10 bude
nový chvost v určitom okamihu

268
00:13:41,620 --> 00:13:44,459
v čase, keď všetky tieto
reťaze sú pripojené,

269
00:13:44,459 --> 00:13:46,250
nič sa príde
po 10 práve teraz.

270
00:13:46,250 --> 00:13:49,880
A tak ďalší ukazovateľ 10 je
bude ukazovať na null,

271
00:13:49,880 --> 00:13:53,580
a potom po tom, čo sme to urobiť, potom, čo sme
pripojený 10 dozadu k reťazi,

272
00:13:53,580 --> 00:13:57,780
môžeme vziať staré hlavu, alebo, ospravedlnenie
ja, starý chvost fronty.

273
00:13:57,780 --> 00:14:02,980
Starý koniec frontu,
13, a urobiť z neho poukazujú na 10.

274
00:14:02,980 --> 00:14:08,220
A teraz, v tomto bode, máme
enqueued číslo 10 do tejto fronty.

275
00:14:08,220 --> 00:14:14,740
Všetko, čo musíme urobiť, je teraz len presunúť
tail, aby ukazoval na 10 namiesto toho, aby 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing je vlastne
veľmi podobné praskanie

277
00:14:17,630 --> 00:14:21,710
zo zásobníka, ktorý je
realizovaný ako spájať zoznam

278
00:14:21,710 --> 00:14:24,040
ak ste videli stohy videa.

279
00:14:24,040 --> 00:14:27,280
Všetko, čo musíme urobiť, je začať u
začiatok, nájsť druhý prvok,

280
00:14:27,280 --> 00:14:30,480
uvoľniť prvý prvok,
a presuňte hlavu

281
00:14:30,480 --> 00:14:32,930
prejdite k druhému prvku.

282
00:14:32,930 --> 00:14:37,920
Pravdepodobne lepšie ho vizualizovať
jednoducho byť extra jasné, o tom.

283
00:14:37,920 --> 00:14:39,230
Tak tu je zase naša fronta.

284
00:14:39,230 --> 00:14:42,600
12 je najstaršia element
v našej fronte, hlavy.

285
00:14:42,600 --> 00:14:46,210
10 je najnovší prvok
v našej fronte, chvostom.

286
00:14:46,210 --> 00:14:49,310
>> A tak, keď chceme,
na dequeue prvok,

287
00:14:49,310 --> 00:14:52,202
chceme odstrániť najstarší prvok.

288
00:14:52,202 --> 00:14:52,910
Tak čo budeme robiť?

289
00:14:52,910 --> 00:14:55,243
Tak sme si stanovili ukazovatele traversal
ktorý začína v čele,

290
00:14:55,243 --> 00:14:57,840
a my sme ho presunúť tak, aby sa
poukazuje na druhý prvok

291
00:14:57,840 --> 00:15:02,290
z toho queue-- niečo tým, že hovorí tráv
sa rovná tráv šípku, napríklad,

292
00:15:02,290 --> 00:15:07,170
by sa pohyboval tráv tu poukázať na
15, ktorý po tom, čo sme dequeue 12,

293
00:15:07,170 --> 00:15:13,030
alebo potom, čo sme odobratie 12, bude
sa stal vtedajší najstarší element.

294
00:15:13,030 --> 00:15:16,360
>> Teraz máme držať na prvý
prvok cez ukazovateľ hlavy

295
00:15:16,360 --> 00:15:19,440
a druhý prvok
pomocou ukazovateľa tráv.

296
00:15:19,440 --> 00:15:25,170
Teraz môžeme bez hlavy, a potom môžeme
teda pred 15. nič príde ešte.

297
00:15:25,170 --> 00:15:29,990
Takže môžeme zmeniť 15 je predchádzajúca
ukazovateľ poukázať na null,

298
00:15:29,990 --> 00:15:31,874
a my len presunúť hlavu nad.

299
00:15:31,874 --> 00:15:32,540
A tam ideme.

300
00:15:32,540 --> 00:15:35,840
Teraz máme úspešne sa
dequeued 12, a teraz sme

301
00:15:35,840 --> 00:15:39,180
majú ďalšie fronty 4 prvkov.

302
00:15:39,180 --> 00:15:41,700
To je skoro všetky
tam je front,

303
00:15:41,700 --> 00:15:45,810
ako pole-based a spojený-list báze.

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

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

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