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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Tehát, ha már
nézte a videót verem,

3
00:00:07,370 --> 00:00:09,870
ez valószínűleg fog érezni
mint egy kis deja vu.

4
00:00:09,870 --> 00:00:13,850
Ez lesz egy nagyon hasonló fogalom,
Csak egy kis csavarral rajta.

5
00:00:13,850 --> 00:00:15,530
Fogunk beszélni most körülbelül sorok.

6
00:00:15,530 --> 00:00:19,350
Tehát egy sorban, hasonló egy köteg,
egy másik fajta adatstruktúra

7
00:00:19,350 --> 00:00:22,412
hogy tudjuk használni, hogy fenntartsák
adatokat szervezett módon.

8
00:00:22,412 --> 00:00:24,120
Hasonlóan egy köteg,
ez lehet végrehajtani

9
00:00:24,120 --> 00:00:27,000
mint egy tömb, vagy egy láncolt lista.

10
00:00:27,000 --> 00:00:30,320
Ellentétben a verem, a szabályok
hogy az általunk használt meghatározásához

11
00:00:30,320 --> 00:00:34,210
Amikor a dolgok hozzá, és eltávolították
Egy sorban egy kicsit más.

12
00:00:34,210 --> 00:00:36,590
>> Szemben egy köteg, amely
egy LIFO szerkezet,

13
00:00:36,590 --> 00:00:45,610
tart, first out, a várólista egy FIFO
szerkezet, FIFO, első, first out.

14
00:00:45,610 --> 00:00:49,320
Most sorba, akkor valószínűleg
Van egy analógia sorok.

15
00:00:49,320 --> 00:00:52,820
Ha valaha is volt a sorban
egy vidámpark és egy bank,

16
00:00:52,820 --> 00:00:56,430
van egyfajta méltányosság
végrehajtási struktúrát.

17
00:00:56,430 --> 00:00:59,160
Az első ember a sorban
A bank az első, aki

18
00:00:59,160 --> 00:01:00,760
aki kapja, hogy beszéljen a pénztárosnak.

19
00:01:00,760 --> 00:01:03,522
>> Nem lenne egyfajta verseny
az aljára, ha az egyetlen módja

20
00:01:03,522 --> 00:01:06,730
megvan beszélni a pénztárosnak a
bank volt, hogy az utolsó, aki a sorban.

21
00:01:06,730 --> 00:01:09,146
Mindenki azt mindig akar
hogy az utolsó, aki a sorban,

22
00:01:09,146 --> 00:01:12,580
és az a személy, aki ott volt az első
aki már várja egy darabig,

23
00:01:12,580 --> 00:01:14,715
lehet ott órákig,
és munkaidő, az órát

24
00:01:14,715 --> 00:01:17,590
mielőtt még egy esélyt, hogy ténylegesen
vissza semmilyen pénzt a bankban.

25
00:01:17,590 --> 00:01:22,510
És így sorok fajta a
méltányosság végrehajtási struktúrát.

26
00:01:22,510 --> 00:01:25,780
De ez nem feltétlenül jelenti azt,
hogy stack egy rossz dolog, csak

27
00:01:25,780 --> 00:01:28,160
hogy várólisták más módon kell csinálni.

28
00:01:28,160 --> 00:01:32,420
Szóval megint egy sort először, első
ki, szemben egy köteg, amely utolsóként

29
00:01:32,420 --> 00:01:34,440
első ki.

30
00:01:34,440 --> 00:01:36,190
Hasonlóan egy köteg,
van két művelet

31
00:01:36,190 --> 00:01:38,470
hogy el tudjuk végezni a sorok.

32
00:01:38,470 --> 00:01:43,910
A nevek Enqueue, ami az, hogy adjunk
Új elem, hogy a végén a sorban,

33
00:01:43,910 --> 00:01:47,330
és dequeue, amely
hogy távolítsa el a legrégebbi

34
00:01:47,330 --> 00:01:49,670
elem az első a sorban.

35
00:01:49,670 --> 00:01:53,600
Mi is így fogjuk adni elemek
rá a végén a sorban,

36
00:01:53,600 --> 00:01:57,220
és megyünk elemek eltávolítása
A első a sorban.

37
00:01:57,220 --> 00:02:00,790
Ismét a verem, mi volt hozzá
elemek a tetején a verem

