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

2
00:00:05,204 --> 00:00:07,370
Doug LLOYD: Mela jekk inti stajt
jaraw l-video fuq munzell,

3
00:00:07,370 --> 00:00:09,870
dan huwa probabbilment se jħossu
bħal xi ftit ta 'deja vu.

4
00:00:09,870 --> 00:00:13,850
Huwa ser kunċett simili ħafna,
biss bi twist żgħir fuqha.

5
00:00:13,850 --> 00:00:15,530
Aħna qed tmur biex jitkellmu issa dwar kjuwijiet.

6
00:00:15,530 --> 00:00:19,350
Allura kju, simili għal munzell,
huwa tip ieħor ta 'struttura data

7
00:00:19,350 --> 00:00:22,412
li nistgħu nużaw biex iżommu
data b'mod organizzat.

8
00:00:22,412 --> 00:00:24,120
Simili għal munzell,
dan jista 'jiġi implimentat

9
00:00:24,120 --> 00:00:27,000
bħala firxa jew lista marbuta.

10
00:00:27,000 --> 00:00:30,320
B'differenza munzell, ir-regoli
li nużaw biex jiddeterminaw

11
00:00:30,320 --> 00:00:34,210
meta l-affarijiet nikseb miżjud u mneħħija mill
kju huma xi ftit differenti.

12
00:00:34,210 --> 00:00:36,590
>> B'differenza munzell, li
hija struttura LIFO,

13
00:00:36,590 --> 00:00:45,610
aħħar li l-ewwel out, kju huwa FIFO
istruttura, FIFO, l-ewwel fl-ewwel li joħroġ.

14
00:00:45,610 --> 00:00:49,320
Issa kjuwijiet, inti probabilment
għandhom analoġija biex kjuwijiet.

15
00:00:49,320 --> 00:00:52,820
Jekk inti stajt qatt kienu fil-linja fil
park ta 'divertiment jew fil-bank,

16
00:00:52,820 --> 00:00:56,430
hemm tip ta 'ekwità
implimentazzjoni istruttura.

17
00:00:56,430 --> 00:00:59,160
L-ewwel persuna fil-linja fil
l-bank huwa l-ewwel persuna

18
00:00:59,160 --> 00:01:00,760
li jottjeni biex tkellem lill-kaxxiera.

19
00:01:00,760 --> 00:01:03,522
>> Ikun tip ta 'razza
sal-qiegħ jekk l-uniku mod

20
00:01:03,522 --> 00:01:06,730
idea li jkellem lill-kaxxiera fil-
bank kellha tkun l-aħħar persuna fil-linja.

21
00:01:06,730 --> 00:01:09,146
Kulħadd dejjem tixtieq
tkun l-aħħar persuna fil-linja,

22
00:01:09,146 --> 00:01:12,580
u l-persuna li kien hemm l-ewwel
li baqgħet tistenna għal xi ftit,

23
00:01:12,580 --> 00:01:14,715
jista 'jkun hemm għal siegħa,
u siegħat, u sigħat

24
00:01:14,715 --> 00:01:17,590
qabel ma jkollhom ċans li attwalment
jirtira xi flus fil-bank.

25
00:01:17,590 --> 00:01:22,510
U hekk kjuwijiet huma tip ta 'l-
ġustizzja implimentazzjoni istruttura.

26
00:01:22,510 --> 00:01:25,780
Iżda dan ma jfissirx neċessarjament
li stacks huma xi ħaġa ħażina, biss

27
00:01:25,780 --> 00:01:28,160
li kjuwijiet huma mod ieħor biex tagħmel dan.

28
00:01:28,160 --> 00:01:32,420
Għalhekk għal darb'oħra kju huwa l-ewwel fl-ewwel
out, versus munzell li jdum fil-

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

30
00:01:34,440 --> 00:01:36,190
Simili għal munzell,
għandna żewġ operazzjonijiet

31
00:01:36,190 --> 00:01:38,470
li nistgħu twettaq fuq kjuwijiet.

32
00:01:38,470 --> 00:01:43,910
L-ismijiet huma enqueue, li huwa li żżid
element ġdid sa l-aħħar tal-kju,

33
00:01:43,910 --> 00:01:47,330
u dequeue, li hija
biex jitneħħew l-eqdem

34
00:01:47,330 --> 00:01:49,670
element minn quddiem tal-kju.

35
00:01:49,670 --> 00:01:53,600
Allura aħna qed tmur biex jiżdiedu elementi
fuq il-aħħar tal-kju,

36
00:01:53,600 --> 00:01:57,220
u aħna qed tmur biex jitneħħew l-elementi
minn quddiem tal-kju.

37
00:01:57,220 --> 00:02:00,790
Għal darb'oħra, bl-munzell, konna żżid
Elementi għall-quċċata tal-munzell

