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

2
00:00:05,204 --> 00:00:07,370
DOUG Lloyd: Pra, nëse ju keni
shikuar video në rafte,

3
00:00:07,370 --> 00:00:09,870
kjo është ndoshta do të ndihen
si një pak e deja vu.

4
00:00:09,870 --> 00:00:13,850
Është duke shkuar në një koncept shumë të ngjashme,
vetëm me një kthesë të vogël në të.

5
00:00:13,850 --> 00:00:15,530
Ne do të flasim tani për rradhë.

6
00:00:15,530 --> 00:00:19,350
Pra, një radhë, të ngjashme me një pirg,
është një tjetër lloj i strukturës së të dhënave

7
00:00:19,350 --> 00:00:22,412
që ne mund të përdorim për të ruajtur
të dhënat në mënyrë të organizuar.

8
00:00:22,412 --> 00:00:24,120
Ngjashëm me një pirg,
kjo mund të realizohet

9
00:00:24,120 --> 00:00:27,000
si një grup ose një listë e lidhur.

10
00:00:27,000 --> 00:00:30,320
Ndryshe nga një pirg, rregullat
që ne përdorim për të përcaktuar

11
00:00:30,320 --> 00:00:34,210
kur gjërat merrni shtuar dhe hequr nga
një radhë janë pak të ndryshme.

12
00:00:34,210 --> 00:00:36,590
>> Ndryshe nga një pirg, e cila
është një strukturë LIFO,

13
00:00:36,590 --> 00:00:45,610
zgjasë në, nga e para, një radhë është një FIFO
Struktura, FIFO, së pari në, nga e para.

14
00:00:45,610 --> 00:00:49,320
Tani rradhë, ju ndoshta
kanë një analogji me rradhë.

15
00:00:49,320 --> 00:00:52,820
Nëse ju keni qenë ndonjëherë në përputhje me
një amusement park ose në një bankë,

16
00:00:52,820 --> 00:00:56,430
nuk është lloj i një drejtësisë
zbatimin e strukturës.

17
00:00:56,430 --> 00:00:59,160
Personi i parë në përputhje me
banka është personi i parë

18
00:00:59,160 --> 00:01:00,760
i cili merr për të folur me tregimtar.

19
00:01:00,760 --> 00:01:03,522
>> Ajo do të jetë lloj i një gare
në fund, nëse e vetmja mënyrë

20
00:01:03,522 --> 00:01:06,730
ju mori për të folur me tregimtar më së
banka do të ishte personi i fundit në linjë.

21
00:01:06,730 --> 00:01:09,146
Gjithkush do të duan gjithmonë
të jetë personi i fundit në linjë:

22
00:01:09,146 --> 00:01:12,580
dhe personi i cili ishte atje në fillim
i cili ka qenë duke pritur për një kohë,

23
00:01:12,580 --> 00:01:14,715
mund të jetë atje për orë të tëra,
dhe orë dhe orë

24
00:01:14,715 --> 00:01:17,590
para se ata kanë një shans për të vërtetë
tërheqë ndonjë para në bankë.

25
00:01:17,590 --> 00:01:22,510
Dhe kështu radhët e gjata janë lloj i
ndershmërisë zbatimin e strukturës.

26
00:01:22,510 --> 00:01:25,780
Por kjo nuk do të thotë
se oxhaqet janë një gjë e keqe, vetëm

27
00:01:25,780 --> 00:01:28,160
se radhët e gjata janë një mënyrë për të bërë atë.

28
00:01:28,160 --> 00:01:32,420
Pra, përsëri një radhë është i pari në, së pari
jashtë, kundrejt një pirg i cili zgjatë në,

29
00:01:32,420 --> 00:01:34,440
për herë të parë jashtë.

30
00:01:34,440 --> 00:01:36,190
Ngjashëm me një pirg,
ne kemi dy operacione

31
00:01:36,190 --> 00:01:38,470
që ne mund të kryejnë në radhët e gjata.

32
00:01:38,470 --> 00:01:43,910
Emrat janë enqueue, e cila është për të shtuar
një element i ri në fund të radhë,

33
00:01:43,910 --> 00:01:47,330
dhe dequeue, i cili është
për të hequr më i vjetër

34
00:01:47,330 --> 00:01:49,670
element nga frontin e radhë.

35
00:01:49,670 --> 00:01:53,600
Pra, ne jemi duke shkuar për të shtuar elemente të
në fund të radhë,

36
00:01:53,600 --> 00:01:57,220
dhe ne jemi duke shkuar për të hequr elementet
nga frontin e radhë.

37
00:01:57,220 --> 00:02:00,790
Përsëri, me rafte, ne ishim duke shtuar
elemente majë të pirg

38
00:02:00,790 --> 00:02:03,380
dhe elementët largimin
nga maja e pirg.