38
00:02:00,790 --> 00:02:03,380
és eltávolítása elemek
A tetején a verem.

39
00:02:03,380 --> 00:02:07,570
Tehát Enqueue, ez hozzátéve, hogy
A végén, megszüntetve elölről.

40
00:02:07,570 --> 00:02:10,639
Tehát a legrégebbi dolog van
Mindig a következő dolog,

41
00:02:10,639 --> 00:02:13,620
hogy jöjjön ki, ha megpróbáljuk
és dequeue valamit.

42
00:02:13,620 --> 00:02:18,330
>> Tehát megint a sorokat, tudjuk
tömb alapú megvalósítások

43
00:02:18,330 --> 00:02:20,110
és a hozzá kapcsolódó-lista alapú megvalósítások.

44
00:02:20,110 --> 00:02:24,620
Kezdjük újra
tömb alapú megvalósítások.

45
00:02:24,620 --> 00:02:27,070
A szerkezet meghatározása
úgy néz ki, szép hasonló.

46
00:02:27,070 --> 00:02:30,720
Van egy másik tömb
ott az adatok típusú érték,

47
00:02:30,720 --> 00:02:32,690
így tartsa tetszőleges adattípusok.

48
00:02:32,690 --> 00:02:35,570
Mi újra fog használni
egészek ebben a példában.

49
00:02:35,570 --> 00:02:39,830
>> És csakúgy, mint a mi
tömbalapú verem megvalósításban

50
00:02:39,830 --> 00:02:42,340
mert mi használ
tömb, akkor feltétlenül

51
00:02:42,340 --> 00:02:46,850
Van ez a korlátozás, hogy a C típusú
A érvényesíti ránk, ami azt

52
00:02:46,850 --> 00:02:51,670
nincs dinamizmus mi
növekedni tudjon, és összezsugorodik a tömbben.

53
00:02:51,670 --> 00:02:55,710
El kell döntenünk, az elején
mi az a maximális számú dolog

54
00:02:55,710 --> 00:02:59,300
hogy mi is ebbe
várakozási sor, és ebben az esetben,

55
00:02:59,300 --> 00:03:02,070
kapacitás lenne néhány font
meghatározott állandó kódunkat.

56
00:03:02,070 --> 00:03:05,430
És a jelen
videó, kapacitás lesz 10.

57
00:03:05,430 --> 00:03:07,690
>> Meg kell nyomon követni
Az első a sorban

58
00:03:07,690 --> 00:03:11,160
így tudjuk, hogy melyik elem
akarunk dequeue,

59
00:03:11,160 --> 00:03:15,070
és azt is meg kell nyomon követni
valami else-- az elemek száma

60
00:03:15,070 --> 00:03:16,690
hogy mi a mi sorban.

61
00:03:16,690 --> 00:03:19,360
Figyeljük meg mi nem nyomon követhetőek
a végén a sorban, csak

62
00:03:19,360 --> 00:03:21,150
a méret a sorban.

63
00:03:21,150 --> 00:03:24,310
És az oka, hogy remélhetőleg
lesz egy kicsit világosabb, egy pillanat.

64
00:03:24,310 --> 00:03:26,143
Miután befejeztük
Az ilyen típusú meghatározása,

65
00:03:26,143 --> 00:03:29,080
van egy új adattípus
nevű sorban, amiről most

66
00:03:29,080 --> 00:03:30,630
Kijelentem, változó ugyanilyen típusra.

67
00:03:30,630 --> 00:03:35,350
És némi zavart, úgy döntöttem,
hívni ezt a sort q, a levél

68
00:03:35,350 --> 00:03:38,090
q helyett az adatok a q.

69
00:03:38,090 --> 00:03:39,600
>> Tehát itt van a mi sorban.

70
00:03:39,600 --> 00:03:40,700
Ez egy szerkezet.

71
00:03:40,700 --> 00:03:45,730
Ez tartalmaz három tagja vagy három
mezők, egy sor méretű kapacitás.

72
00:03:45,730 --> 00:03:47,340
Ebben az esetben, a kapacitás 10.

73
00:03:47,340 --> 00:03:49,580
És ez a tömb
fog tartani egész számok.

74
00:03:49,580 --> 00:03:55,240
Ebben a zöld az első a mi sorban, a
következő elem el kell távolítani, és a piros

75
00:03:55,240 --> 00:03:58,610
lesz a méret a sorban,
hány elem jelenleg