38
00:02:00,790 --> 00:02:03,380
u t-tneħħija elementi
mill-quċċata tal-munzell.

39
00:02:03,380 --> 00:02:07,570
Allura ma enqueue, huwa jżid mal
l-aħħar, it-tneħħija minn quddiem.

40
00:02:07,570 --> 00:02:10,639
Allura l-eqdem ħaġa fil hemm
huwa dejjem l-ħaġa li jmiss

41
00:02:10,639 --> 00:02:13,620
li toħroġ jekk nippruvaw
u dequeue xi ħaġa.

42
00:02:13,620 --> 00:02:18,330
>> Għalhekk għal darb'oħra, ma kjuwijiet, nistgħu
implimentazzjonijiet bbażati fuq array

43
00:02:18,330 --> 00:02:20,110
u marbuta mal-lista implimentazzjonijiet bbażata.

44
00:02:20,110 --> 00:02:24,620
Aħna ser tibda mill-ġdid ma
implimentazzjonijiet bbażati fuq array.

45
00:02:24,620 --> 00:02:27,070
Id-definizzjoni istruttura
jistenna pretty simili.

46
00:02:27,070 --> 00:02:30,720
Għandna firxa ieħor
hemm valur tip ta 'dejta,

47
00:02:30,720 --> 00:02:32,690
għalhekk tista 'żżomm tipi ta' data arbitrarji.

48
00:02:32,690 --> 00:02:35,570
Aħna darb'oħra ser tuża
interi F'dan l-eżempju.

49
00:02:35,570 --> 00:02:39,830
>> U bħad bil tagħna
implimentazzjoni munzell bbażati fuq firxa,

50
00:02:39,830 --> 00:02:42,340
għaliex aħna qed tuża
firxa, aħna neċessarjament

51
00:02:42,340 --> 00:02:46,850
jkollhom din il-limitazzjoni dan it-tip C
tal tinforza fuqna, li hija aħna

52
00:02:46,850 --> 00:02:51,670
m'għandhom l-ebda dinamiżmu fil tagħna
abbiltà li jikbru u tiċkien il-firxa.

53
00:02:51,670 --> 00:02:55,710
Irridu jiddeċiedu fil-bidu
X'inhu n-numru massimu ta 'affarijiet

54
00:02:55,710 --> 00:02:59,300
li nistgħu npoġġu fis dan
kju, u f'dan il-każ,

55
00:02:59,300 --> 00:03:02,070
kapaċità tkun xi lira
definit kostanti fil-kodiċi tagħna.

56
00:03:02,070 --> 00:03:05,430
U għall-finijiet ta 'dan
video, il-kapaċità se tkun 10.

57
00:03:05,430 --> 00:03:07,690
>> Għandna bżonn li jżommu rekord ta '
quddiem tal-kju

58
00:03:07,690 --> 00:03:11,160
hekk nafu liema element
irridu dequeue,

59
00:03:11,160 --> 00:03:15,070
u wkoll għandna bżonn li jżommu rekord ta '
xi ħaġa else---numru ta 'elementi

60
00:03:15,070 --> 00:03:16,690
li għandna fil-kju tagħna.

61
00:03:16,690 --> 00:03:19,360
Avviż aħna mhux qed iżżomm rekord
tal-aħħar tal-kju, just

62
00:03:19,360 --> 00:03:21,150
id-daqs tal-kju.

63
00:03:21,150 --> 00:03:24,310
U r-raġuni għal dik se nisperaw
issir daqsxejn aktar ċara fil-mument.

64
00:03:24,310 --> 00:03:26,143
Ladarba aħna temmew
din id-definizzjoni tat-tip,

65
00:03:26,143 --> 00:03:29,080
għandna tip ta 'dejta ġdida
imsejħa kju, li nistgħu issa

66
00:03:29,080 --> 00:03:30,630
tiddikjara varjabbli ta 'dak it-tip tad-data.

67
00:03:30,630 --> 00:03:35,350
U kemmxejn joħloq konfużjoni, stajt iddeċieda
biex sejħa dan kju q, l-ittra

68
00:03:35,350 --> 00:03:38,090
q minflok il-q tip ta 'data.

69
00:03:38,090 --> 00:03:39,600
>> Allura hawnhekk huwa kju tagħna.

70
00:03:39,600 --> 00:03:40,700
Hija struttura.

71
00:03:40,700 --> 00:03:45,730
Fiha tliet membri jew tlieta
oqsma, firxa ta 'KAPAĊITÀ daqs.

72
00:03:45,730 --> 00:03:47,340
F'dan il-każ, il-kapaċità hija 10.

73
00:03:47,340 --> 00:03:49,580
U dan array huwa
se jżommu interi.

