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

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

3
00:00:07,370 --> 00:00:09,870
je to pravděpodobně bude cítit
jako trochou déjà vu.

4
00:00:09,870 --> 00:00:13,850
Bude to velmi podobným konceptem,
jen s mírným twist na to.

5
00:00:13,850 --> 00:00:15,530
Budeme mluvit teď o frontách.

6
00:00:15,530 --> 00:00:19,350
Takže fronta, podobně jako zásobníku,
je další druh datové struktury

7
00:00:19,350 --> 00:00:22,412
že můžeme použít k udržení
Data v organizovaným způsobem.

8
00:00:22,412 --> 00:00:24,120
Podobně jako stack,
aby mohl být zaveden

9
00:00:24,120 --> 00:00:27,000
jako pole nebo propojeném seznamu.

10
00:00:27,000 --> 00:00:30,320
Na rozdíl od zásobníku, pravidla
že jsme se použít k určení

11
00:00:30,320 --> 00:00:34,210
když se věci dostat přidáno a odstraněn z
fronta je trochu jinak.

12
00:00:34,210 --> 00:00:36,590
>> Na rozdíl od stohu, který je
je struktura LIFO,

13
00:00:36,590 --> 00:00:45,610
poslední dovnitř, první ven, fronta je FIFO
Struktura, FIFO, první dovnitř, první ven.

14
00:00:45,610 --> 00:00:49,320
Nyní fronty, budete pravděpodobně
mají analogii k front.

15
00:00:49,320 --> 00:00:52,820
Pokud jste někdy byli ve frontě na
zábavní park, nebo v bance,

16
00:00:52,820 --> 00:00:56,430
je tu jakýsi spravedlnosti
prováděcí strukturu.

17
00:00:56,430 --> 00:00:59,160
První osoba ve frontě u
banka je první osobou,

18
00:00:59,160 --> 00:01:00,760
kdo dostane mluvit s přepážce.

19
00:01:00,760 --> 00:01:03,522
>> Bylo by to jakýsi závod
do spodní části v případě, že jediným způsobem, jak

20
00:01:03,522 --> 00:01:06,730
musíš mluvit s Teller At The
Banka měla být poslední, kdo v řadě.

21
00:01:06,730 --> 00:01:09,146
Každý by vždycky chtějí
být poslední, kdo v řadě,

22
00:01:09,146 --> 00:01:12,580
a osoba, která tam byl jako první
který byl čekal na chvíli,

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

24
00:01:14,715 --> 00:01:17,590
před tím, než mají šanci skutečně
stáhnout nějaké peníze v bance.

25
00:01:17,590 --> 00:01:22,510
A tak fronty jsou hornin
spravedlivost prováděcí strukturu.

26
00:01:22,510 --> 00:01:25,780
Ale to nemusí nutně znamenat,
že komíny jsou špatná věc, jen

27
00:01:25,780 --> 00:01:28,160
že fronty jsou dalším způsobem, jak to udělat.

28
00:01:28,160 --> 00:01:32,420
Takže opět fronty je první, nejprve
out, proti stohu, který jako poslední,

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

30
00:01:34,440 --> 00:01:36,190
Podobně jako stack,
Máme dvě operace

31
00:01:36,190 --> 00:01:38,470
že můžeme hrát na frontách.

32
00:01:38,470 --> 00:01:43,910
Jména jsou Enqueue, což je přidání
nový prvek na konec fronty,

33
00:01:43,910 --> 00:01:47,330
a dequeue, který je
k odstranění nejstarší

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

35
00:01:49,670 --> 00:01:53,600
Takže budeme přidávat prvky
na konci fronty,

36
00:01:53,600 --> 00:01:57,220
a budeme odstranit prvky
z fronty.

37
00:01:57,220 --> 00:02:00,790
Opět platí, že se v zásobníku, jsme přidávali
prvky na vrchol stohu

38
00:02:00,790 --> 00:02:03,380
a odebírání prvků
z vrcholu zásobníku.