39
00:02:03,380 --> 00:02:07,570
Pra me enqueue, ajo është shtuar në
në fund, duke hequr nga e para.

40
00:02:07,570 --> 00:02:10,639
Pra, gjëja e vjetër në atje
është gjithmonë gjë tjetër

41
00:02:10,639 --> 00:02:13,620
për të dalë nëse ne përpiqemi
dhe dequeue diçka.

42
00:02:13,620 --> 00:02:18,330
>> Pra, përsëri, me rradhë, ne mund të
Implementimi array-bazuar

43
00:02:18,330 --> 00:02:20,110
dhe lidhur-lista Implementimi i bazuar.

44
00:02:20,110 --> 00:02:24,620
Ne do të fillojë përsëri me
array-bazuar Implementimi.

45
00:02:24,620 --> 00:02:27,070
Struktura Përkufizimi
duket goxha i ngjashëm.

46
00:02:27,070 --> 00:02:30,720
Ne kemi një tjetër rrjet
nuk e vlerës së të dhënave tipit,

47
00:02:30,720 --> 00:02:32,690
kështu që ai mund të mbajë lloje të të dhënave arbitrare.

48
00:02:32,690 --> 00:02:35,570
Ne jemi duke shkuar për të përdorur përsëri
integers në këtë shembull.

49
00:02:35,570 --> 00:02:39,830
>> Dhe ashtu si me tonë
Zbatimi rafte array-bazë,

50
00:02:39,830 --> 00:02:42,340
sepse ne jemi duke përdorur një
grup, ne domosdo

51
00:02:42,340 --> 00:02:46,850
kanë atë kufizim që lloji C
i zbaton mbi ne, i cili është ne

52
00:02:46,850 --> 00:02:51,670
nuk kanë ndonjë dinamizëm në tonë
aftësia për të rritet dhe tkurret array.

53
00:02:51,670 --> 00:02:55,710
Ne duhet të vendosin në fillim
çfarë është numri maksimal i gjërave

54
00:02:55,710 --> 00:02:59,300
që ne mund të vënë në këtë
radhë, dhe në këtë rast,

55
00:02:59,300 --> 00:03:02,070
Kapaciteti do të ketë disa kile
përkufizuar konstante në kodin tonë.

56
00:03:02,070 --> 00:03:05,430
Dhe për qëllime të këtij
Video, kapaciteti do të jetë 10.

57
00:03:05,430 --> 00:03:07,690
>> Ne duhet të mbajnë gjurmët e
e përparme e radhë

58
00:03:07,690 --> 00:03:11,160
kështu që ne e dimë që elementi
ne duam të dequeue,

59
00:03:11,160 --> 00:03:15,070
dhe ne gjithashtu duhet të mbajnë gjurmët e
diçka else-- numrin e elementeve

60
00:03:15,070 --> 00:03:16,690
që ne kemi në radhë tonë.

61
00:03:16,690 --> 00:03:19,360
Vini re ne nuk jemi mbajtja
në fund të radhë, vetëm

62
00:03:19,360 --> 00:03:21,150
madhësia e radhë.

63
00:03:21,150 --> 00:03:24,310
Dhe arsyeja për këtë do të shpresojmë se
të bëhet një pak më të qartë në një moment.

64
00:03:24,310 --> 00:03:26,143
Pasi ne kemi përfunduar
ky përkufizim lloj,

65
00:03:26,143 --> 00:03:29,080
ne kemi një lloj të ri të dhënave
quajtur radhë, të cilat ne mund të tani

66
00:03:29,080 --> 00:03:30,630
deklarojnë variablave të atij lloji të dhënave.

67
00:03:30,630 --> 00:03:35,350
Dhe disi çudi, unë kam vendosur
për të thirrur këtë q radhë, letra

68
00:03:35,350 --> 00:03:38,090
q në vend të tipit të dhënave q.

69
00:03:38,090 --> 00:03:39,600
>> Kështu që këtu është radhë ynë.

70
00:03:39,600 --> 00:03:40,700
Kjo është një strukturë.

71
00:03:40,700 --> 00:03:45,730
Ajo përmban tre anëtarë apo tre
fusha, një grup prej madhësisë kapacitetit.

72
00:03:45,730 --> 00:03:47,340
Në këtë rast, kapaciteti është 10.

73
00:03:47,340 --> 00:03:49,580
Dhe kjo grup është
do të mbajë integers.

74
00:03:49,580 --> 00:03:55,240
Në gjelbër është front i radhë tonë,
element tjetër për të hequr, dhe në të kuqe

75
00:03:55,240 --> 00:03:58,610
do të jetë madhësia e radhë,
Sa elemente janë aktualisht

76
00:03:58,610 --> 00:04:01,190
ekzistuese në radhë.