74
00:03:49,580 --> 00:03:55,240
Fil ħadra hija l-quddiem tal-kju tagħna, il-
element jmiss li jitneħħew, u bl-aħmar

75
00:03:55,240 --> 00:03:58,610
se jkun id-daqs tal-kju,
kemm elementi bħalissa huma

76
00:03:58,610 --> 00:04:01,190
eżistenti fil-kju.

77
00:04:01,190 --> 00:04:05,300
Allura jekk aħna ngħidu ugwali q.front
0, u d-daqs q.size ugwali 0--

78
00:04:05,300 --> 00:04:07,120
aħna qed tqegħid 0s f'dawk l-oqsma.

79
00:04:07,120 --> 00:04:11,070
U f'dan il-punt, aħna qed pretty ħafna
lest li tibda taħdem ma kju tagħna.

80
00:04:11,070 --> 00:04:14,140
>> Allura l-ewwel operazzjoni nistgħu
tagħmel huwa li enqueue xi ħaġa,

81
00:04:14,140 --> 00:04:16,860
li żżid element ġdid li
l-aħħar tal-kju.

82
00:04:16,860 --> 00:04:19,089
Well dak li għandna bżonn biex
tagħmel fil-każ ġenerali?

83
00:04:19,089 --> 00:04:23,690
Ukoll din il-funzjoni enqueue bżonnijiet
li jaċċetta pointer li kju tagħna.

84
00:04:23,690 --> 00:04:26,370
Għal darb'oħra, jekk aħna kien iddikjara
kju tagħna globalment,

85
00:04:26,370 --> 00:04:29,490
aħna ma bżonn tagħmel dan
neċessarjament, iżda b'mod ġenerali, aħna

86
00:04:29,490 --> 00:04:32,330
bżonn li jaċċettaw pointers
li strutturi ta 'dejta

87
00:04:32,330 --> 00:04:35,040
bħal dan, għax inkella,
aħna qed tgħaddi minn value-- aħna qed

88
00:04:35,040 --> 00:04:38,140
tgħaddi kopji tal-kju,
u hekk aħna mhux qed attwalment qed jinbidlu

89
00:04:38,140 --> 00:04:41,050
-kju li għandna l-intenzjoni li jibdlu.

90
00:04:41,050 --> 00:04:44,860
>> Il-ħaġa oħra li teħtieġ li tagħmel huwa jaċċetta
element tad-data tat-tip xieraq.

91
00:04:44,860 --> 00:04:46,818
Għal darb'oħra, f'dan il-każ, huwa
se tkun interi,

92
00:04:46,818 --> 00:04:49,330
imma int tista arbitrarjament
tiddikjara t-tip tad-data kif valur

93
00:04:49,330 --> 00:04:51,160
u jużaw dan b'mod aktar ġenerali.

94
00:04:51,160 --> 00:04:56,030
Dik hija l-element li rridu enqueue,
irridu li żżid mal-aħħar tal-kju.

95
00:04:56,030 --> 00:04:58,573
Imbagħad aħna attwalment jridu
post li d-data fil-kju.

96
00:04:58,573 --> 00:05:01,490
F'dan il-każ, it-tqegħid tagħha fis-
post korretta tal array tagħna,

97
00:05:01,490 --> 00:05:05,040
u mbagħad irridu li jibdlu l-daqs
tal-kju, kemm elementi aħna

98
00:05:05,040 --> 00:05:07,050
bħalissa għandhom.

99
00:05:07,050 --> 00:05:07,990
>> Mela ejja tibda.

100
00:05:07,990 --> 00:05:10,890
Hawnhekk huwa, għal darb'oħra, li āenerali
Dikjarazzjoni funzjoni formola

101
00:05:10,890 --> 00:05:13,980
għal dak enqueue jista 'dehra.

102
00:05:13,980 --> 00:05:14,910
U here we go.

103
00:05:14,910 --> 00:05:18,335
Ejja enqueue-numru
28 fil-kju.

104
00:05:18,335 --> 00:05:19,460
Allura dak li aħna se jagħmlu?

105
00:05:19,460 --> 00:05:23,390
Ukoll, il-faċċata tal kju tagħna huwa
f'0, u d-daqs ta 'kju tagħna

106
00:05:23,390 --> 00:05:29,680
huwa ta '0, u hekk aħna probabilment tixtieq li tqiegħed
in-numru 28 fil-firxa numru element

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

108
00:05:31,124 --> 00:05:32,540
Allura konna issa imqiegħda li fil hemmhekk.

109
00:05:32,540 --> 00:05:34,820
Allura issa dak li għandna bżonn għall-bidla?

110
00:05:34,820 --> 00:05:37,090
Aħna ma jridux bidla
quddiem tal-kju,

111
00:05:37,090 --> 00:05:40,850
għaliex irridu li taf liema element
nistgħu bżonn li dequeue aktar tard.