39
00:02:03,380 --> 00:02:07,570
Tak s Zařadí, je to přidáním
konec, vyjmutí z přední strany.

40
00:02:07,570 --> 00:02:10,639
A tak nejstarší věc v tu
je vždy další věc,

41
00:02:10,639 --> 00:02:13,620
vyjít ven, když se pokusíme
a dequeue něco.

42
00:02:13,620 --> 00:02:18,330
>> Takže znovu, s frontami, můžeme
implementace založená na poli

43
00:02:18,330 --> 00:02:20,110
a spojený-list na základě implementace.

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

45
00:02:24,620 --> 00:02:27,070
Definice struktura
Vypadá dost podobné.

46
00:02:27,070 --> 00:02:30,720
Máme další pole
tam typu datové hodnoty,

47
00:02:30,720 --> 00:02:32,690
takže to může držet libovolné datové typy.

48
00:02:32,690 --> 00:02:35,570
Máme jít znovu k použití
celá čísla v tomto příkladu.

49
00:02:35,570 --> 00:02:39,830
>> A stejně jako s našimi
Implementace zásobníku založená na poli,

50
00:02:39,830 --> 00:02:42,340
proto, že jsme za použití
pole, jsme nutně

51
00:02:42,340 --> 00:02:46,850
má toto omezení, že C druh
z vynucuje na nás, což je, že jsme

52
00:02:46,850 --> 00:02:51,670
nemají žádnou dynamiku v naší
schopnost růst a zmenšit pole.

53
00:02:51,670 --> 00:02:55,710
Musíme se rozhodnout, na začátku
jaká je maximální počet věcí

54
00:02:55,710 --> 00:02:59,300
že můžeme dát do toho
fronta, a v tomto případě,

55
00:02:59,300 --> 00:03:02,070
kapacita by měla být asi libra
definovaná konstantou našeho kódu.

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

57
00:03:05,430 --> 00:03:07,690
>> Musíme sledovat
přední fronty

58
00:03:07,690 --> 00:03:11,160
takže víme, které element
chceme dequeue,

59
00:03:11,160 --> 00:03:15,070
a musíme také sledovat
něco else-- počet prvků

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

61
00:03:16,690 --> 00:03:19,360
Všimněte si, nejsme sledování
na konci fronty, jen

62
00:03:19,360 --> 00:03:21,150
velikost fronty.

63
00:03:21,150 --> 00:03:24,310
A důvod pro to, doufejme,
stát se trochu jasnější za chvíli.

64
00:03:24,310 --> 00:03:26,143
Poté, co jsme dokončili
tato definice typu,

65
00:03:26,143 --> 00:03:29,080
máme nový datový typ
volal fronta, kterou můžeme nyní

66
00:03:29,080 --> 00:03:30,630
deklarovat proměnné tohoto typu dat.

67
00:03:30,630 --> 00:03:35,350
A poněkud matouce, rozhodl jsem se
volat tento fronty Q, písmeno

68
00:03:35,350 --> 00:03:38,090
Q namísto datového typu q.

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

70
00:03:39,600 --> 00:03:40,700
Jedná se o strukturu.

71
00:03:40,700 --> 00:03:45,730
Obsahuje tři členy nebo tři
pole, pole kapacity velikosti.

72
00:03:45,730 --> 00:03:47,340
V tomto případě, kapacita je 10.

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

74
00:03:49,580 --> 00:03:55,240
V zeleném je přední část naší fronty,
Dalším prvkem, který bude odebrán, a v červené

75
00:03:55,240 --> 00:03:58,610
bude velikost fronty,
kolik prvky jsou v současné době

76
00:03:58,610 --> 00:04:01,190
existující ve frontě.

77
00:04:01,190 --> 00:04:05,300
Takže když řekneme q.front rovni
0, a velikost q.size rovná 0--

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

79
00:04:07,120 --> 00:04:11,070
A v tomto bodě, jsme docela hodně
připraveni začít pracovat s naším fronty.