76
00:03:58,610 --> 00:04:01,190
meglévő a sorban.

77
00:04:01,190 --> 00:04:05,300
Tehát, ha azt mondjuk, q.front egyenlők
0, és q.size mérete megegyezik 0--

78
00:04:05,300 --> 00:04:07,120
mi vagyunk ami 0-át ezeken a területeken.

79
00:04:07,120 --> 00:04:11,070
És ezen a ponton, mi elég sokat
készen áll a munka a mi sorban.

80
00:04:11,070 --> 00:04:14,140
>> Tehát az első művelet, amit lehet
végre van sorba állítását valamit,

81
00:04:14,140 --> 00:04:16,860
hogy egy új elem, hogy
a végén a sorban.

82
00:04:16,860 --> 00:04:19,089
Hát mit is kell
nem az általános esetben?

83
00:04:19,089 --> 00:04:23,690
Hát ez a funkció sorba állítását igényeinek
hogy elfogadja a mutatót a sorban.

84
00:04:23,690 --> 00:04:26,370
Ismét, ha már kijelentette,
a sorban globálisan,

85
00:04:26,370 --> 00:04:29,490
akkor nem kell, hogy ezt
szükségszerűen, de általában, mi

86
00:04:29,490 --> 00:04:32,330
el kell fogadnunk mutatók
az adatstruktúrák

87
00:04:32,330 --> 00:04:35,040
mint ez, mert különben
mi elhaladó value-- vagyunk

88
00:04:35,040 --> 00:04:38,140
elhaladó példányban a sorban,
és így akkor nem is igazából változó

89
00:04:38,140 --> 00:04:41,050
a sorban, hogy mi áll szándékunkban változtatni.

90
00:04:41,050 --> 00:04:44,860
>> A másik dolog, hogy meg kell tennie, elfogadom
egy adat eleme a megfelelő típust.

91
00:04:44,860 --> 00:04:46,818
Ismét, ebben az esetben ez
lesz egészek,

92
00:04:46,818 --> 00:04:49,330
de lehet önkényesen
Kijelentem, az adatok típusát, mint érték

93
00:04:49,330 --> 00:04:51,160
és ezt általában.

94
00:04:51,160 --> 00:04:56,030
Ez az elem szeretnénk sorba állítását,
szeretnénk hozzáadni, hogy a végén a sorban.

95
00:04:56,030 --> 00:04:58,573
Aztán tényleg akar
helyezze, hogy az adatok a sorban.

96
00:04:58,573 --> 00:05:01,490
Ebben az esetben, helyezze azt a
megfelelő helyen a mi tömb,

97
00:05:01,490 --> 00:05:05,040
majd meg akarjuk változtatni a méretét
A sorban, hány elem van

98
00:05:05,040 --> 00:05:07,050
jelenleg.

99
00:05:07,050 --> 00:05:07,990
>> Szóval kezdjük.

100
00:05:07,990 --> 00:05:10,890
Itt van, megint, hogy az általános
formában funkciót nyilatkozat

101
00:05:10,890 --> 00:05:13,980
amit Enqueue nézhet.

102
00:05:13,980 --> 00:05:14,910
És kész is van.

103
00:05:14,910 --> 00:05:18,335
Nézzük sorba állítását száma
28 a sorba.

104
00:05:18,335 --> 00:05:19,460
Szóval mit fogunk csinálni?

105
00:05:19,460 --> 00:05:23,390
Nos, az első a mi várólista
0, és a mérete a sorban

106
00:05:23,390 --> 00:05:29,680
értéke 0, és így valószínűleg kívánja helyezni
száma 28 tömb elem száma

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

108
00:05:31,124 --> 00:05:32,540
Így már most elhelyezni, hogy ott van.

109
00:05:32,540 --> 00:05:34,820
Tehát most mit is kell változtatni?

110
00:05:34,820 --> 00:05:37,090
Nem akarjuk megváltoztatni
Az első a sorban,

111
00:05:37,090 --> 00:05:40,850
mert azt szeretnénk tudni, hogy mi elem
szükségünk lehet a dequeue később.

112
00:05:40,850 --> 00:05:44,020
Szóval miért kapnak előlap
egyfajta indikátora mi

113
00:05:44,020 --> 00:05:46,439
A legrégebbi dolog a tömbben.