77
00:04:01,190 --> 00:04:05,300
Pra, nëse ne themi barabartë q.front
0, dhe madhësia q.size barabartë 0--

78
00:04:05,300 --> 00:04:07,120
ne jemi duke 0s në këto fusha.

79
00:04:07,120 --> 00:04:11,070
Dhe në këtë pikë, ne jemi shumë e shumë
gati për të filluar punën me radhë tonë.

80
00:04:11,070 --> 00:04:14,140
>> Pra, operacioni i parë që ne mund të
kryejnë është të enqueue diçka,

81
00:04:14,140 --> 00:04:16,860
për të shtuar një element të ri për
fundi i radhë.

82
00:04:16,860 --> 00:04:19,089
E pra çfarë kemi nevojë për të
të bëjë në rastin e përgjithshme?

83
00:04:19,089 --> 00:04:23,690
E pra ky funksion enqueue nevojat
të pranojë një tregues për radhë tonë.

84
00:04:23,690 --> 00:04:26,370
Përsëri, në qoftë se ne e kishte deklaruar
radhë tona globalisht,

85
00:04:26,370 --> 00:04:29,490
ne nuk do të ketë nevojë për të bërë këtë
domosdoshmërisht, por në përgjithësi, ne

86
00:04:29,490 --> 00:04:32,330
duhet të pranojnë pointers
në strukturat e të dhënave

87
00:04:32,330 --> 00:04:35,040
si kjo, sepse përndryshe,
ne jemi duke kaluar nga value-- ne jemi

88
00:04:35,040 --> 00:04:38,140
duke kaluar në kopje të radhë,
dhe kështu ne nuk jemi të vërtetë ndryshuar

89
00:04:38,140 --> 00:04:41,050
radhë që ne kemi ndërmend të ndryshojë.

90
00:04:41,050 --> 00:04:44,860
>> Gjë tjetër që duhet të bëni është të pranojë
një element të dhënat e llojit të përshtatshme.

91
00:04:44,860 --> 00:04:46,818
Përsëri, në këtë rast, është
do të jetë e integers,

92
00:04:46,818 --> 00:04:49,330
por ju mund të në mënyrë arbitrare
të deklarojë llojin e të dhënave si vlerë

93
00:04:49,330 --> 00:04:51,160
dhe të përdorin këtë në përgjithësi.

94
00:04:51,160 --> 00:04:56,030
Ky është elementi që ne duam të enqueue,
ne duam për të shtuar në fund të rreshtit.

95
00:04:56,030 --> 00:04:58,573
Pastaj ne të vërtetë duan të
vendosni se të dhënat në radhë.

96
00:04:58,573 --> 00:05:01,490
Në këtë rast, duke e vendosur atë në
vendndodhja e saktë e array tonë,

97
00:05:01,490 --> 00:05:05,040
dhe pastaj ne duam të ndryshojmë madhësinë
e radhë, sa elemente ne

98
00:05:05,040 --> 00:05:07,050
aktualisht kanë.

99
00:05:07,050 --> 00:05:07,990
>> Pra, le të ketë filluar.

100
00:05:07,990 --> 00:05:10,890
Këtu është, përsëri, se i përgjithshëm
deklaratë funksion formë

101
00:05:10,890 --> 00:05:13,980
për atë që enqueue mund të duket si.

102
00:05:13,980 --> 00:05:14,910
Dhe këtu ne do të shkojmë.

103
00:05:14,910 --> 00:05:18,335
Le të enqueue numrin
28 në radhë.

104
00:05:18,335 --> 00:05:19,460
Pra, çfarë do të shkojmë të bëjmë?

105
00:05:19,460 --> 00:05:23,390
E pra, para së radhës tonë është
në 0, dhe madhësia e radhës tonë

106
00:05:23,390 --> 00:05:29,680
është në 0, dhe kështu që ne ndoshta dëshironi të vënë
numri 28 në array numër element

107
00:05:29,680 --> 00:05:31,124
0, e drejtë?

108
00:05:31,124 --> 00:05:32,540
Pra, ne kemi vendosur tani se në atje.

109
00:05:32,540 --> 00:05:34,820
Kështu që tani ajo që nuk kemi nevojë për të ndryshuar?

110
00:05:34,820 --> 00:05:37,090
Ne nuk duam të ndryshojmë
e përparme e radhë,

111
00:05:37,090 --> 00:05:40,850
sepse ne duam të dimë se çfarë element
ne mund të kenë nevojë për të dequeue më vonë.

112
00:05:40,850 --> 00:05:44,020
Pra, arsyeja që ne kemi front atje
është lloj i një tregues i asaj që është

113
00:05:44,020 --> 00:05:46,439
gjëja më i vjetër në rrjet.

114
00:05:46,439 --> 00:05:49,730
E pra gjëja më i vjetër në array-- në
fakt, e vetmja gjë në rrjet e drejtë