80
00:04:11,070 --> 00:04:14,140
>> Takže první operace můžeme
proveďte je Zařadí něco,

81
00:04:14,140 --> 00:04:16,860
přidat nový prvek
konec fronty.

82
00:04:16,860 --> 00:04:19,089
No co potřebujeme
dělat v obecném případě?

83
00:04:19,089 --> 00:04:23,690
No to funkce Zařadí potřeby
k přijetí ukazatele na naší fronty.

84
00:04:23,690 --> 00:04:26,370
Opět platí, že pokud bychom prohlásil
naše fronta globálně,

85
00:04:26,370 --> 00:04:29,490
nebudeme potřebovat to udělat
nutně, ale obecně, jsme

86
00:04:29,490 --> 00:04:32,330
je třeba přijmout ukazatele
do datových struktur

87
00:04:32,330 --> 00:04:35,040
jako je tento, protože jinak,
jsme kolem value-- jsme

88
00:04:35,040 --> 00:04:38,140
předáním kopie frontě,
a proto nejsme skutečně mění,

89
00:04:38,140 --> 00:04:41,050
fronta, že máme v úmyslu změnit.

90
00:04:41,050 --> 00:04:44,860
>> Další věc, kterou je třeba udělat, je přijmout
datový prvek příslušného typu.

91
00:04:44,860 --> 00:04:46,818
Opět platí, že v tomto případě je to
bude celá čísla,

92
00:04:46,818 --> 00:04:49,330
ale můžete libovolně
deklarovat datový typ jako hodnotu

93
00:04:49,330 --> 00:04:51,160
a použít obecněji.

94
00:04:51,160 --> 00:04:56,030
To je prvek, chceme Zařadí,
chceme přidat na konec fronty.

95
00:04:56,030 --> 00:04:58,573
Pak jsme se skutečně chtějí
umístit tato data ve frontě.

96
00:04:58,573 --> 00:05:01,490
V tomto případě, umístění do
Správné umístění našeho pole,

97
00:05:01,490 --> 00:05:05,040
a pak chceme změnit velikost
fronty, kolik prvků jsme

98
00:05:05,040 --> 00:05:07,050
V současné době máme.

99
00:05:07,050 --> 00:05:07,990
>> Tak pojďme začít.

100
00:05:07,990 --> 00:05:10,890
Zde je, opět, že obecná
deklarace funkce forma

101
00:05:10,890 --> 00:05:13,980
za to, co Enqueue by mohl vypadat.

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

103
00:05:14,910 --> 00:05:18,335
Pojďme Zařadí číslo
28 do fronty.

104
00:05:18,335 --> 00:05:19,460
Tak co budeme dělat?

105
00:05:19,460 --> 00:05:23,390
No, před naší frontě
při 0 ° C, a velikosti našeho fronty

106
00:05:23,390 --> 00:05:29,680
je 0, a tak jsme asi chcete dát
čí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 jsme teď umístěny tak, aby se tam.

109
00:05:32,540 --> 00:05:34,820
Takže teď co musíme změnit?

110
00:05:34,820 --> 00:05:37,090
Nechceme měnit
přední fronty,

111
00:05:37,090 --> 00:05:40,850
protože chceme vědět, jaký prvek
bychom mohli potřebovat, aby dequeue později.

112
00:05:40,850 --> 00:05:44,020
Takže důvod, proč jsme tam front
je jakýmsi ukazatelem toho, co je

113
00:05:44,020 --> 00:05:46,439
nejstarší věc na poli.

114
00:05:46,439 --> 00:05:49,730
No nejstarší věc na array-- v
Skutečnost, jediná věc, v poli vpravo

115
00:05:49,730 --> 00:05:53,540
now-- je 28, který je
v místě pole 0.

116
00:05:53,540 --> 00:05:56,160
Takže nechceme, aby
změnit tuto zelenou linku,

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

118
00:05:57,910 --> 00:06:00,510
Spíše chceme změnit velikost.