114
00:05:46,439 --> 00:05:49,730
Nos legrégebbi dolog a array-- a
Tény, hogy az egyetlen dolog a tömb jobb

115
00:05:49,730 --> 00:05:53,540
now-- 28, amely a
A tömb 0 helyen.

116
00:05:53,540 --> 00:05:56,160
Tehát mi nem akarjuk, hogy
megváltoztatni, hogy a zöld számot,

117
00:05:56,160 --> 00:05:57,910
mert ez a legrégebbi eleme.

118
00:05:57,910 --> 00:06:00,510
Inkább azt szeretnénk változtatni a méretét.

119
00:06:00,510 --> 00:06:04,110
Tehát ebben az esetben, akkor
növekmény mérete 1.

120
00:06:04,110 --> 00:06:08,430
>> Most egy általános egyfajta képet, ahol a
következő elem fog menni a sorban

121
00:06:08,430 --> 00:06:12,310
van hozzá a két számot
együtt, első és mérete,

122
00:06:12,310 --> 00:06:16,390
és hogy megmondjuk, ahol a következő
elem a sorban fog menni.

123
00:06:16,390 --> 00:06:18,130
Így most nézzük sorba állítását másik számot.

124
00:06:18,130 --> 00:06:20,250
Nézzük sorba állítását 33.

125
00:06:20,250 --> 00:06:24,480
Tehát 33 fog menni
tömb helyen 0 és 1.

126
00:06:24,480 --> 00:06:26,840
Tehát ebben az esetben, ez lesz
bemenni tömb helyen 1,

127
00:06:26,840 --> 00:06:29,500
és most a mérete a sorban 2.

128
00:06:29,500 --> 00:06:31,840
>> Ismét nem vagyunk változó
Az első a mi sorban,

129
00:06:31,840 --> 00:06:34,730
mert 28 még mindig a
legrégibb eleme, és mi

130
00:06:34,730 --> 00:06:38,220
szeretnénk az alábbiakra: amikor végül kap
hogy dequeuing, megszüntetve elemek

131
00:06:38,220 --> 00:06:43,300
ebből a sorból, azt szeretném tudni,
ahol a legrégebbi elem.

132
00:06:43,300 --> 00:06:48,620
És így mindig fenn kell tartani
Néhány mutatója, hol van.

133
00:06:48,620 --> 00:06:50,410
Szóval ez az, amit a 0 ott van.

134
00:06:50,410 --> 00:06:52,910
Ez az, ami előtte van ott.

135
00:06:52,910 --> 00:06:55,022
>> Nézzük a Enqueue még egy elem, 19.

136
00:06:55,022 --> 00:06:56,980
Biztos vagyok benne, akkor hiszem,
ahol 19 fog menni.

137
00:06:56,980 --> 00:06:59,860
Meg fog menni
tömb helyét száma 2.

138
00:06:59,860 --> 00:07:01,570
Ez 0 és 2.

139
00:07:01,570 --> 00:07:03,199
És most a mérete a sorban 3.

140
00:07:03,199 --> 00:07:04,240
Jelenleg 3 elem kerül bele.

141
00:07:04,240 --> 00:07:08,490
Tehát ha mi voltunk, és nem megyünk
hogy most, sorba állítását másik elem,

142
00:07:08,490 --> 00:07:11,370
akkor bemegy tömb helyét
3. számú, és a mérete a sorban

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

144
00:07:13,160 --> 00:07:15,279
Így már enqueued több elemből most.

145
00:07:15,279 --> 00:07:16,570
Most kezdjük eltávolítani őket.

146
00:07:16,570 --> 00:07:19,450
Nézzük dequeue őket a sorból.

147
00:07:19,450 --> 00:07:23,340
>> Tehát hasonló pop, ami egyfajta
Az analóg ennek a stack,

148
00:07:23,340 --> 00:07:26,180
dequeue kell elfogadni
mutatót a queue-- újra,

149
00:07:26,180 --> 00:07:28,140
hacsak nem globálisan deklarált.

150
00:07:28,140 --> 00:07:31,610
Most szeretnénk változtatni a helyét
Az első a sorban.

151
00:07:31,610 --> 00:07:35,050
Ez az, ahol ez a fajta jön
játékba, hogy a front változó,

152
00:07:35,050 --> 00:07:37,310
mert azonnal elhárítjuk
egy elem, szeretnénk

153
00:07:37,310 --> 00:07:40,720
mozgatni, hogy a következő legrégebbi eleme.