115
00:05:49,730 --> 00:05:53,540
tani, është 28, i cili është
në array vend të 0.

116
00:05:53,540 --> 00:05:56,160
Pra, ne nuk duam të
ndryshojë këtë numër të gjelbër,

117
00:05:56,160 --> 00:05:57,910
sepse kjo është elementi më i vjetër.

118
00:05:57,910 --> 00:06:00,510
Përkundrazi, ne duam të ndryshojmë madhësinë.

119
00:06:00,510 --> 00:06:04,110
Pra, në këtë rast, ne do të
ardhura madhësinë në 1.

120
00:06:04,110 --> 00:06:08,430
>> Tani një lloj i përgjithshëm i idesë së, ku
element tjetër do të shkojë në radhë

121
00:06:08,430 --> 00:06:12,310
është për të shtuar këto dy numra
së bashku, para dhe madhësia,

122
00:06:12,310 --> 00:06:16,390
dhe që do të ju tregojnë se ku tjetër
element në radhë do të shkojë.

123
00:06:16,390 --> 00:06:18,130
Pra, tani le të enqueue një numër tjetër.

124
00:06:18,130 --> 00:06:20,250
Le të enqueue 33.

125
00:06:20,250 --> 00:06:24,480
Pra, 33 do të shkojë në
array vendndodhjen 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Pra, në këtë rast, ajo do
për të shkuar në array lokacioni 1,

127
00:06:26,840 --> 00:06:29,500
dhe tani madhësia e radhës tonë është 2.

128
00:06:29,500 --> 00:06:31,840
>> Përsëri, ne nuk jemi duke ndryshuar
pjesa e përparme e radhë sonë,

129
00:06:31,840 --> 00:06:34,730
sepse 28 është ende
element i vjetër, dhe ne

130
00:06:34,730 --> 00:06:38,220
dua to-- kur ne përfundimisht të merrni
të dequeuing, duke hequr elemente

131
00:06:38,220 --> 00:06:43,300
nga kjo radhë, ne duam të dimë
ku elementi më i vjetër është.

132
00:06:43,300 --> 00:06:48,620
Dhe kështu që ne gjithmonë duhet të ruajë
disa tregues se ku është.

133
00:06:48,620 --> 00:06:50,410
Pra, kjo është ajo që është atje për 0.

134
00:06:50,410 --> 00:06:52,910
Kjo është ajo që është atje për front.

135
00:06:52,910 --> 00:06:55,022
>> Le në enqueue një element më shumë, 19.

136
00:06:55,022 --> 00:06:56,980
Unë jam i sigurt që ju mund të me mend
ku 19 do të shkojë.

137
00:06:56,980 --> 00:06:59,860
Ajo do të shkojë në
Grup lokacioni numër 2.

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

139
00:07:01,570 --> 00:07:03,199
Dhe tani madhësia e radhës tonë është 3.

140
00:07:03,199 --> 00:07:04,240
Ne kemi 3 elemente në të.

141
00:07:04,240 --> 00:07:08,490
Pra, nëse ne do të, dhe ne nuk jemi duke shkuar
për tani, enqueue një element tjetër,

142
00:07:08,490 --> 00:07:11,370
ai do të shkojë në vend array
numër 3, dhe madhësia e radhës tonë

143
00:07:11,370 --> 00:07:13,160
do të jetë 4.

144
00:07:13,160 --> 00:07:15,279
Pra, ne kemi enqueued disa elemente tani.

145
00:07:15,279 --> 00:07:16,570
Tani le të fillojë për të hequr ato.

146
00:07:16,570 --> 00:07:19,450
Le dequeue ato nga radhë.

147
00:07:19,450 --> 00:07:23,340
>> Pra, të ngjashme me pop, e cila është lloj
i analogut te ky për kollonat,

148
00:07:23,340 --> 00:07:26,180
dequeue duhet të pranojë një
tregues të queue-- përsëri,

149
00:07:26,180 --> 00:07:28,140
përveç nëse është e deklaruar në nivel global.

150
00:07:28,140 --> 00:07:31,610
Tani ne duam të ndryshojmë vendndodhjen
i frontin e radhë.

151
00:07:31,610 --> 00:07:35,050
Kjo është ku ai lloj i vjen
në lojë, se ndryshueshme front,

152
00:07:35,050 --> 00:07:37,310
sepse sapo kemi hequr
një element, ne duam

153
00:07:37,310 --> 00:07:40,720
për të lëvizur atë që elementi i vjetër tjeter.

154
00:07:40,720 --> 00:07:44,180
>> Atëherë ne duam që të ulet
madhësia e radhë,

155
00:07:44,180 --> 00:07:47,130
dhe pastaj ne duam të kthehen vlerën
që u hoq nga radhë.