119
00:06:00,510 --> 00:06:04,110
Takže v tomto případě, budeme
zvýšit velikost na 1.

120
00:06:04,110 --> 00:06:08,430
>> Nyní obecný jakousi myšlenkou, kde se
další prvek se chystá jít ve frontě

121
00:06:08,430 --> 00:06:12,310
je přidat těchto dvou čísel
spolu, přední a velikost,

122
00:06:12,310 --> 00:06:16,390
a že tě kde vyprávět další
prvek ve frontě se chystá jít.

123
00:06:16,390 --> 00:06:18,130
Takže teď pojďme Zařadí jiné číslo.

124
00:06:18,130 --> 00:06:20,250
Pojďme Zařadí 33.

125
00:06:20,250 --> 00:06:24,480
Takže 33 se chystá jít do
Poloha pole 0 a 1.

126
00:06:24,480 --> 00:06:26,840
Takže v tomto případě, bude to
jít do umístění pole 1,

127
00:06:26,840 --> 00:06:29,500
a nyní velikost naší fronty je 2.

128
00:06:29,500 --> 00:06:31,840
>> Opět platí, že nejsme mění
přední část naší fronty,

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

130
00:06:34,730 --> 00:06:38,220
Chcete-to-- když se nakonec dostal
na dequeuing, odebírání prvků

131
00:06:38,220 --> 00:06:43,300
z této fronty, chceme vědět
kde je nejstarší element.

132
00:06:43,300 --> 00:06:48,620
A tak jsme vždycky je třeba zachovat
některé ukazatel, kde to je.

133
00:06:48,620 --> 00:06:50,410
Takže to je to, co je tu pro 0.

134
00:06:50,410 --> 00:06:52,910
To je to, co přední straně je tam.

135
00:06:52,910 --> 00:06:55,022
>> Pojďme v Zařadí ještě jeden prvek, 19.

136
00:06:55,022 --> 00:06:56,980
Jsem si jistý, můžete hádat,
kde 19 se chystá jít.

137
00:06:56,980 --> 00:06:59,860
Bude to jít do
pole číslo umístění 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 nyní je velikost naší fronty 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 pokud jsme měli, a nebudeme
právě teď, Zařadí další prvek,

142
00:07:08,490 --> 00:07:11,370
to by jít do místa pole
číslo 3, a velikost naší fronty

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

144
00:07:13,160 --> 00:07:15,279
Proto jsme enqueued několik prvků teď.

145
00:07:15,279 --> 00:07:16,570
Nyní začněme k jejich odstranění.

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

147
00:07:19,450 --> 00:07:23,340
>> Takže podobně jako pop, který je trochu
analogu tohoto pro komíny,

148
00:07:23,340 --> 00:07:26,180
dequeue třeba akceptovat
Ukazatel na queue-- znovu

149
00:07:26,180 --> 00:07:28,140
pokud je to v celosvětovém měřítku deklarována.

150
00:07:28,140 --> 00:07:31,610
Nyní chceme změnit umístění
z fronty.

151
00:07:31,610 --> 00:07:35,050
To je místo, kde to tak nějak přijde
do hry, že přední variabilní,

152
00:07:35,050 --> 00:07:37,310
protože jakmile jsme se odstranit
prvek, chceme

153
00:07:37,310 --> 00:07:40,720
přesunout do dalšího nejstarší prvek.

154
00:07:40,720 --> 00:07:44,180
>> Pak chceme snížit
velikost fronty,

155
00:07:44,180 --> 00:07:47,130
a pak jsme se chcete vrátit hodnotu
, který byl odebrán z fronty.

156
00:07:47,130 --> 00:07:48,921
Opět platí, že nechceme, aby prostě odhodit to.

157
00:07:48,921 --> 00:07:51,170
Jsme pravděpodobně Extrahujete
to z queue-- kterém jsme

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

159
00:07:54,170 --> 00:08:01,080
Takže chceme, aby tato funkce se vrátit
datový prvek typu hodnoty.