154
00:07:40,720 --> 00:07:44,180
>> Aztán csökkenteni akarjuk
a méret a sorban,

155
00:07:44,180 --> 00:07:47,130
és aztán vissza akar térni az értéket
hogy lekerült a sorban.

156
00:07:47,130 --> 00:07:48,921
Ismét nem akarjuk, hogy csak megválni tőle.

157
00:07:48,921 --> 00:07:51,170
Mi feltehetően bontja
ez a queue-- vagyunk

158
00:07:51,170 --> 00:07:54,170
dequeuing, mert mi érdekli.

159
00:07:54,170 --> 00:08:01,080
Ezért szeretnénk ezt a funkciót, hogy visszatérjen
adatelem típusú értéket.

160
00:08:01,080 --> 00:08:04,360
Ismét, ez esetben, az érték egész szám.

161
00:08:04,360 --> 00:08:05,670
>> Így most nézzük dequeue valamit.

162
00:08:05,670 --> 00:08:09,310
Nézzük eltávolít egy elemet a sorból.

163
00:08:09,310 --> 00:08:15,970
Ha azt mondjuk, int x = & q, és jelet q--
újra, hogy egy mutató ebben q adatok

164
00:08:15,970 --> 00:08:20,177
structure-- melyik elem
lesz dequeued?

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

166
00:08:23,840 --> 00:08:29,480
Ebben az esetben, mert ez egy első
in, first out adatok szerkezete, FIFO,

167
00:08:29,480 --> 00:08:33,690
Az első dolog, amit ebbe
várakozási sor 28 volt, és így ebben az esetben,

168
00:08:33,690 --> 00:08:37,245
fogunk venni 28 ki
a sorba, nem 19, amely a mi

169
00:08:37,245 --> 00:08:38,870
mi volna, ha ez egy verem.

170
00:08:38,870 --> 00:08:42,220
Megyünk, hogy 28 ki a sorból.

171
00:08:42,220 --> 00:08:44,960
>> Hasonló ahhoz, amit csinált
verem, nem vagyunk valójában

172
00:08:44,960 --> 00:08:47,345
fog törölni 28
a sorból magát,

173
00:08:47,345 --> 00:08:49,470
mi csak lesz ilyen
A tettetni, hogy nincs ott.

174
00:08:49,470 --> 00:08:51,678
Szóval ez ott marad
a memóriában, de mi csak

175
00:08:51,678 --> 00:08:57,820
fog fajta figyelmen kívül hagyja azt a mozgó
a másik két terület a mi Q adatok

176
00:08:57,820 --> 00:08:58,830
szerkezetét.

177
00:08:58,830 --> 00:09:00,230
Fogunk előlapja cserélhető.

178
00:09:00,230 --> 00:09:04,290
Q.front most fog
lehet 1, mert ez most

179
00:09:04,290 --> 00:09:07,740
A legrégebbi elem van a mi
sorban, hiszen már eltávolították 28,

180
00:09:07,740 --> 00:09:10,460
ami a korábbi legrégebbi eleme.

181
00:09:10,460 --> 00:09:13,540
>> És most, szeretnénk változtatni
a méret a sorban

182
00:09:13,540 --> 00:09:15,780
a két elem három helyett.

183
00:09:15,780 --> 00:09:20,450
Most emlékszem, korábban mondtam, amikor
szeretné adni elemek a sorban,

184
00:09:20,450 --> 00:09:26,000
rakjuk egy tömbben helyen
amely az összege elülső és mérete.

185
00:09:26,000 --> 00:09:29,050
Tehát ebben az esetben, mi még mindig üzembe
ez a következő elem a sorban,

186
00:09:29,050 --> 00:09:33,360
a tömb helyen, 3, és
látni fogjuk, hogy a második.

187
00:09:33,360 --> 00:09:35,730
>> Így már most dequeued mi
első eleme a sorból.

188
00:09:35,730 --> 00:09:36,480
Csináljuk újra.

189
00:09:36,480 --> 00:09:38,696
Nézzük eltávolítani egy másik
eleme a sorból.

190
00:09:38,696 --> 00:09:42,400
Abban az esetben, a jelenlegi legrégebbi
elem tömb helyét 1.

191
00:09:42,400 --> 00:09:44,220
Ez az, amit q.front mondja nekünk.