156
00:07:47,130 --> 00:07:48,921
Përsëri, ne nuk duam të vetëm hidhni atë.

157
00:07:48,921 --> 00:07:51,170
Ne me sa duket jemi të nxjerrë
ajo nga queue-- ne jemi

158
00:07:51,170 --> 00:07:54,170
dequeuing atë, sepse ne kujdesemi për të.

159
00:07:54,170 --> 00:08:01,080
Pra, ne duam që ky funksion të kthehen
një element të dhëna me vlerë të tipit.

160
00:08:01,080 --> 00:08:04,360
Përsëri, në këtë rast, vlera është numër i plotë.

161
00:08:04,360 --> 00:08:05,670
>> Pra, tani le të dequeue diçka.

162
00:08:05,670 --> 00:08:09,310
Le të hequr një element nga radhë.

163
00:08:09,310 --> 00:08:15,970
Nëse themi int x është e barabartë dhe q, simbol q--
përsëri kjo është një tregues për këto të dhëna q

164
00:08:15,970 --> 00:08:20,177
structure-- çfarë element
do të jetë dequeued?

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

166
00:08:23,840 --> 00:08:29,480
Në këtë rast, sepse kjo është një e parë
në, së pari jashtë strukturën e të dhënave, FIFO,

167
00:08:29,480 --> 00:08:33,690
gjëja e parë që ne kemi vënë në këtë
radhë ishte 28, dhe kështu që në këtë rast,

168
00:08:33,690 --> 00:08:37,245
ne jemi duke shkuar për të marrë 28 nga
radhë, jo 19, e cila është ajo

169
00:08:37,245 --> 00:08:38,870
ne do të kishte bërë nëse kjo ishte një pirg.

170
00:08:38,870 --> 00:08:42,220
Ne jemi duke shkuar për të marrë 28 nga radhë.

171
00:08:42,220 --> 00:08:44,960
>> Ngjashme me atë që ne e bëmë me
një pirg, ne nuk jemi në fakt

172
00:08:44,960 --> 00:08:47,345
do të fshini 28
nga radhë vetë,

173
00:08:47,345 --> 00:08:49,470
ne jemi vetëm duke shkuar për të llojit
të pretendojë se nuk është atje.

174
00:08:49,470 --> 00:08:51,678
Kështu ajo do të qëndrojë atje
në kujtesë, por ne jemi vetëm

175
00:08:51,678 --> 00:08:57,820
duke shkuar për të lloj të injorojë atë duke lëvizur
dy fusha të tjera të të dhënave tona q

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

177
00:08:58,830 --> 00:09:00,230
Ne jemi duke shkuar për të ndryshuar para.

178
00:09:00,230 --> 00:09:04,290
Q.front tani është duke shkuar për
të jetë 1, sepse kjo është tani

179
00:09:04,290 --> 00:09:07,740
elementi më i vjetër që kemi në tonë
radhë, sepse ne kemi hequr tashmë 28,

180
00:09:07,740 --> 00:09:10,460
e cila ishte elementi ish vjetër.

181
00:09:10,460 --> 00:09:13,540
>> Dhe tani, ne duam të ndryshojmë
madhësia e radhës

182
00:09:13,540 --> 00:09:15,780
për dy elemente në vend të tre.

183
00:09:15,780 --> 00:09:20,450
Tani mos harroni kam thënë më parë, kur ne
doni të shtoni elemente në radhë,

184
00:09:20,450 --> 00:09:26,000
ne kemi vënë atë në një vend array
cila është shuma e para dhe të madhësisë.

185
00:09:26,000 --> 00:09:29,050
Pra, në këtë rast, ne jemi ende duke vënë
ajo, elementi tjetër në radhë,

186
00:09:29,050 --> 00:09:33,360
në array vend 3, dhe
ne do të shohim se në një të dytë.

187
00:09:33,360 --> 00:09:35,730
>> Pra, ne kemi dequeued tani tonë
Elementi i parë nga radhë.

188
00:09:35,730 --> 00:09:36,480
Le ta bëjmë atë përsëri.

189
00:09:36,480 --> 00:09:38,696
Le të largojë një tjetër
element nga radhë.

190
00:09:38,696 --> 00:09:42,400
Në rast, aktual vjetër
element është array vend 1.

191
00:09:42,400 --> 00:09:44,220
Kjo është ajo që q.front na tregon.

192
00:09:44,220 --> 00:09:46,980
Kjo kuti e gjelbër na tregon se
kjo është elementi më i vjetër.

193
00:09:46,980 --> 00:09:49,310
Dhe kështu, x do të bëhet 33.

194
00:09:49,310 --> 00:09:52,130
Ne vetëm do lloj i harrojmë
se 33 ekziston në grup,