160
00:08:01,080 --> 00:08:04,360
Opět platí, že v tomto případě, že hodnota je celé číslo.

161
00:08:04,360 --> 00:08:05,670
>> Takže teď pojďme dequeue něco.

162
00:08:05,670 --> 00:08:09,310
Pojďme odstranit prvek z fronty.

163
00:08:09,310 --> 00:08:15,970
Říkáme-li, int x rovná & q, ampersand q--
Znovu to je ukazatel na tento q dat

164
00:08:15,970 --> 00:08:20,177
structure-- co element
se bude dequeued?

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

166
00:08:23,840 --> 00:08:29,480
V tomto případě, protože se jedná o prvním
in, first out datové struktury, FIFO,

167
00:08:29,480 --> 00:08:33,690
První věc, kterou jsme se dát do toho
fronta byla 28, a tedy v tomto případě,

168
00:08:33,690 --> 00:08:37,245
budeme brát 28 z
fronty, ne 19, který je co

169
00:08:37,245 --> 00:08:38,870
bychom udělali, jestli to byla hromada.

170
00:08:38,870 --> 00:08:42,220
Chystáme se přijmout 28 z fronty.

171
00:08:42,220 --> 00:08:44,960
>> Podobně k tomu, co jsme to udělali s
stoh, nejsme ve skutečnosti

172
00:08:44,960 --> 00:08:47,345
chystá vymazat 28
z fronty samotné,

173
00:08:47,345 --> 00:08:49,470
my jen tak druhu
z předstírat, že tam není.

174
00:08:49,470 --> 00:08:51,678
Takže to bude tam zůstat
v paměti, ale my jsme prostě

175
00:08:51,678 --> 00:08:57,820
bude druh ignorovat pohybem
další dvě pole naší q dat

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

177
00:08:58,830 --> 00:09:00,230
Chystáme se změnit frontu.

178
00:09:00,230 --> 00:09:04,290
Q.front se nyní chystá
být 1, protože to je nyní

179
00:09:04,290 --> 00:09:07,740
nejstarší prvek máme v naší
fronta, protože jsme už odstraněno 28,

180
00:09:07,740 --> 00:09:10,460
což byl bývalý nejstarší element.

181
00:09:10,460 --> 00:09:13,540
>> A teď, chceme změnit
velikost fronty

182
00:09:13,540 --> 00:09:15,780
na dva prvky místo tří.

183
00:09:15,780 --> 00:09:20,450
Teď pamatovat dříve jsem řekl, když jsme
Chcete přidat prvky do fronty,

184
00:09:20,450 --> 00:09:26,000
dáme to v místě pole
který je součtem přední a velikosti.

185
00:09:26,000 --> 00:09:29,050
Takže v tomto případě, jsme stále uvedení
to, další element ve frontě,

186
00:09:29,050 --> 00:09:33,360
do umístění pole 3, a
budeme vidět, že v druhém.

187
00:09:33,360 --> 00:09:35,730
>> Proto jsme nyní naše dequeued
První element z fronty.

188
00:09:35,730 --> 00:09:36,480
Udělejme to znovu.

189
00:09:36,480 --> 00:09:38,696
Pojďme odstranit další
element z fronty.

190
00:09:38,696 --> 00:09:42,400
V případě, aktuální nejstarší
prvkem je umístění pole 1.

191
00:09:42,400 --> 00:09:44,220
To je to, co nám říká q.front.

192
00:09:44,220 --> 00:09:46,980
To zelené pole nám říká, že
že je to nejstarší element.

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

194
00:09:49,310 --> 00:09:52,130
Budeme tak nějak zapomněl
33, že existuje v poli,

195
00:09:52,130 --> 00:09:55,100
a budeme říkat, že teď,
Nový nejstarší element ve frontě

196
00:09:55,100 --> 00:09:58,900
je v místě pole 2 a velikost
fronty, počet prvků

197
00:09:58,900 --> 00:10:02,152
máme ve frontě, je 1.