192
00:09:44,220 --> 00:09:46,980
Hogy a zöld mezőben azt mondja, hogy
ez a legrégebbi eleme.

193
00:09:46,980 --> 00:09:49,310
És így, x lesz 33.

194
00:09:49,310 --> 00:09:52,130
Majd csak ilyen elfelejteni
hogy 33 létezik a tömb,

195
00:09:52,130 --> 00:09:55,100
és azt fogjuk mondani, hogy most, a
Új legrégebbi elem a sorban

196
00:09:55,100 --> 00:09:58,900
van tömb helyen 2, és a mérete
A sorban az elemek száma

197
00:09:58,900 --> 00:10:02,152
van a sorban, az 1.

198
00:10:02,152 --> 00:10:05,110
Most nézzük sorba állítását valamit, és én
egyfajta adta ezt el egy második ezelőtt,

199
00:10:05,110 --> 00:10:10,340
de ha azt akarjuk, hogy 40 a
sorban, ahol 40 fog menni?

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

201
00:10:12,880 --> 00:10:17,730
Hát mi már üzembe is
A q.front plusz sornak a mérete,

202
00:10:17,730 --> 00:10:20,850
És ez így van értelme
valóban, hogy 40 itt.

203
00:10:20,850 --> 00:10:22,840
Most észre, hogy a
Valamikor megyünk

204
00:10:22,840 --> 00:10:27,980
eljutni a végére
a tömb belsejében q,

205
00:10:27,980 --> 00:10:32,010
de ez elhalványult 28 és 33--
ők valójában, technikailag

206
00:10:32,010 --> 00:10:33,300
tereivel, ugye?

207
00:10:33,300 --> 00:10:36,040
És igen, mi is eventually--
ezt a szabályt, hozzátéve

208
00:10:36,040 --> 00:10:40,390
E két together-- előbb utóbb
kell, hogy mod a méret a kapacitás

209
00:10:40,390 --> 00:10:41,410
így tudjuk kerületi.

210
00:10:41,410 --> 00:10:43,620
>> Tehát, ha eljutunk elem
száma 10, ha mi vagyunk

211
00:10:43,620 --> 00:10:48,790
helyette az elemszám 10, mi lenne
ténylegesen tedd tömb 0 helyen.

212
00:10:48,790 --> 00:10:50,997
És ha megyünk
tömb telephelyein bocsánat,

213
00:10:50,997 --> 00:10:53,080
ha hozzáadott azokat össze
és mi van számát

214
00:10:53,080 --> 00:10:56,330
11 lenne, ha azt kellene tenni
azt, amely nem létezik ebben array--

215
00:10:56,330 --> 00:10:58,200
akkor megy ki a határokat.

216
00:10:58,200 --> 00:11:03,367
Mi lehetne mod 10 és tegye
ez a tömb helyét 1.

217
00:11:03,367 --> 00:11:04,450
Szóval így sorban állás dolgozni.

218
00:11:04,450 --> 00:11:08,540
Mindig csak menni balról
jobbra és esetleg kerületi.

219
00:11:08,540 --> 00:11:11,280
És tudod, hogy ők
Teljes ha a méret, hogy a piros doboz,

220
00:11:11,280 --> 00:11:13,710
egyenlővé válik kapacitást.

221
00:11:13,710 --> 00:11:16,720
És így, miután elérhetővé tettük, hogy a 40
queue, illetve mit kell tennünk?

222
00:11:16,720 --> 00:11:19,890
Nos, a legrégebbi elem
a sorban még mindig 19,

223
00:11:19,890 --> 00:11:21,990
így nem akar változtatni
Az első a sorban,

224
00:11:21,990 --> 00:11:23,820
de most már két
elemek a sorban,

225
00:11:23,820 --> 00:11:28,710
és így növelni akarjuk,
a mérete 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Ez nagyjából azt a
dolgozó tömb alapú sorok,

227
00:11:31,820 --> 00:11:33,630
és hasonló verem,
van még egy módja

228
00:11:33,630 --> 00:11:36,450
hogy végre egy sorba, mint egy láncolt lista.

229
00:11:36,450 --> 00:11:40,150
Most, ha ez az adat struktúra típus
úgy néz ki, ismerős neked ez.

230
00:11:40,150 --> 00:11:43,780
Ez nem egy egyszeresen láncolt lista,
ez egy kétszeresen láncolt lista.