112
00:05:40,850 --> 00:05:44,020
Allura r-raġuni għandna quddiem hemm
huwa tip ta 'indikatur ta' x'hemm

113
00:05:44,020 --> 00:05:46,439
l-eqdem ħaġa fil-firxa.

114
00:05:46,439 --> 00:05:49,730
Ukoll l-eqdem ħaġa fil-array-- fil
fatt, l-unika ħaġa fil-firxa dritt

115
00:05:49,730 --> 00:05:53,540
now-- huwa 28, li huwa
fil-post array 0.

116
00:05:53,540 --> 00:05:56,160
Allura aħna ma rridux li
bidla dak in-numru aħdar,

117
00:05:56,160 --> 00:05:57,910
minħabba li l-element eqdem.

118
00:05:57,910 --> 00:06:00,510
Pjuttost, irridu li jibdlu l-daqs.

119
00:06:00,510 --> 00:06:04,110
Allura f'dan il-każ, aħna ser
inkrement daqs għal 1.

120
00:06:04,110 --> 00:06:08,430
>> Issa tip ġenerali ta 'idea ta' fejn l-
element jmiss se jmorru fil-kju

121
00:06:08,430 --> 00:06:12,310
huwa li żżid dawn iż-żewġ numri
flimkien, quddiem u d-daqs,

122
00:06:12,310 --> 00:06:16,390
u li ser jgħidlek meta l-li jmiss
element fil-kju se jmorru.

123
00:06:16,390 --> 00:06:18,130
Allura issa ejja enqueue numru ieħor.

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

125
00:06:20,250 --> 00:06:24,480
Allura 33 huwa se jmorru fil
post array 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Allura f'dan il-każ, li għaddej
li jmorru fis lokazzjoni firxa 1,

127
00:06:26,840 --> 00:06:29,500
u issa d-daqs ta 'kju tagħna huwa ta' 2.

128
00:06:29,500 --> 00:06:31,840
>> Għal darb'oħra, aħna mhux qed jinbidlu
quddiem tal-kju tagħna,

129
00:06:31,840 --> 00:06:34,730
minħabba 28 għadu l-
eqdem element, u aħna

130
00:06:34,730 --> 00:06:38,220
tixtieq to-- meta aħna eventwalment jiksbu
li dequeuing, it-tneħħija elementi

131
00:06:38,220 --> 00:06:43,300
minn dan kju, li rridu nkunu nafu
fejn l-element eqdem hu.

132
00:06:43,300 --> 00:06:48,620
U hekk aħna dejjem bżonn li jinżamm
xi indikatur ta 'fejn dan huwa.

133
00:06:48,620 --> 00:06:50,410
Allura dak hu li l-0 qiegħed hemm għall.

134
00:06:50,410 --> 00:06:52,910
Dak hu quddiem huwa hemm għal.

135
00:06:52,910 --> 00:06:55,022
>> Ejja fil enqueue wieħed aktar element, 19.

136
00:06:55,022 --> 00:06:56,980
Jien ċert li inti tista 'raden
fejn 19 se jmorru.

137
00:06:56,980 --> 00:06:59,860
Li għaddej biex tmur fil
firxa numru lokazzjoni 2.

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

139
00:07:01,570 --> 00:07:03,199
U issa id-daqs ta 'kju tagħna huwa ta' 3.

140
00:07:03,199 --> 00:07:04,240
Aħna 3 elementi fiha.

141
00:07:04,240 --> 00:07:08,490
Hekk jekk konna biex, u aħna mhux qed tmur
li dritt issa, enqueue element ieħor,

142
00:07:08,490 --> 00:07:11,370
dan imur fis lokazzjoni firxa
numru 3, u d-daqs ta 'kju tagħna

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

144
00:07:13,160 --> 00:07:15,279
Allura konna enqueued diversi elementi issa.

145
00:07:15,279 --> 00:07:16,570
Issa ejja nibdew biex jitneħħew.

146
00:07:16,570 --> 00:07:19,450
Ejja dequeue minnhom mill-kju.

147
00:07:19,450 --> 00:07:23,340
>> Allura simili li pop, li huwa tip
tal-Analog ta 'dan għal stacks,

148
00:07:23,340 --> 00:07:26,180
dequeue jeħtieġ li taċċetta
pointer għall-queue-- mill-ġdid,

149
00:07:26,180 --> 00:07:28,140
sakemm huwa globalment iddikjarat.

150
00:07:28,140 --> 00:07:31,610
Issa rridu li jibdlu l-post
ta 'quddiem tal-kju.

151
00:07:31,610 --> 00:07:35,050
Dan huwa fejn tip ta 'niġu
fis-rwol, dak il-varjabbli ta 'quddiem,