198
00:10:02,152 --> 00:10:05,110
Nyní pojďme Zařadí něco, a já
nějak dal to pryč před vteřinou,

199
00:10:05,110 --> 00:10:10,340
ale pokud chceme dát 40 do
fronta, kde je 40 jít?

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

201
00:10:12,880 --> 00:10:17,730
Dobře jsme se ho uvedení
v q.front a fronty velikosti,

202
00:10:17,730 --> 00:10:20,850
a tak to dává smysl, aby
skutečně dát 40 sem.

203
00:10:20,850 --> 00:10:22,840
Nyní si všimněte, že v
nějaký bod, jdeme

204
00:10:22,840 --> 00:10:27,980
se dostat do konce roku
Naše pole uvnitř q,

205
00:10:27,980 --> 00:10:32,010
ale že vybledla 28 a 33--
jsou to ve skutečnosti, technicky

206
00:10:32,010 --> 00:10:33,300
otevřené prostory, je to tak?

207
00:10:33,300 --> 00:10:36,040
A tak můžeme eventually--
že pravidlo přidání

208
00:10:36,040 --> 00:10:40,390
ti dva together-- jsme může nakonec
je třeba mod podle velikosti kapacity

209
00:10:40,390 --> 00:10:41,410
takže můžeme zabalit kolem.

210
00:10:41,410 --> 00:10:43,620
>> Takže pokud se dostaneme do prvku
číslo 10, když jsme

211
00:10:43,620 --> 00:10:48,790
nahradí ji v elementu číslo 10, měli bychom
skutečně dát do lokalitě pole 0.

212
00:10:48,790 --> 00:10:50,997
A když jsme se chystali
array mě location-- omluvte,

213
00:10:50,997 --> 00:10:53,080
pokud jsme přidali je spolu,
a dostali jsme se na číslo

214
00:10:53,080 --> 00:10:56,330
11 z nich by být tam, kde bychom dát
to, která neexistuje v tomto array--

215
00:10:56,330 --> 00:10:58,200
to by měl jít mimo hrací plochu.

216
00:10:58,200 --> 00:11:03,367
Mohli bychom mod o 10 a dal
že v místě pole 1.

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

218
00:11:04,450 --> 00:11:08,540
Vždycky jít zleva
doprava a případně zábal kolem.

219
00:11:08,540 --> 00:11:11,280
A víte, že jsou
plné výši, pokud velikost, že červené pole,

220
00:11:11,280 --> 00:11:13,710
stává stejnou kapacitu.

221
00:11:13,710 --> 00:11:16,720
A tak poté, co jsme přidali 40 do
fronta, no co musíme udělat?

222
00:11:16,720 --> 00:11:19,890
No, nejstarší element
ve frontě je stále 19,

223
00:11:19,890 --> 00:11:21,990
takže nechceme měnit
přední fronty,

224
00:11:21,990 --> 00:11:23,820
ale teď máme dvě
prvky ve frontě,

225
00:11:23,820 --> 00:11:28,710
a tak chceme zvýšit
naší velikosti od 1 do 2.

226
00:11:28,710 --> 00:11:31,820
>> To je docela hodně to s
pracovat s front založená na poli,

227
00:11:31,820 --> 00:11:33,630
a podobně jako komín,
tam je také způsob,

228
00:11:33,630 --> 00:11:36,450
realizovat fronty jako Google seznamu.

229
00:11:36,450 --> 00:11:40,150
Nyní, pokud tento typ struktura dat
vypadá povědomě vám, to je.

230
00:11:40,150 --> 00:11:43,780
Není to jednotlivě spojový seznam,
je to dvojnásob provázaný seznam.

231
00:11:43,780 --> 00:11:46,790
A teď, jak stranou, to je
ve skutečnosti je to možné realizovat

232
00:11:46,790 --> 00:11:50,160
fronta jako jednotlivě spojový seznam, ale
Myslím si, že pokud jde o vizualizaci,