231
00:11:43,780 --> 00:11:46,790
És most, mint félretéve, ez
valóban lehetséges, hogy végre

232
00:11:46,790 --> 00:11:50,160
egy sorba, mint egy egyszeresen láncolt lista, de
Azt hiszem, tekintve a megjelenítés,

233
00:11:50,160 --> 00:11:53,350
valójában talán segít, hogy megtekinthesse
ezt egy kétszeresen láncolt lista.

234
00:11:53,350 --> 00:11:56,850
De ez határozottan lehetséges
Ehhez a külön-külön láncolt lista.

235
00:11:56,850 --> 00:12:00,110
>> Szóval vessünk egy pillantást
mi ez a nézhet.

236
00:12:00,110 --> 00:12:02,750
Ha azt akarjuk, hogy enquue--
így most megint mi vagyunk

237
00:12:02,750 --> 00:12:05,360
váltás egy kapcsolt lista
alapú modell itt.

238
00:12:05,360 --> 00:12:08,420
Ha azt akarjuk, hogy sorba állítását, azt akarjuk,
hogy egy új elem, valamint

239
00:12:08,420 --> 00:12:09,730
Mit kell tennünk?

240
00:12:09,730 --> 00:12:12,770
Nos, először is, mert
mi hozzátéve, hogy a végén

241
00:12:12,770 --> 00:12:15,520
és eltávolítja a
kezdődő, akkor valószínűleg

242
00:12:15,520 --> 00:12:20,050
szeretné fenntartani mutatók mind a
fej és a farok a láncolt lista?

243
00:12:20,050 --> 00:12:22,660
Farok hogy egy másik kifejezés
a végén a láncolt lista,

244
00:12:22,660 --> 00:12:24,496
Az utolsó elem a láncolt lista.

245
00:12:24,496 --> 00:12:26,620
És ezek valószínűleg,
megint lehet hasznos számunkra

246
00:12:26,620 --> 00:12:28,477
ha globális változókat.

247
00:12:28,477 --> 00:12:31,060
De most, ha azt akarjuk, hogy egy új
elem mit kell tennünk?

248
00:12:31,060 --> 00:12:35,262
Amit most [? malak?], vagy dinamikusan
osztja az új csomópont magunknak.

249
00:12:35,262 --> 00:12:38,220
És akkor, mint amikor mi hozzá semmilyen
elemet egy kétszeresen láncolt lista vagyunk,

250
00:12:38,220 --> 00:12:40,410
Csak meg kell rendezni of--
az utolsó három lépés itt

251
00:12:40,410 --> 00:12:43,330
Íme, minden a mozgásról szól a
mutatók a helyes utat

252
00:12:43,330 --> 00:12:46,710
úgy, hogy az elem lesz hozzá
A lánc feltörése nélkül a lánc

253
00:12:46,710 --> 00:12:49,580
vagy hogy valamilyen hiba
vagy amelynek valamilyen baleset

254
00:12:49,580 --> 00:12:54,505
történni, amely által véletlenül
árva egyes elemeit a sorban.

255
00:12:54,505 --> 00:12:55,880
Itt van, amit ez nézhet.

256
00:12:55,880 --> 00:13:00,980
Szeretnénk felvenni az elem
10 a vége ennek a sorban.

257
00:13:00,980 --> 00:13:03,380
Tehát a legrégebbi eleme van
képviseli a fejét.

258
00:13:03,380 --> 00:13:06,800
Ez az első dolog, amit tenni
ebbe a feltételezett sorban itt.

259
00:13:06,800 --> 00:13:10,430
És a farok, a 13., a leginkább
Nemrég hozzáadott elem.

260
00:13:10,430 --> 00:13:17,030
És így ha azt akarjuk, hogy sorba állítását 10-et
ez a sorban, szeretnénk tedd után 13.

261
00:13:17,030 --> 00:13:19,860
És így fogunk dinamikusan
osztja helyet egy új csomópont

262
00:13:19,860 --> 00:13:23,280
és ellenőrizze a null hogy győződjön meg arról
nincs memória hiba.

263
00:13:23,280 --> 00:13:27,040
Aztán megyünk
helyezze be, hogy a 10 csomópont,

264
00:13:27,040 --> 00:13:30,030
és most meg kell, hogy legyen óvatos
hogyan szervezzük mutatók

265
00:13:30,030 --> 00:13:32,180
így nem megtörni a láncot.