152
00:07:35,050 --> 00:07:37,310
għaliex ladarba aħna tneħħi
element, irridu

153
00:07:37,310 --> 00:07:40,720
li jġorrhom għall-element li jmiss eqdem.

154
00:07:40,720 --> 00:07:44,180
>> Imbagħad irridu li jnaqqsu
id-daqs tal-kju,

155
00:07:44,180 --> 00:07:47,130
u allura aħna jridu jirritornaw il-valur
li tneħħa mill-kju.

156
00:07:47,130 --> 00:07:48,921
Għal darb'oħra, aħna ma jridux biss armiha.

157
00:07:48,921 --> 00:07:51,170
Aħna preżumibbilment huma estrazzjoni
mis-queue-- aħna qed

158
00:07:51,170 --> 00:07:54,170
dequeuing għaliex aħna kura dwar dan.

159
00:07:54,170 --> 00:08:01,080
Allura rridu din il-funzjoni li jirritornaw
element tad-data ta 'valur tip.

160
00:08:01,080 --> 00:08:04,360
Għal darb'oħra, f'dan il-każ, il-valur huwa numru sħiħ.

161
00:08:04,360 --> 00:08:05,670
>> Allura issa ejja dequeue xi ħaġa.

162
00:08:05,670 --> 00:08:09,310
Ejja neħħi element mill-kju.

163
00:08:09,310 --> 00:08:15,970
Jekk aħna ngħidu int x ugwali u q, ampersand q--
għal darb'oħra li l-pointer li din id-data q

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

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

166
00:08:23,840 --> 00:08:29,480
F'dan il-każ, għaliex hija l-ewwel
fl-ewwel out istruttura ta 'data, FIFO,

167
00:08:29,480 --> 00:08:33,690
l-ewwel ħaġa li għandna jitqiegħdu fis dan
kju kien 28, u għalhekk f'dan il-każ,

168
00:08:33,690 --> 00:08:37,245
aħna qed tmur biex tieħu 28 minn
-kju, mhux 19, li huwa dak

169
00:08:37,245 --> 00:08:38,870
aħna kien jagħmel kieku dan kien munzell.

170
00:08:38,870 --> 00:08:42,220
Aħna qed tmur biex tieħu 28 mill-kju.

171
00:08:42,220 --> 00:08:44,960
>> Simili għal dak li għamilna ma '
munzell, aħna mhux qed attwalment

172
00:08:44,960 --> 00:08:47,345
ser tħassar 28
mill-kju innifsu,

173
00:08:47,345 --> 00:08:49,470
aħna qed biss ser tip
ta nippretendu ma jkunx hemm.

174
00:08:49,470 --> 00:08:51,678
Allura li għaddej biex tibqa 'hemm
fil-memorja, imma aħna qed biss

175
00:08:51,678 --> 00:08:57,820
ser tip ta 'jinjoraha billi mexxew
iż-żewġ oqsma oħra ta 'data q tagħna

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

177
00:08:58,830 --> 00:09:00,230
Aħna ser jibdlu l-front.

178
00:09:00,230 --> 00:09:04,290
Q.front issa se
jkun 1, minħabba li issa huwa

179
00:09:04,290 --> 00:09:07,740
l-element eqdem għandna fil tagħna
kju, għaliex aħna stajt diġà tneħħiet 28,

180
00:09:07,740 --> 00:09:10,460
li kienet l-element ta 'qabel eqdem.

181
00:09:10,460 --> 00:09:13,540
>> U issa, aħna tixtieq li tibdel
id-daqs tal-kju

182
00:09:13,540 --> 00:09:15,780
għal żewġ elementi minflok tlieta.

183
00:09:15,780 --> 00:09:20,450
Issa ftakar qabel I said meta aħna
trid iżżid elementi għall-kju,

184
00:09:20,450 --> 00:09:26,000
aħna poġġih f'post firxa
li hija s-somma ta 'quddiem u d-daqs.

185
00:09:26,000 --> 00:09:29,050
Allura f'dan il-każ, aħna qed għadhom tqegħid
dan, l-element li jmiss fil-kju,

186
00:09:29,050 --> 00:09:33,360
fis lokazzjoni firxa 3, u
Ser naraw li fit-tieni.

187
00:09:33,360 --> 00:09:35,730
>> Allura aħna issa stajt dequeued tagħna
ewwel element mill-kju.

188
00:09:35,730 --> 00:09:36,480
Ejja nagħmlu dan mill-ġdid.

189
00:09:36,480 --> 00:09:38,696
Ejja neħħi ieħor
element mill-kju.

190
00:09:38,696 --> 00:09:42,400
Fil-każ, l-kurrent eqdem
element huwa post array 1.

191
00:09:42,400 --> 00:09:44,220
Dak hu li q.front tgħidilna.