233
00:11:50,160 --> 00:11:53,350
to vlastně mohlo pomoci k zobrazení
to jako dvojnásobně Google seznamu.

234
00:11:53,350 --> 00:11:56,850
Ale je to určitě možné
dělat to jako singly provázaný seznam.

235
00:11:56,850 --> 00:12:00,110
>> Takže pojďme se podívat na
co by to mohlo vypadat.

236
00:12:00,110 --> 00:12:02,750
Pokud chceme, aby enquue--
takže teď, opět jsme

237
00:12:02,750 --> 00:12:05,360
přepnutí na Google-list
na základě modelu zde.

238
00:12:05,360 --> 00:12:08,420
Pokud chceme, aby Zařadí, chceme
přidat nový prvek, dobře

239
00:12:08,420 --> 00:12:09,730
Co musíme udělat?

240
00:12:09,730 --> 00:12:12,770
No, v první řadě, protože
budeme přidávat na konec

241
00:12:12,770 --> 00:12:15,520
a odstranění z
Zpočátku jsme pravděpodobně

242
00:12:15,520 --> 00:12:20,050
chtějí zachovat odkazy na oba
hlava a ocas Google seznamu?

243
00:12:20,050 --> 00:12:22,660
Ocas je další termín pro
konec seznamu Google,

244
00:12:22,660 --> 00:12:24,496
poslední prvek v připojeném seznamu.

245
00:12:24,496 --> 00:12:26,620
A to bude asi,
opět, být prospěšné pro nás

246
00:12:26,620 --> 00:12:28,477
pokud jsou globální proměnné.

247
00:12:28,477 --> 00:12:31,060
Ale teď, když chceme přidat nový
prvek co musíme udělat?

248
00:12:31,060 --> 00:12:35,262
To, co jsme právě [? Malak?], nebo dynamicky
přidělit náš nový uzel pro sebe.

249
00:12:35,262 --> 00:12:38,220
A pak, jako když jsme se přidat některý
prvek do dvojnásobně Google seznamu my,

250
00:12:38,220 --> 00:12:40,410
prostě musí třídit of--
ty poslední tři kroky zde

251
00:12:40,410 --> 00:12:43,330
jsou všechno jen o přesunutí
ukazatele v správným způsobem

252
00:12:43,330 --> 00:12:46,710
tak, že prvek dostane přidán do
řetěz bez přerušení řetězce

253
00:12:46,710 --> 00:12:49,580
nebo dělat nějaký chyby
nebo má nějaký nehody

254
00:12:49,580 --> 00:12:54,505
stát, v němž bychom náhodou
orphan některé prvky naší fronty.

255
00:12:54,505 --> 00:12:55,880
Tady je to, co by to mohlo vypadat.

256
00:12:55,880 --> 00:13:00,980
Chceme přidat prvek
10 na konci této fronty.

257
00:13:00,980 --> 00:13:03,380
Takže nejstarší prvek zde
je reprezentován hlavy.

258
00:13:03,380 --> 00:13:06,800
To je první věc, kterou klademe
do tohoto hypotetického fronty zde.

259
00:13:06,800 --> 00:13:10,430
A ocas, 13, je nejvíce
nedávno přidal prvek.

260
00:13:10,430 --> 00:13:17,030
A tak, pokud chceme, aby do 10 Zařadí
Tato fronta, chceme, aby to po 13.

261
00:13:17,030 --> 00:13:19,860
A tak budeme dynamicky
přidělit prostor pro nový uzel

262
00:13:19,860 --> 00:13:23,280
a zkontrolujte, zda null, aby se ujistil
nemáme selhání paměti.

263
00:13:23,280 --> 00:13:27,040
Pak jsme se chystáte
místo 10 do tohoto uzlu,

264
00:13:27,040 --> 00:13:30,030
a nyní musíme být opatrní
o tom, jak organizovat ukazatele

265
00:13:30,030 --> 00:13:32,180
takže neporušují řetěz.

266
00:13:32,180 --> 00:13:38,910
>> Můžeme nastavit 10 je předchozí pole
poukázat zpět do starého ocasu