266
00:13:32,180 --> 00:13:38,910
>> Mi lehet állítani 10 korábbi terén
hogy pont vissza a régi farok,

267
00:13:38,910 --> 00:13:41,620
és mivel '10 lesz az
új hátsó valamikor

268
00:13:41,620 --> 00:13:44,459
Mire az összes ilyen
láncok vannak kapcsolva,

269
00:13:44,459 --> 00:13:46,250
semmi sem fog jönni
10 után most.

270
00:13:46,250 --> 00:13:49,880
És így 10 következő mutatót
fog mutatni null,

271
00:13:49,880 --> 00:13:53,580
majd miután ezt tesszük, miután már
csatlakoztatva 10 hátra a lánc,

272
00:13:53,580 --> 00:13:57,780
tudjuk venni a régi fej, vagy mentség
Számomra a régi farok a sorban.

273
00:13:57,780 --> 00:14:02,980
A régi és a sor végéről,
13, és azt pont 10.

274
00:14:02,980 --> 00:14:08,220
És most, ezen a ponton, van
enqueued száma 10 ebbe a sorba.

275
00:14:08,220 --> 00:14:14,740
Csak annyit kell csinálni, csak ki kell menni a
farok, hogy pont helyett 10 és 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing valójában
nagyon hasonló a felbukkanó

277
00:14:17,630 --> 00:14:21,710
kéményből, amely
végre egy láncolt lista

278
00:14:21,710 --> 00:14:24,040
ha láttad a halom videót.

279
00:14:24,040 --> 00:14:27,280
Csak annyit kell tennie, hogy indítsa el a
kezdődő, keresse meg a második elem,

280
00:14:27,280 --> 00:14:30,480
Az első, az elem,
majd mozgatni a fejét

281
00:14:30,480 --> 00:14:32,930
hogy pont a második elem.

282
00:14:32,930 --> 00:14:37,920
Valószínűleg jobb képzelni
csak hogy extra világos róla.

283
00:14:37,920 --> 00:14:39,230
Tehát itt van a sorban újra.

284
00:14:39,230 --> 00:14:42,600
12 legrégebbi elem
a mi sorban, a fej.

285
00:14:42,600 --> 00:14:46,210
10 a legújabb elem
a mi sorban, a farok.

286
00:14:46,210 --> 00:14:49,310
>> És amikor azt akarjuk,
hogy dequeue egy elem,

287
00:14:49,310 --> 00:14:52,202
azt akarjuk, hogy távolítsa el a legrégebbi eleme.

288
00:14:52,202 --> 00:14:52,910
Szóval mit tegyünk?

289
00:14:52,910 --> 00:14:55,243
Hát mi meg bejárás mutatót
hogy indul az élén,

290
00:14:55,243 --> 00:14:57,840
és haladunk úgy, hogy
rámutat, hogy a második elem

291
00:14:57,840 --> 00:15:02,290
E queue-- valamit azzal trav
egyenlő Trav arrow következő, például,

292
00:15:02,290 --> 00:15:07,170
költözik trav van, hogy pont
15, amely, miután dequeue 12,

293
00:15:07,170 --> 00:15:13,030
vagy azt követően, hogy távolítsa el a 12, majd
lett az akkori legrégebbi eleme.

294
00:15:13,030 --> 00:15:16,360
>> Most már van hatalma az első
elem segítségével a mutató vezetője

295
00:15:16,360 --> 00:15:19,440
és a második elem
keresztül a mutatót trav.

296
00:15:19,440 --> 00:15:25,170
Most már szabad fejét, és akkor mi is
nem beszélve a szó előtt 15 már.

297
00:15:25,170 --> 00:15:29,990
Így tudunk változtatni 15 korábbi
mutatóját a null,

298
00:15:29,990 --> 00:15:31,874
és mi csak mozog a feje fölött.

299
00:15:31,874 --> 00:15:32,540
És ott is vagyunk.

300
00:15:32,540 --> 00:15:35,840
Most már sikeresen
dequeued 12, és most

301
00:15:35,840 --> 00:15:39,180
Van egy másik sorban a 4 elem.

302
00:15:39,180 --> 00:15:41,700
Ez elég sok minden
van a sorok,

303
00:15:41,700 --> 00:15:45,810
Mindkét tömb alapú és kapcsolt-lista alapján.

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

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

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