192
00:09:44,220 --> 00:09:46,980
Li l-kaxxa ħadra tgħidilna li
dak l-element eqdem.

193
00:09:46,980 --> 00:09:49,310
U għalhekk, x se jsiru 33.

194
00:09:49,310 --> 00:09:52,130
Aħna ser biss tip ta 'ninsew
li 33 teżisti fil-firxa,

195
00:09:52,130 --> 00:09:55,100
u aħna ser ngħidu li issa, l-
element ġdid eqdem fil-kju

196
00:09:55,100 --> 00:09:58,900
huwa fil-post array 2, u d-daqs
tal-kju, in-numru ta 'elementi

197
00:09:58,900 --> 00:10:02,152
għandna fil-kju, huwa 1.

198
00:10:02,152 --> 00:10:05,110
Issa ejja enqueue xi ħaġa, u I
tip ta 'taw din bogħod tieni ilu,

199
00:10:05,110 --> 00:10:10,340
imma jekk irridu li tqiegħed 40 fil-
kju, fejn s-40 se jmorru?

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

201
00:10:12,880 --> 00:10:17,730
Well we kont qed tqegħid
fil q.front plus kju daqs,

202
00:10:17,730 --> 00:10:20,850
u għalhekk jagħmel sens li
fil-fatt li jpoġġu 40 hawn.

203
00:10:20,850 --> 00:10:22,840
Issa avviż li fil
F'xi punt, aħna qed tmur

204
00:10:22,840 --> 00:10:27,980
biex jiksbu l-aħħar ta '
firxa tagħna ġewwa tal q,

205
00:10:27,980 --> 00:10:32,010
iżda li faded out 28 u 33--
dawn qed attwalment, teknikament

206
00:10:32,010 --> 00:10:33,300
spazji miftuħa, id-dritt?

207
00:10:33,300 --> 00:10:36,040
U hekk, aħna jistgħu eventually--
din ir-regola ta 'żżid

208
00:10:36,040 --> 00:10:40,390
dawn iż-żewġ together-- nistgħu eventwalment
jeħtieġ li mod mid-daqs tal-kapaċità

209
00:10:40,390 --> 00:10:41,410
hekk nistgħu wrap madwar.

210
00:10:41,410 --> 00:10:43,620
>> Hekk jekk irridu jiksbu l-element
numru 10, jekk aħna qed

211
00:10:43,620 --> 00:10:48,790
jissostitwixxih fil element numru 10, aħna'd
attwalment tqiegħed fil-post array 0.

212
00:10:48,790 --> 00:10:50,997
U jekk konna se
firxa location-- skuża me,

213
00:10:50,997 --> 00:10:53,080
jekk aħna miżjud up flimkien,
u aħna ltqajna biex numru

214
00:10:53,080 --> 00:10:56,330
11 Ikun fejn rridu naraw li jpoġġi
dan, li ma teżistix f'dan il array--

215
00:10:56,330 --> 00:10:58,200
ikun għaddej minn limiti.

216
00:10:58,200 --> 00:11:03,367
Nistgħu Mod b'10 u mqiegħda
għalih fil-post array 1.

217
00:11:03,367 --> 00:11:04,450
Allura li kif kjuwijiet jaħdmu.

218
00:11:04,450 --> 00:11:08,540
Huma qed dejjem se jmorru minn fuq ix-xellug
għal-lemin u possibilment around.

219
00:11:08,540 --> 00:11:11,280
U inti taf li dawn qed
sħiħ jekk id-daqs, li l-kaxxa aħmar,

220
00:11:11,280 --> 00:11:13,710
isir ugwali għal kapaċità.

221
00:11:13,710 --> 00:11:16,720
U hekk wara konna miżjud 40 sa l-
kju, sew dak li rridu nagħmlu?

222
00:11:16,720 --> 00:11:19,890
Ukoll, l-element eqdem
fil-kju għadu 19,

223
00:11:19,890 --> 00:11:21,990
hekk aħna ma jridux bidla
quddiem tal-kju,

224
00:11:21,990 --> 00:11:23,820
iżda issa għandna żewġ
elementi fil-kju,

225
00:11:23,820 --> 00:11:28,710
u hekk aħna tixtieq li jiżdied
daqs tagħna 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Li pretty ħafna ma '
ħidma ma kjuwijiet bbażati fuq array,

227
00:11:31,820 --> 00:11:33,630
u simili munzell,
hemm ukoll mod

228
00:11:33,630 --> 00:11:36,450
biex timplimenta kju bħala lista marbuta.

229
00:11:36,450 --> 00:11:40,150
Issa jekk dan it-tip istruttura tad-data
jistenna familjari għalik, huwa.

230
00:11:40,150 --> 00:11:43,780
Mhuwiex lista marbuta waħdu,
huwa lista marbuta doppjament.