195
00:09:52,130 --> 00:09:55,100
dhe ne do të themi se për tani,
element i ri i vjetër në radhë

196
00:09:55,100 --> 00:09:58,900
është në vend të vargut 2, dhe madhësinë
e radhë, numri i elementeve

197
00:09:58,900 --> 00:10:02,152
ne kemi në radhë, është 1.

198
00:10:02,152 --> 00:10:05,110
Tani le të enqueue diçka, dhe unë
lloj i dha kësaj larg një të dytë më parë,

199
00:10:05,110 --> 00:10:10,340
por në qoftë se ne duam të vënë 40 në të
radhë, ku është 40 do të shkojë?

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

201
00:10:12,880 --> 00:10:17,730
E pra ne kemi qenë vënë atë
në q.front plus radhë madhësi,

202
00:10:17,730 --> 00:10:20,850
dhe kështu që ka kuptim për
në fakt për të vënë 40 këtu.

203
00:10:20,850 --> 00:10:22,840
Tani vini re se në
disa pika, ne jemi duke shkuar

204
00:10:22,840 --> 00:10:27,980
për të marrë në fund të
array tonë brenda q,

205
00:10:27,980 --> 00:10:32,010
por që venitur nga 28 dhe 33--
ata janë në fakt, teknikisht

206
00:10:32,010 --> 00:10:33,300
hapësira të hapura, e drejtë?

207
00:10:33,300 --> 00:10:36,040
Dhe kështu, ne mund të eventually--
se sundimi i shtuar

208
00:10:36,040 --> 00:10:40,390
ata të dy together-- ne mund përfundimisht
duhet të MM nga madhësia e kapaciteteve

209
00:10:40,390 --> 00:10:41,410
kështu që ne mund të përfundojë rreth.

210
00:10:41,410 --> 00:10:43,620
>> Pra, në qoftë se ne të merrni për elementin
numër 10, në qoftë se ne jemi

211
00:10:43,620 --> 00:10:48,790
zëvendësuar atë në element numër 10, ne do të
në fakt e vënë atë në vend array 0.

212
00:10:48,790 --> 00:10:50,997
Dhe në qoftë se ne ishim duke shkuar për të
Grup location-- më falni,

213
00:10:50,997 --> 00:10:53,080
nëse kemi shtuar ato së bashku,
dhe kemi marrë në numrin

214
00:10:53,080 --> 00:10:56,330
11 do të jetë aty ku ne do të duhet për të vënë
kjo, e cila nuk ekziston ne kete array--

215
00:10:56,330 --> 00:10:58,200
kjo do të shkojnë jashtë caqeve.

216
00:10:58,200 --> 00:11:03,367
Ne mund të mod me 10 dhe vënë
në array vend të 1.

217
00:11:03,367 --> 00:11:04,450
Pra, kjo është se si punojnë rradhë.

218
00:11:04,450 --> 00:11:08,540
Ata janë gjithmonë do të shkojnë nga e majta
në të djathtë dhe ndoshta të përfundojë rreth.

219
00:11:08,540 --> 00:11:11,280
Dhe ju e dini se ata janë të
nëse me permasa të plota, se kuti të kuqe,

220
00:11:11,280 --> 00:11:13,710
bëhet e barabartë me kapacitetin.

221
00:11:13,710 --> 00:11:16,720
Dhe kështu pasi ne kemi shtuar 40 të
radhë, dhe çfarë duhet të bëjmë?

222
00:11:16,720 --> 00:11:19,890
E pra, elementi më i vjetër
në radhë është ende 19,

223
00:11:19,890 --> 00:11:21,990
kështu që ne nuk duam të ndryshojmë
e përparme e radhë,

224
00:11:21,990 --> 00:11:23,820
por tani ne kemi dy
elementet në radhë,

225
00:11:23,820 --> 00:11:28,710
dhe kështu ne duam të rritur
madhësia tonë nga 1 deri në 2.

226
00:11:28,710 --> 00:11:31,820
>> Kjo është shumë e shumë atë me
duke punuar me rradhë array-bazë,

227
00:11:31,820 --> 00:11:33,630
dhe të ngjashme me rafte,
ka edhe një mënyrë

228
00:11:33,630 --> 00:11:36,450
për të zbatuar një radhë si një listë e lidhur.

229
00:11:36,450 --> 00:11:40,150
Tani në qoftë se ky lloj Struktura e të dhënave
duket të njohura për ju, ajo është.

230
00:11:40,150 --> 00:11:43,780
Kjo nuk është një listë e lidhur në formë individuale,
kjo është një listë e lidhur dyfish.

231
00:11:43,780 --> 00:11:46,790
Dhe tani, si një mënjanë, ajo është
në fakt e mundur për të zbatuar

232
00:11:46,790 --> 00:11:50,160
një radhë si një listë e lidhur në formë individuale, por
Unë mendoj se në aspektin e vizualizimi,