267
00:13:38,910 --> 00:13:41,620
a protože '10 bude
nový ocas v určitém okamžiku

268
00:13:41,620 --> 00:13:44,459
v době, kdy všechny tyto
řetězy jsou připojeny,

269
00:13:44,459 --> 00:13:46,250
nic se přijde
po 10 právě teď.

270
00:13:46,250 --> 00:13:49,880
A tak další ukazatel 10 je
bude ukazovat na null,

271
00:13:49,880 --> 00:13:53,580
a pak poté, co jsme to udělat, poté, co jsme
připojený 10 dozadu k řetězu,

272
00:13:53,580 --> 00:13:57,780
můžeme vzít staré hlavu, nebo, omluvu
já, starý ocas fronty.

273
00:13:57,780 --> 00:14:02,980
Starý konec fronty,
13, a učinit z něj poukazují na 10.

274
00:14:02,980 --> 00:14:08,220
A nyní, v tomto bodě, máme
enqueued číslo 10 do této fronty.

275
00:14:08,220 --> 00:14:14,740
Vše, co musíme udělat, je nyní jen přesunout
tail, aby ukazoval na 10 místo toho, aby 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing je vlastně
velmi podobné praskání

277
00:14:17,630 --> 00:14:21,710
ze zásobníku, který je
realizován jako spojový seznam

278
00:14:21,710 --> 00:14:24,040
pokud jste viděli stohy videa.

279
00:14:24,040 --> 00:14:27,280
Vše, co musíme udělat, je začít u
začátek, najít druhý prvek,

280
00:14:27,280 --> 00:14:30,480
uvolnit první prvek,
a přesuňte hlavu

281
00:14:30,480 --> 00:14:32,930
přejděte k druhému prvku.

282
00:14:32,930 --> 00:14:37,920
Pravděpodobně lepší jej vizualizovat
prostě být extra jasné, o tom.

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

284
00:14:39,230 --> 00:14:42,600
12 je nejstarší element
v naší frontě, hlavy.

285
00:14:42,600 --> 00:14:46,210
10 je nejnovější prvek
v naší frontě, ocasem.

286
00:14:46,210 --> 00:14:49,310
>> A tak, když chceme,
na dequeue prvek,

287
00:14:49,310 --> 00:14:52,202
chceme odstranit nejstarší prvek.

288
00:14:52,202 --> 00:14:52,910
Tak co budeme dělat?

289
00:14:52,910 --> 00:14:55,243
Tak jsme si stanovili ukazatele traversal
který začíná v čele,

290
00:14:55,243 --> 00:14:57,840
a my jsme jej přesunout tak, aby se
poukazuje na druhý prvek

291
00:14:57,840 --> 00:15:02,290
z toho queue-- něco tím, že říká trav
se rovná trav šipku, například,

292
00:15:02,290 --> 00:15:07,170
by se pohyboval trav zde poukázat na
15, který poté, co jsme dequeue 12,

293
00:15:07,170 --> 00:15:13,030
nebo poté, co jsme odebrání 12, bude
se stal tehdejší nejstarší element.

294
00:15:13,030 --> 00:15:16,360
>> Nyní máme držet na první
prvek přes ukazatel hlavy

295
00:15:16,360 --> 00:15:19,440
a druhý prvek
pomocí ukazatele trav.

296
00:15:19,440 --> 00:15:25,170
Nyní můžeme bez hlavy, a pak můžeme
tedy před 15. nic přijde ještě.

297
00:15:25,170 --> 00:15:29,990
Takže můžeme změnit 15 je předchozí
ukazatel poukázat na null,

298
00:15:29,990 --> 00:15:31,874
a my jen přesunout hlavu nad.

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

300
00:15:32,540 --> 00:15:35,840
Nyní máme úspěšně se
dequeued 12, a teď jsme

301
00:15:35,840 --> 00:15:39,180
mají další fronty 4 prvků.

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

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

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

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

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