231
00:11:43,780 --> 00:11:46,790
U issa, bħala twarrib, huwa
fil-fatt possibbli li jiġu implimentati

232
00:11:46,790 --> 00:11:50,160
kju bħala lista marbuta waħdu, iżda
I jaħsbu f'termini ta viżwalizzazzjoni,

233
00:11:50,160 --> 00:11:53,350
fil-fatt tista 'tgħin biex tara
dan bħala lista marbuta doppjament.

234
00:11:53,350 --> 00:11:56,850
Iżda huwa definittivament possibbli li
tagħmel dan bħala lista marbuta weħidhom.

235
00:11:56,850 --> 00:12:00,110
>> Mela ejja jkollhom ħarsa lejn
dak li dan jista 'dehra.

236
00:12:00,110 --> 00:12:02,750
Jekk irridu li enquue--
hekk issa, għal darb'oħra aħna qed

237
00:12:02,750 --> 00:12:05,360
jaqilbu għal-lista marbuta
mudell ibbażat hawn.

238
00:12:05,360 --> 00:12:08,420
Jekk irridu li enqueue, irridu
li żżid element ġdid, sew

239
00:12:08,420 --> 00:12:09,730
dak li rridu nagħmlu?

240
00:12:09,730 --> 00:12:12,770
Ukoll, qabel kollox, għaliex
aħna qed jżid mal-aħħar

241
00:12:12,770 --> 00:12:15,520
u t-tneħħija mill-
bidu, aħna probabbilment

242
00:12:15,520 --> 00:12:20,050
tixtieq li tinżamm pointers kemm lill-
ras u d-denb tal-lista marbuta?

243
00:12:20,050 --> 00:12:22,660
Denb jkunu għal perijodu ieħor għal
l-aħħar tal-lista marbuta,

244
00:12:22,660 --> 00:12:24,496
l-aħħar element fil-lista marbuta.

245
00:12:24,496 --> 00:12:26,620
U dawn se probabbilment,
għal darb'oħra, tkun ta 'benefiċċju għalina

246
00:12:26,620 --> 00:12:28,477
jekk huma varjabbli globali.

247
00:12:28,477 --> 00:12:31,060
Imma issa jekk irridu li żżid ġdida
element dak li għandna nagħmlu?

248
00:12:31,060 --> 00:12:35,262
Dak li aħna biss [? Malak?] jew dinamikament
jallokaw node ġdid tagħna għalina.

249
00:12:35,262 --> 00:12:38,220
U mbagħad, biss bħal meta aħna żid xi
element għal lista marbuta doppjament aħna,

250
00:12:38,220 --> 00:12:40,410
sempliċiment għandek issolvi of--
dawk aħħar tliet passi hawn

251
00:12:40,410 --> 00:12:43,330
huma biss kollha dwar jiċċaqilqu l-
pointers fil-mod korrett

252
00:12:43,330 --> 00:12:46,710
sabiex l-element gets miżjuda mal
il-katina mingħajr ma jitkissru l-katina

253
00:12:46,710 --> 00:12:49,580
jew jagħmlu xi tip ta 'żball
jew li xi tip ta 'inċident

254
00:12:49,580 --> 00:12:54,505
jiġri li biha aħna aċċidentalment
orfni xi elementi ta 'kju tagħna.

255
00:12:54,505 --> 00:12:55,880
Hawn dak li dan jista 'dehra.

256
00:12:55,880 --> 00:13:00,980
Aħna rridu li jżidu l-element
10 sa l-aħħar ta 'din kju.

257
00:13:00,980 --> 00:13:03,380
Allura l-element eqdem hawn
hija rappreżentata minn ras.

258
00:13:03,380 --> 00:13:06,800
Dik hija l-ewwel ħaġa li nitfgħu
fis dan kju ipotetiku hawnhekk.

259
00:13:06,800 --> 00:13:10,430
U denb, 13, huwa l-aktar
element miżjuda riċentament.

260
00:13:10,430 --> 00:13:17,030
U hekk jekk irridu li enqueue 10 fis
dan kju, irridu li tqiegħed lilha wara 13.

261
00:13:17,030 --> 00:13:19,860
U hekk aħna qed tmur biex dinamikament
jalloka territorju għal node ġdid

262
00:13:19,860 --> 00:13:23,280
u ċċekkja għall null biex tiżgura
aħna ma jkollhomx nuqqas memorja.

263
00:13:23,280 --> 00:13:27,040
Allura aħna qed tmur biex
introduċi 10 f'dak node,

264
00:13:27,040 --> 00:13:30,030
u issa għandna bżonn li tkun attenta
dwar kif norganizzaw pointers

265
00:13:30,030 --> 00:13:32,180
hekk aħna ma jqassmux il-katina.