233
00:11:50,160 --> 00:11:53,350
ai në fakt mund të ndihmojë për të parë
këtë si një listë e lidhur dyfish.

234
00:11:53,350 --> 00:11:56,850
Por kjo është padyshim e mundur për
e bëjnë këtë si një listë e lidhur në formë individuale.

235
00:11:56,850 --> 00:12:00,110
>> Pra, le të kemi një vështrim në
çfarë kjo mund të duket si.

236
00:12:00,110 --> 00:12:02,750
Në qoftë se ne duam të enquue--
kështu që tani, përsëri ne jemi

237
00:12:02,750 --> 00:12:05,360
kalimi te një i lidhur-listë
model të bazuar këtu.

238
00:12:05,360 --> 00:12:08,420
Në qoftë se ne duam të enqueue, ne duam
për të shtuar një element të ri, dhe

239
00:12:08,420 --> 00:12:09,730
çfarë duhet të bëjmë?

240
00:12:09,730 --> 00:12:12,770
E pra, para së gjithash, për shkak se
ne jemi duke shtuar në fund

241
00:12:12,770 --> 00:12:15,520
dhe largimin nga
fillimi, ne ndoshta

242
00:12:15,520 --> 00:12:20,050
duan të ruajnë pointers për të dyja
koka dhe bishti i listës të lidhura?

243
00:12:20,050 --> 00:12:22,660
Bishti qenit një term tjetër për
në fund të listës të lidhura,

244
00:12:22,660 --> 00:12:24,496
elementi i fundit në lista e lidhur.

245
00:12:24,496 --> 00:12:26,620
Dhe këto do të ndoshta,
përsëri, të jetë e dobishme për ne

246
00:12:26,620 --> 00:12:28,477
nëse ata janë variabla globale.

247
00:12:28,477 --> 00:12:31,060
Por tani në qoftë se ne duam të shtoni një të ri
element çfarë ne duhet të bëjmë?

248
00:12:31,060 --> 00:12:35,262
Ajo që ne vetëm [? malak?] apo dinamike
ndajë nyjen tonë të ri për veten.

249
00:12:35,262 --> 00:12:38,220
Dhe pastaj, ashtu si kur ne të shtoni ndonjë
element për një listë ne e lidhur dyfish,

250
00:12:38,220 --> 00:12:40,410
vetëm duhet për të zgjidhur of--
këto tre hapa të fundit këtu

251
00:12:40,410 --> 00:12:43,330
janë vetëm në lidhje me të gjithë duke lëvizur
pointers në mënyrë korrekte

252
00:12:43,330 --> 00:12:46,710
kështu që elementi merr shtuar në
zinxhiri pa thyer zinxhirin

253
00:12:46,710 --> 00:12:49,580
ose për të bërë një lloj të gabimit
ose që kanë disa lloj aksidenti

254
00:12:49,580 --> 00:12:54,505
ndodhë ku ne rastësisht
jetim disa elemente të radhë sonë.

255
00:12:54,505 --> 00:12:55,880
Ja se çfarë kjo mund të duket si.

256
00:12:55,880 --> 00:13:00,980
Ne duam të shtoni elementin
10 deri në fund të këtij radhë.

257
00:13:00,980 --> 00:13:03,380
Pra, elementi më i vjetër këtu
përfaqësohet nga kokës.

258
00:13:03,380 --> 00:13:06,800
Kjo është gjëja e parë që ne kemi vënë
në këtë radhë hipotetik këtu.

259
00:13:06,800 --> 00:13:10,430
Dhe bisht, 13, është më
kohët e fundit shtuar element.

260
00:13:10,430 --> 00:13:17,030
Dhe kështu që në qoftë se ne duam të enqueue 10 në
këtë radhë, ne duam të vënë atë pas 13.

261
00:13:17,030 --> 00:13:19,860
Dhe kështu që ne jemi duke shkuar për dinamike
ndajë hapësirë ​​për një nyje të re

262
00:13:19,860 --> 00:13:23,280
dhe kontrolloni për null që të sigurohemi
ne nuk kemi një dështim kujtesës.

263
00:13:23,280 --> 00:13:27,040
Pastaj ne jemi duke shkuar për
vendin e 10 në atë nyje,

264
00:13:27,040 --> 00:13:30,030
dhe tani ne duhet të jemi të kujdesshëm
për mënyrën se si ne organizimin pointers

265
00:13:30,030 --> 00:13:32,180
kështu që ne nuk e thyejnë zinxhirin.

266
00:13:32,180 --> 00:13:38,910
>> Ne mund të vendosni fushë mëparshëm 10 s
për pikë përsëri në bisht të vjetër,

267
00:13:38,910 --> 00:13:41,620
dhe që nga viti '10 do të jetë
bisht i ri në disa pika