266
00:13:32,180 --> 00:13:38,910
>> Nistgħu stabbilit 10 ta qasam preċedenti
għall-punt lura għall-denb qodma,

267
00:13:38,910 --> 00:13:41,620
u peress '10 se tkun l-
denb ġdid f'xi punt

268
00:13:41,620 --> 00:13:44,459
mill-ħin dawn kollha
ktajjen huma konnessi,

269
00:13:44,459 --> 00:13:46,250
xejn għaddej biex jiġu
wara 10 dritt issa.

270
00:13:46,250 --> 00:13:49,880
U hekk 10 ta pointer li jmiss
se jindika null,

271
00:13:49,880 --> 00:13:53,580
u mbagħad wara nagħmlu dan, wara konna
konnessi 10 lura għall-katina,

272
00:13:53,580 --> 00:13:57,780
nistgħu nieħdu l-kap qodma, jew, skuża
me,-denb antika tal-kju.

273
00:13:57,780 --> 00:14:02,980
It-tmiem antika tal-kju,
13, u jagħmluha punt sa 10.

274
00:14:02,980 --> 00:14:08,220
U issa, f'dan il-punt, għandna
enqueued-numru 10 fis dan kju.

275
00:14:08,220 --> 00:14:14,740
Kollha għandna bżonn tagħmel issa huwa biss jċaqalqu l-
denb għall-punt 10 minflok sa 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing huwa attwalment
simili ħafna għall popping

277
00:14:17,630 --> 00:14:21,710
minn munzell li hija
implimentati bħala lista marbuta

278
00:14:21,710 --> 00:14:24,040
jekk inti stajt tidher l-video stacks.

279
00:14:24,040 --> 00:14:27,280
Kollha għandna bżonn tagħmel hu li tibda fil-
bidu, isibu t-tieni element,

280
00:14:27,280 --> 00:14:30,480
ħielsa l-ewwel element,
u mbagħad jimxu l-kap

281
00:14:30,480 --> 00:14:32,930
għall-punt li t-tieni element.

282
00:14:32,930 --> 00:14:37,920
Probabbilment aħjar li Ħares lilha
biss sabiex ikunu extra ċara dwar dan.

283
00:14:37,920 --> 00:14:39,230
Allura hawnhekk kju tagħna għal darb'oħra.

284
00:14:39,230 --> 00:14:42,600
12 huwa l-element eqdem
fil-kju tagħna, il-kap.

285
00:14:42,600 --> 00:14:46,210
10 huwa l-element l-aktar ġodda
fil-kju tagħna, denb tagħna.

286
00:14:46,210 --> 00:14:49,310
>> U hekk meta rridu
li dequeue element,

287
00:14:49,310 --> 00:14:52,202
irridu li tneħħi l-element eqdem.

288
00:14:52,202 --> 00:14:52,910
Allura dak li nagħmlu?

289
00:14:52,910 --> 00:14:55,243
Well waqqafna pointer traversal
li jibda fil-ras,

290
00:14:55,243 --> 00:14:57,840
u nimxu hekk li
Jinnota t-tieni element

291
00:14:57,840 --> 00:15:02,290
ta 'dan queue-- xi ħaġa billi qal trav
ugwali trav vleġġa li jmiss, per eżempju,

292
00:15:02,290 --> 00:15:07,170
se jimxu trav hemm għall-punt li
15, li, wara we dequeue 12,

293
00:15:07,170 --> 00:15:13,030
jew wara we tneħħi 12, se
jsiru l-element mbagħad-eqdem.

294
00:15:13,030 --> 00:15:16,360
>> Issa konna ltqajna istiva fuq l-ewwel
element permezz tal-kap pointer

295
00:15:16,360 --> 00:15:19,440
u t-tieni element
permezz tal-trav pointer.

296
00:15:19,440 --> 00:15:25,170
Nistgħu ras issa ħielsa, u mbagħad nistgħu
jgħidu ma joħroġ xejn qabel il-15 aktar.

297
00:15:25,170 --> 00:15:29,990
Allura nistgħu nbiddlu 15 ta 'qabel
pointer għall-punt li nulla,

298
00:15:29,990 --> 00:15:31,874
u aħna biss jiċċaqalqu l fuq ras.

299
00:15:31,874 --> 00:15:32,540
U hemm immorru.

300
00:15:32,540 --> 00:15:35,840
Issa aħna rnexxielna
dequeued 12, u issa aħna

301
00:15:35,840 --> 00:15:39,180
jkollhom kju ieħor ta '4 elementi.

302
00:15:39,180 --> 00:15:41,700
Li pretty ħafna kollha
hemm li jkunu kjuwijiet,

303
00:15:41,700 --> 00:15:45,810
tnejn li huma bbażati bbażati fuq firxa u marbuta mal-lista.

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

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

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