268
00:13:41,620 --> 00:13:44,459
me kohë të gjitha këto
zinxhirët janë të lidhura,

269
00:13:44,459 --> 00:13:46,250
asgjë nuk do të vijë
pas 10 tani.

270
00:13:46,250 --> 00:13:49,880
Dhe kështu tregues tjetër 10-së
do të tregojnë për null,

271
00:13:49,880 --> 00:13:53,580
dhe pastaj pasi e bëjmë këtë, pasi ne kemi
10 lidhur prapa me zinxhir,

272
00:13:53,580 --> 00:13:57,780
ne mund të marrë kreun e vjetër, ose, justifikim
mua, bishti i vjetër i radhë.

273
00:13:57,780 --> 00:14:02,980
Fundi i vjetër i radhë,
13, dhe të bëjë atë pikë në 10.

274
00:14:02,980 --> 00:14:08,220
Dhe tani, në këtë pikë, ne kemi
enqueued numrin 10 në këtë radhë.

275
00:14:08,220 --> 00:14:14,740
Të gjithë ne duhet të bëjmë tani është vetëm të lëvizur
bisht për pikë në 10 në vend të 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing është në fakt
shumë e ngjashme me popping

277
00:14:17,630 --> 00:14:21,710
nga nje pirg që është
zbatohet si një listë të lidhura

278
00:14:21,710 --> 00:14:24,040
në qoftë se ju keni parë videon oxhaqet.

279
00:14:24,040 --> 00:14:27,280
Të gjithë ne duhet të bëni është të fillojë në nivel
duke filluar, gjetur elementin e dytë,

280
00:14:27,280 --> 00:14:30,480
pa elementin e parë,
dhe pastaj të lëvizë kokën

281
00:14:30,480 --> 00:14:32,930
për të vënë në elementin e dytë.

282
00:14:32,930 --> 00:14:37,920
Ndoshta më mirë të kujtoj atë
vetëm të jenë tepër të qarta në lidhje me të.

283
00:14:37,920 --> 00:14:39,230
Kështu që këtu është radhë ynë përsëri.

284
00:14:39,230 --> 00:14:42,600
12 është elementi më i vjetër
në radhë tonë, kokë.

285
00:14:42,600 --> 00:14:46,210
10 është elementi më i ri
në radhë tonë, bisht tonë.

286
00:14:46,210 --> 00:14:49,310
>> Dhe kështu kur ne duam
një element të dequeue,

287
00:14:49,310 --> 00:14:52,202
ne duam të hequr elementin më të vjetër.

288
00:14:52,202 --> 00:14:52,910
Pra, çfarë bëjmë ne?

289
00:14:52,910 --> 00:14:55,243
E pra ne kemi vendosur një akrep traversal
që fillon në krye,

290
00:14:55,243 --> 00:14:57,840
dhe ne e lëvizin atë në mënyrë që ajo
vë në elementin e dytë

291
00:14:57,840 --> 00:15:02,290
e kjo queue-- diçka duke thënë trav
është e barabartë me Trav shigjetë tjetër, për shembull,

292
00:15:02,290 --> 00:15:07,170
do të shkojë trav atje që të tregojnë për
15, e cila, pas ne dequeue 12,

293
00:15:07,170 --> 00:15:13,030
ose pasi kemi hequr 12, do të
të bëhet element i atëhershëm i vjetër.

294
00:15:13,030 --> 00:15:16,360
>> Tani ne kemi marrë një të mbajë në ditën e parë
Elementi nëpërmjet kokë akrep

295
00:15:16,360 --> 00:15:19,440
dhe elementi i dytë
nëpërmjet trav akrep.

296
00:15:19,440 --> 00:15:25,170
Ne mund kokën tani të lirë, dhe pastaj ne mund të
thonë se asgjë nuk vjen para 15 më.

297
00:15:25,170 --> 00:15:29,990
Pra, ne mund të ndryshojmë 15 e mëparshme
tregues të tregojnë për null,

298
00:15:29,990 --> 00:15:31,874
dhe ne vetëm lëvizin kokën gjatë.

299
00:15:31,874 --> 00:15:32,540
Dhe atje ne do të shkojmë.

300
00:15:32,540 --> 00:15:35,840
Tani ne kemi sukses
dequeued 12, dhe tani ne

301
00:15:35,840 --> 00:15:39,180
kanë një radhë prej 4 elementeve.

302
00:15:39,180 --> 00:15:41,700
Kjo është shumë e shumë të gjithë
ka për radhët e gjata,

303
00:15:41,700 --> 00:15:45,810
edhe array-bazuara dhe të lidhura-lista e bazuar.

304
00:15:45,810 --> 00:15:46,860
Unë jam Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Kjo është CS 50.

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