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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Svo ef þú hefur
horfði á vídeó á mánudaginn,

3
00:00:07,370 --> 00:00:09,870
þetta er líklega að fara að líða
eins smá deja vu.

4
00:00:09,870 --> 00:00:13,850
Það er að fara að mjög svipuðum toga,
bara með smá snúa á það.

5
00:00:13,850 --> 00:00:15,530
Við erum að fara að tala nú um biðraðir.

6
00:00:15,530 --> 00:00:19,350
Svo biðröð, svipað stafla,
er annars konar gögn uppbygging

7
00:00:19,350 --> 00:00:22,412
að við getum notað til að viðhalda
gögn í skipulegum hætti.

8
00:00:22,412 --> 00:00:24,120
Líkur á stafla,
það er hægt að innleiða

9
00:00:24,120 --> 00:00:27,000
sem fylki eða tengda listanum.

10
00:00:27,000 --> 00:00:30,320
Ólíkt stafla, reglur
sem við notum til að ákvarða

11
00:00:30,320 --> 00:00:34,210
þegar hlutirnir fá bætt og fjarlægð frá
biðröð eru svolítið öðruvísi.

12
00:00:34,210 --> 00:00:36,590
>> Ólíkt stafla, sem
er LIFO uppbyggingu,

13
00:00:36,590 --> 00:00:45,610
endast í, fyrst út, biðröð er FIFO
uppbyggingu, FIFO, fyrst inn, fyrst út.

14
00:00:45,610 --> 00:00:49,320
Nú biðraðir, þú sennilega
hafa hliðstæðan að biðröð.

15
00:00:49,320 --> 00:00:52,820
Ef þú hefur einhvern tíma verið í samræmi við
skemmtigarður eða í banka,

16
00:00:52,820 --> 00:00:56,430
það er tegund af sanngirni
framkvæmd uppbyggingu.

17
00:00:56,430 --> 00:00:59,160
Fyrsta manneskjan í takt við
bankinn er sá fyrsti

18
00:00:59,160 --> 00:01:00,760
hver fær að tala við Teller.

19
00:01:00,760 --> 00:01:03,522
>> Það væri tegund af kapp
til botns, ef eina leiðin

20
00:01:03,522 --> 00:01:06,730
þú got til að tala við Teller í síðasta
Bankinn átti að vera síðasta manneskja í línu.

21
00:01:06,730 --> 00:01:09,146
Allir myndu alltaf vilja
að vera síðasta manneskja í línu,

22
00:01:09,146 --> 00:01:12,580
og sá sem var þar fyrst
sem hefur verið að bíða um stund,

23
00:01:12,580 --> 00:01:14,715
mætti ​​þar tímunum saman,
og tíma, sem og tímum

24
00:01:14,715 --> 00:01:17,590
áður en þeir hafa tækifæri til að í raun og veru
draga allir peningar í bankanum.

25
00:01:17,590 --> 00:01:22,510
Og svo biðraðir eru tegund af
sanngirni framkvæmd uppbyggingu.

26
00:01:22,510 --> 00:01:25,780
En það þýðir ekki endilega að þýða
að stafla eru slæmur hlutur, bara

27
00:01:25,780 --> 00:01:28,160
sem biðraðir eru önnur leið til að gera það.

28
00:01:28,160 --> 00:01:32,420
Svo aftur biðröð er fyrst inn fyrst
út, á móti og stafla sem síðastur inn,

29
00:01:32,420 --> 00:01:34,440
fyrst út.

30
00:01:34,440 --> 00:01:36,190
Líkur á stafla,
höfum við tvær aðgerðir

31
00:01:36,190 --> 00:01:38,470
sem við getum gert á biðröðum.

32
00:01:38,470 --> 00:01:43,910
Nöfn eru enqueue, sem er að bæta við
a nýr þáttur til loka biðröð,

33
00:01:43,910 --> 00:01:47,330
og dequeue, sem er
að fjarlægja elsta

34
00:01:47,330 --> 00:01:49,670
þáttur frá the andlit af the biðröð.

35
00:01:49,670 --> 00:01:53,600
Þannig að við erum að fara að bæta þætti
á the endir af the biðröð,

36
00:01:53,600 --> 00:01:57,220
og við erum að fara að fjarlægja þætti
frá the andlit af the biðröð.

37
00:01:57,220 --> 00:02:00,790
Aftur, með stafla, við vorum að bæta
þættir til the toppur af the stafla

38
00:02:00,790 --> 00:02:03,380
og fjarlægja þætti
frá efsta hluta stafla.

39
00:02:03,380 --> 00:02:07,570
Svo með enqueue, það er að bæta við
enda, fjarlægja að framan.

40
00:02:07,570 --> 00:02:10,639
Svo elsta hlutur þarna
er alltaf næsti hlutur

41
00:02:10,639 --> 00:02:13,620
að koma út ef við reynum
og dequeue eitthvað.

42
00:02:13,620 --> 00:02:18,330
>> Svo aftur, með biðröð, við getum
array byggir gerð

43
00:02:18,330 --> 00:02:20,110
og tengd-listi byggir útfærslur.

44
00:02:20,110 --> 00:02:24,620
Við munum byrja aftur með
array byggir gerð.

45
00:02:24,620 --> 00:02:27,070
Uppbygging skilgreining
lítur mjög svipað.

46
00:02:27,070 --> 00:02:30,720
Við höfum annað array
þar af gögnum tegund gildi,

47
00:02:30,720 --> 00:02:32,690
svo það er hægt að halda handahófskennt gögn gerðum.

48
00:02:32,690 --> 00:02:35,570
Við erum aftur að fara að nota
heilar tölur í þessu dæmi.

49
00:02:35,570 --> 00:02:39,830
>> Og rétt eins og með okkar
array byggir stafla framkvæmd,

50
00:02:39,830 --> 00:02:42,340
vegna þess að við erum að nota er
array, við endilega

51
00:02:42,340 --> 00:02:46,850
hafa þessi takmörkun sem C góður
af knýja á okkur, sem er að við

52
00:02:46,850 --> 00:02:51,670
ekki hafa allir kraft í okkar
getu til að vaxa og minnka fylkisins.

53
00:02:51,670 --> 00:02:55,710
Við verðum að ákveða í upphafi
hvað er hámarksfjöldi hlutum

54
00:02:55,710 --> 00:02:59,300
sem við getum sett inn í þetta
biðröð, og í þessu tilfelli,

55
00:02:59,300 --> 00:03:02,070
getu væri einhver pund
skilgreint stöðug í númerið okkar.

56
00:03:02,070 --> 00:03:05,430
Og að því er varðar þetta
video, getu er að fara að vera 10.

57
00:03:05,430 --> 00:03:07,690
>> Við þurfum að halda utan um
framan á biðröð

58
00:03:07,690 --> 00:03:11,160
svo við vitum hver þáttur
við viljum dequeue,

59
00:03:11,160 --> 00:03:15,070
og við þurfum líka að halda utan um
eitthvað else-- fjölda staka

60
00:03:15,070 --> 00:03:16,690
sem við höfum í biðröð okkar.

61
00:03:16,690 --> 00:03:19,360
Taka við erum ekki að halda utan
í lok biðröð, bara

62
00:03:19,360 --> 00:03:21,150
stærð biðröð.

63
00:03:21,150 --> 00:03:24,310
Og ástæðan fyrir því mun vonandi
orðið svolítið skýrari á augnabliki.

64
00:03:24,310 --> 00:03:26,143
Þegar við höfum lokið
þessi tegund skilgreining,

65
00:03:26,143 --> 00:03:29,080
við höfum nýtt gögn tegund
heitir biðröð, sem við getum nú

66
00:03:29,080 --> 00:03:30,630
lýsa breytur þeirrar gögn tegund.

67
00:03:30,630 --> 00:03:35,350
Og nokkuð villast, hef ég ákveðið
að kalla þetta biðröð q, bréf

68
00:03:35,350 --> 00:03:38,090
q stað gögn tegund q.

69
00:03:38,090 --> 00:03:39,600
>> Svo hér er biðröð okkar.

70
00:03:39,600 --> 00:03:40,700
Það er uppbygging.

71
00:03:40,700 --> 00:03:45,730
Það inniheldur þrjá fulltrúa eða þrjá
sviðum, fylki af stærð getu.

72
00:03:45,730 --> 00:03:47,340
Í þessu tilfelli, getu er 10.

73
00:03:47,340 --> 00:03:49,580
Og þetta array er
fara að halda heiltölur.

74
00:03:49,580 --> 00:03:55,240
Í græna er framan á biðröð okkar,
Næsta þáttur til að fjarlægja, og í rauðu

75
00:03:55,240 --> 00:03:58,610
mun vera á stærð við biðröð,
hversu margir þættir eru nú

76
00:03:58,610 --> 00:04:01,190
núverandi í biðröð.

77
00:04:01,190 --> 00:04:05,300
Þannig að ef við segjum q.front jafngildir
0, og q.size stærð jafngildir 0--

78
00:04:05,300 --> 00:04:07,120
við erum að setja 0s í þessum sviðum.

79
00:04:07,120 --> 00:04:11,070
Og á þessum tímapunkti, við erum ansi mikið
tilbúinn til að byrja að vinna með biðröð okkar.

80
00:04:11,070 --> 00:04:14,140
>> Svo fyrsta aðgerð við getum
framkvæma er að enqueue eitthvað,

81
00:04:14,140 --> 00:04:16,860
til að bæta við nýjum þáttum til að
the endir af the biðröð.

82
00:04:16,860 --> 00:04:19,089
Jæja hvað þurfum við að
gera í almennu máli?

83
00:04:19,089 --> 00:04:23,690
Jæja þessi aðgerð enqueue þörfum
að samþykkja bendi biðröð okkar.

84
00:04:23,690 --> 00:04:26,370
Aftur, ef við hefðum lýst
biðröð okkar á heimsvísu,

85
00:04:26,370 --> 00:04:29,490
við myndum ekki þurfa að gera þetta
endilega, en almennt, við

86
00:04:29,490 --> 00:04:32,330
þarf að samþykkja ábendingum
að gögn uppbygging

87
00:04:32,330 --> 00:04:35,040
eins og þetta, því annars,
við erum liggur við value-- við erum

88
00:04:35,040 --> 00:04:38,140
liggur í afrit af biðröð,
og svo erum við í raun ekki að breyta

89
00:04:38,140 --> 00:04:41,050
biðröð að við ætlum að breyta.

90
00:04:41,050 --> 00:04:44,860
>> The annar hlutur sem það þarf að gera er að taka
a gögn þáttur viðeigandi tegund.

91
00:04:44,860 --> 00:04:46,818
Aftur, í þessu tilfelli, það er
að fara að vera heiltölur,

92
00:04:46,818 --> 00:04:49,330
en þú gætir geðþótta
lýsa gögn tegund sem verðmæti

93
00:04:49,330 --> 00:04:51,160
og nota þetta almennt.

94
00:04:51,160 --> 00:04:56,030
Það er þáttur sem við viljum enqueue,
við viljum bæta við lok biðröð.

95
00:04:56,030 --> 00:04:58,573
Þá viljum í raun að
setja þessi gögn í biðröð.

96
00:04:58,573 --> 00:05:01,490
Í þessu tilviki, setja hana í
rétt staðsetning array okkar,

97
00:05:01,490 --> 00:05:05,040
og þá viljum við breyta stærð
í biðröð, hversu margir þættir við

98
00:05:05,040 --> 00:05:07,050
nú hafa.

99
00:05:07,050 --> 00:05:07,990
>> Svo skulum við hefjast handa.

100
00:05:07,990 --> 00:05:10,890
Hér er, aftur, að almennt
form virka yfirlýsingu

101
00:05:10,890 --> 00:05:13,980
fyrir hvað enqueue gæti litið út.

102
00:05:13,980 --> 00:05:14,910
Og hér erum við að fara.

103
00:05:14,910 --> 00:05:18,335
Skulum enqueue fjölda
28 í biðröð.

104
00:05:18,335 --> 00:05:19,460
Svo hvað erum við að fara að gera?

105
00:05:19,460 --> 00:05:23,390
Jæja, the andlit af biðröð okkar er
á 0, og stærð biðröð okkar

106
00:05:23,390 --> 00:05:29,680
er á 0, og þannig að við viljum líklega að setja
fjöldi 28 í array þáttur númer

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

108
00:05:31,124 --> 00:05:32,540
Þannig að við höfum nú komið fyrir að í það.

109
00:05:32,540 --> 00:05:34,820
Svo nú hvað við þurfum að breyta?

110
00:05:34,820 --> 00:05:37,090
Við viljum ekki að breyta
framan biðröð,

111
00:05:37,090 --> 00:05:40,850
vegna þess að við viljum vita hvað þáttur
við gætum þurft að dequeue síðar.

112
00:05:40,850 --> 00:05:44,020
Svo ástæða þess að við höfum framan það
er tegund af vísbending um hvað er

113
00:05:44,020 --> 00:05:46,439
elsta hlutur í fylkinu.

114
00:05:46,439 --> 00:05:49,730
Jæja elsta hlutur í array-- í
staðreynd, það eina í array rétt

115
00:05:49,730 --> 00:05:53,540
now-- er 28, sem er
á array stað 0.

116
00:05:53,540 --> 00:05:56,160
Þannig að við viljum ekki að
breyta því grænt númer,

117
00:05:56,160 --> 00:05:57,910
því það er elsta þáttur.

118
00:05:57,910 --> 00:06:00,510
Frekar viljum við breyta stærð.

119
00:06:00,510 --> 00:06:04,110
Þannig að í þessu tilfelli, munum við
hækka stærð í 1.

120
00:06:04,110 --> 00:06:08,430
>> Nú almennt konar hugmynd um hvar
Næsta þáttur er að fara að fara í biðröð

121
00:06:08,430 --> 00:06:12,310
er að bæta þessa tvo tölur
saman, framan og stærð,

122
00:06:12,310 --> 00:06:16,390
og að segja þér hvar næsta
þáttur í biðröð er að fara að fara.

123
00:06:16,390 --> 00:06:18,130
Svo nú skulum enqueue annað númer.

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

125
00:06:20,250 --> 00:06:24,480
Svo 33 er að fara að fara í
array staðsetningu 0 plús 1.

126
00:06:24,480 --> 00:06:26,840
Þannig að í þessu tilfelli, það er að fara
að fara í array stað 1,

127
00:06:26,840 --> 00:06:29,500
og nú er stærð biðröð okkar 2.

128
00:06:29,500 --> 00:06:31,840
>> Aftur, við erum ekki að breyta
að framan af biðröð okkar,

129
00:06:31,840 --> 00:06:34,730
vegna 28 er enn
elsta þáttur, og við

130
00:06:34,730 --> 00:06:38,220
viljum to-- þegar við komum loksins
að dequeuing, fjarlægja þætti

131
00:06:38,220 --> 00:06:43,300
frá þessari biðröð, viljum við að vita
þar sem elsta þáttur er.

132
00:06:43,300 --> 00:06:48,620
Og svo þurfum við alltaf að halda
sumir vísbending um hvar sem er.

133
00:06:48,620 --> 00:06:50,410
Svo er það það sem 0 er þar fyrir.

134
00:06:50,410 --> 00:06:52,910
Það er það sem að framan er fyrir.

135
00:06:52,910 --> 00:06:55,022
>> Skulum í enqueue eitt frumefni, 19.

136
00:06:55,022 --> 00:06:56,980
Ég er viss um að þú getur giska
þar 19 er að fara að fara.

137
00:06:56,980 --> 00:06:59,860
Það er að fara að fara í
array staðsetningu númer 2.

138
00:06:59,860 --> 00:07:01,570
Það er 0 plús 2.

139
00:07:01,570 --> 00:07:03,199
Og nú er á stærð við biðröð okkar 3.

140
00:07:03,199 --> 00:07:04,240
Við höfum 3 þætti í því.

141
00:07:04,240 --> 00:07:08,490
Þannig að ef við á, og við erum ekki að fara
til núna, enqueue annar þáttur,

142
00:07:08,490 --> 00:07:11,370
það myndi fara í array stað
númer 3, og the stærð af biðröð okkar

143
00:07:11,370 --> 00:07:13,160
væri 4.

144
00:07:13,160 --> 00:07:15,279
Þannig að við höfum enqueued atriðum núna.

145
00:07:15,279 --> 00:07:16,570
Nú skulum byrja að fjarlægja þá.

146
00:07:16,570 --> 00:07:19,450
Skulum dequeue þá frá biðröð.

147
00:07:19,450 --> 00:07:23,340
>> Svo líkur að skjóta, sem er tegund
hliðstæðum um þetta fyrir stafla,

148
00:07:23,340 --> 00:07:26,180
dequeue þarf að sætta sig við
bendi á queue-- aftur,

149
00:07:26,180 --> 00:07:28,140
nema það er á heimsvísu lýst.

150
00:07:28,140 --> 00:07:31,610
Nú viljum við að breyta staðsetningu
á the andlit af the biðröð.

151
00:07:31,610 --> 00:07:35,050
Þetta er þar sem það kemur svona
í leik, sem að framan breyta,

152
00:07:35,050 --> 00:07:37,310
vegna þess að þegar við fjarlægja
þáttur, sem við viljum

153
00:07:37,310 --> 00:07:40,720
að færa það yfir á næsta elsta frumefni.

154
00:07:40,720 --> 00:07:44,180
>> Þá viljum við minnka
stærð biðröð,

155
00:07:44,180 --> 00:07:47,130
og þá viljum við skila gildi
sem var fjarlægt úr biðröð.

156
00:07:47,130 --> 00:07:48,921
Aftur, við viljum ekki bara henda því.

157
00:07:48,921 --> 00:07:51,170
Við væntanlega erum útdráttur
það frá queue-- við erum

158
00:07:51,170 --> 00:07:54,170
dequeuing það vegna þess að við hugsa um það.

159
00:07:54,170 --> 00:08:01,080
Þannig að við viljum þessi aðgerð til að fara aftur
a gögn þátturinn af gerðinni gildi.

160
00:08:01,080 --> 00:08:04,360
Aftur, í þessu tilfelli, gildi er heil tala.

161
00:08:04,360 --> 00:08:05,670
>> Svo nú skulum dequeue eitthvað.

162
00:08:05,670 --> 00:08:09,310
Skulum við fjarlægja stak úr biðröð.

163
00:08:09,310 --> 00:08:15,970
Ef við segjum int x er jafnt og q, merkið q--
aftur er það bendi til þessa q gögnum

164
00:08:15,970 --> 00:08:20,177
structure-- hvað þáttur
er að fara að vera dequeued?

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

166
00:08:23,840 --> 00:08:29,480
Í þessu tilfelli, vegna þess að það er fyrsta
inn, fyrst út gögn uppbygging, FIFO,

167
00:08:29,480 --> 00:08:33,690
það fyrsta sem við setjum inn í þetta
biðröð var 28, og svo í þessu tilviki,

168
00:08:33,690 --> 00:08:37,245
við erum að fara að taka 28 af
biðröð, ekki 19, sem er hvað

169
00:08:37,245 --> 00:08:38,870
við hefðum gert ef þetta væri stakkur.

170
00:08:38,870 --> 00:08:42,220
Við erum að fara að taka 28 af biðröð.

171
00:08:42,220 --> 00:08:44,960
>> Svipað og við gerðum við
stafla, við erum í raun ekki

172
00:08:44,960 --> 00:08:47,345
að fara að eyða 28
frá biðröð sig,

173
00:08:47,345 --> 00:08:49,470
við erum bara að fara að eins konar
af þykjast það er ekki þar.

174
00:08:49,470 --> 00:08:51,678
Svo það er að fara að vera þar
í minni, en við erum bara

175
00:08:51,678 --> 00:08:57,820
fara að eins konar hunsa það með því að færa
hinir tveir reitir af q gögnum okkar

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

177
00:08:58,830 --> 00:09:00,230
Við erum að fara að breyta framan.

178
00:09:00,230 --> 00:09:04,290
Q.front er nú að fara að
vera 1, því það er nú

179
00:09:04,290 --> 00:09:07,740
elsta þátturinn sem við höfum í okkar
biðröð, því að við höfum nú þegar eytt 28,

180
00:09:07,740 --> 00:09:10,460
sem var fyrrum elsta þáttur.

181
00:09:10,460 --> 00:09:13,540
>> Og nú viljum við að breyta
stærð biðröð

182
00:09:13,540 --> 00:09:15,780
að tveimur þáttum í stað þriggja.

183
00:09:15,780 --> 00:09:20,450
Nú man áðan sagði ég þegar við
langar að bæta þætti í biðröð,

184
00:09:20,450 --> 00:09:26,000
við að setja það í fjölda stað
sem er summa framan og stærð.

185
00:09:26,000 --> 00:09:29,050
Þannig að í þessu tilfelli erum við enn að setja
það er næsta þáttur í biðröð,

186
00:09:29,050 --> 00:09:33,360
í array stað 3, og
við munum sjá að í annað.

187
00:09:33,360 --> 00:09:35,730
>> Þannig að við höfum nú dequeued okkar
Fyrsti þátturinn af biðröð.

188
00:09:35,730 --> 00:09:36,480
Við skulum gera það aftur.

189
00:09:36,480 --> 00:09:38,696
Skulum við fjarlægja annað
þáttur frá biðröð.

190
00:09:38,696 --> 00:09:42,400
Í tilviki, núverandi elsta
þáttur er array staðsetningu 1.

191
00:09:42,400 --> 00:09:44,220
Það er það sem q.front segir okkur.

192
00:09:44,220 --> 00:09:46,980
Að grænt kassi segir okkur að
það er elsta þáttur.

193
00:09:46,980 --> 00:09:49,310
Og svo, x verður 33.

194
00:09:49,310 --> 00:09:52,130
Við munum bara svona gleyma
að 33 er í fylkinu,

195
00:09:52,130 --> 00:09:55,100
og við munum segja að nú,
Ný elsta þáttur í biðröð

196
00:09:55,100 --> 00:09:58,900
er array stað 2 og stærð
biðröð, fjöldi staka

197
00:09:58,900 --> 00:10:02,152
við höfum í biðröð, er 1.

198
00:10:02,152 --> 00:10:05,110
Nú skulum enqueue eitthvað, og ég
konar gaf þetta í burtu annað síðan,

199
00:10:05,110 --> 00:10:10,340
en ef við viljum setja 40 inn í
biðröð, þar sem er 40 að fara að fara?

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

201
00:10:12,880 --> 00:10:17,730
Jæja við höfum verið að setja það
í q.front plús biðröð stærð,

202
00:10:17,730 --> 00:10:20,850
og svo gerir það vit í að
í raun að setja 40 hér.

203
00:10:20,850 --> 00:10:22,840
Nú taka eftir því að á
sumir benda, við erum að fara

204
00:10:22,840 --> 00:10:27,980
að fá til the endir af
array okkar inni af Q,

205
00:10:27,980 --> 00:10:32,010
en það dofna út 28 og 33--
þeir eru í raun, tæknilega

206
00:10:32,010 --> 00:10:33,300
opið rými, ekki satt?

207
00:10:33,300 --> 00:10:36,040
Og svo getum við eventually--
að regla um að bæta

208
00:10:36,040 --> 00:10:40,390
þessir tveir together-- við getum loksins
að unga fólkið af stærð getu

209
00:10:40,390 --> 00:10:41,410
svo við getum sett um.

210
00:10:41,410 --> 00:10:43,620
>> Þannig að ef við fáum að frumefni
númer 10, ef við erum

211
00:10:43,620 --> 00:10:48,790
skipta um það í frumefni númer 10, við myndum
reyndar að setja það í array stað 0.

212
00:10:48,790 --> 00:10:50,997
Og ef við ætluðum að
array location-- afsaka mig,

213
00:10:50,997 --> 00:10:53,080
Ef við settum þá upp saman,
og við fengum að tala

214
00:10:53,080 --> 00:10:56,330
11 myndi vera þar sem við þyrfti að setja
það, sem er ekki til í þessum array--

215
00:10:56,330 --> 00:10:58,200
það væri að fara út af mörk.

216
00:10:58,200 --> 00:11:03,367
Við gætum unga fólkið um 10 og setja
það í array stað 1.

217
00:11:03,367 --> 00:11:04,450
Svo er það hvernig biðraðir vinna.

218
00:11:04,450 --> 00:11:08,540
Þeir eru alltaf að fara að fara frá vinstri
til hægri og hugsanlega sett um.

219
00:11:08,540 --> 00:11:11,280
Og þú veist að þeir eru
að fullu ef stærð, sem rauða kassanum,

220
00:11:11,280 --> 00:11:13,710
verður jafnt getu.

221
00:11:13,710 --> 00:11:16,720
Og svo eftir að við höfum bætt 40 við
biðröð, vel hvað við þurfum að gera?

222
00:11:16,720 --> 00:11:19,890
Jæja, elsta þáttur
í biðröð er enn 19,

223
00:11:19,890 --> 00:11:21,990
þannig að við viljum ekki að breyta
framan biðröð,

224
00:11:21,990 --> 00:11:23,820
en nú höfum við tvö
þættir í biðröð,

225
00:11:23,820 --> 00:11:28,710
og svo við viljum auka
stærð okkar frá 1 til 2.

226
00:11:28,710 --> 00:11:31,820
>> Það er ansi mikið um það með
vinna með array byggir biðröð,

227
00:11:31,820 --> 00:11:33,630
og svipað stafla,
Það er líka leið

228
00:11:33,630 --> 00:11:36,450
að innleiða biðröð sem tengda listanum.

229
00:11:36,450 --> 00:11:40,150
Nú ef þessi gögn uppbygging tegund
lítur þekki þig, það er.

230
00:11:40,150 --> 00:11:43,780
Það er ekki ein tengda listanum,
það er tvöfalt tengda listanum.

231
00:11:43,780 --> 00:11:46,790
Og nú, eins og innskot, það er
í raun hægt að hrinda í framkvæmd

232
00:11:46,790 --> 00:11:50,160
biðröð sem eintengdan lista, en
Ég hugsa í skilmálar af visualization,

233
00:11:50,160 --> 00:11:53,350
það í raun gæti hjálpað til að skoða
þetta sem tvöfalt tengda listanum.

234
00:11:53,350 --> 00:11:56,850
En það er örugglega hægt að
gera þetta sem stakar tengda listanum.

235
00:11:56,850 --> 00:12:00,110
>> Svo skulum við hafa a líta á
hvað þetta gæti litið út.

236
00:12:00,110 --> 00:12:02,750
Ef við viljum að enquue--
svo nú aftur við erum

237
00:12:02,750 --> 00:12:05,360
að skipta yfir tengda-listanum
undirstaða líkan hér.

238
00:12:05,360 --> 00:12:08,420
Ef við viljum að enqueue, við viljum
til að bæta við nýjum þáttum, vel

239
00:12:08,420 --> 00:12:09,730
hvað þurfum við að gera?

240
00:12:09,730 --> 00:12:12,770
Jæja, fyrst af öllu, vegna þess að
við erum að bæta við enda

241
00:12:12,770 --> 00:12:15,520
og fjarlægja úr
farin, við líklega

242
00:12:15,520 --> 00:12:20,050
viljum halda ábendingum til bæði
höfuð og hala af tengda listanum?

243
00:12:20,050 --> 00:12:22,660
Tail vera annað orð fyrir
the endir af the tengda listanum,

244
00:12:22,660 --> 00:12:24,496
síðasta þáttur í tengda listanum.

245
00:12:24,496 --> 00:12:26,620
Og þetta mun líklega,
aftur, vera gagnleg fyrir okkur

246
00:12:26,620 --> 00:12:28,477
ef þeir eru alþjóðlegt breytur.

247
00:12:28,477 --> 00:12:31,060
En nú ef við viljum bæta við nýjum
þáttur hvað eigum við að gera?

248
00:12:31,060 --> 00:12:35,262
Það sem við bara [? Malak?] eða breytilega
úthluta nýjum hnút okkar fyrir okkur sjálf.

249
00:12:35,262 --> 00:12:38,220
Og þá, eins og þegar við bætum einhverju
þáttur til tvöfalt tengda listanum við,

250
00:12:38,220 --> 00:12:40,410
bara að raða of--
þessir síðustu þrjú skref hér

251
00:12:40,410 --> 00:12:43,330
eru bara allt um að færa það
ábendingum á réttan hátt

252
00:12:43,330 --> 00:12:46,710
þannig að þátturinn fær bætt við
keðja án þess að brjóta keðju

253
00:12:46,710 --> 00:12:49,580
eða gera einhvers konar mistök
eða hafa einhvers konar slys

254
00:12:49,580 --> 00:12:54,505
gerast þar sem við tilviljun
munaðarlaus sumir þættir biðröð okkar.

255
00:12:54,505 --> 00:12:55,880
Hér er það sem þetta gæti litið út.

256
00:12:55,880 --> 00:13:00,980
Við viljum bæta þáttur
10 til loka þessa biðröð.

257
00:13:00,980 --> 00:13:03,380
Svo elsta þáttur hér
er táknuð með höfuð.

258
00:13:03,380 --> 00:13:06,800
Það er það fyrsta sem við setjum
í þessum ímynduðu biðröð hér.

259
00:13:06,800 --> 00:13:10,430
Með halanum, 13, er mest
nýlega bætt þáttur.

260
00:13:10,430 --> 00:13:17,030
Og svo ef við viljum enqueue 10 í
þetta biðröð, viljum við að setja það á eftir 13.

261
00:13:17,030 --> 00:13:19,860
Og svo við erum að fara að virk
úthluta pláss fyrir nýja hnút

262
00:13:19,860 --> 00:13:23,280
og athuga null til að tryggja
við höfum ekki minni bilun.

263
00:13:23,280 --> 00:13:27,040
Þá erum við að fara að
setja 10 í hnút,

264
00:13:27,040 --> 00:13:30,030
og nú þurfum við að vera varkár
um hvernig við skipuleggjum ábendingum

265
00:13:30,030 --> 00:13:32,180
þannig að við brjóta ekki keðju.

266
00:13:32,180 --> 00:13:38,910
>> Við getum sett 10 er fyrri sviði
að benda aftur á gamla hala,

267
00:13:38,910 --> 00:13:41,620
og síðan '10 verður
Ný hala á einhverjum tímapunkti

268
00:13:41,620 --> 00:13:44,459
með þeim tíma öllum þessum
keðjur eru tengd,

269
00:13:44,459 --> 00:13:46,250
ekkert að fara að koma
eftir 10 núna.

270
00:13:46,250 --> 00:13:49,880
Og svo 10 er næsta bendi
mun benda á núll,

271
00:13:49,880 --> 00:13:53,580
og þá eftir að við að gera þetta, eftir að við höfum
tengdur 10 aftur til að keðja,

272
00:13:53,580 --> 00:13:57,780
við getum tekið gamla höfuð, eða, afsökun
mér, gamla hali biðröð.

273
00:13:57,780 --> 00:14:02,980
Gamla lok biðröð,
13, og gera það benda til að 10.

274
00:14:02,980 --> 00:14:08,220
Og nú, á þessum tímapunkti, höfum við
enqueued númer 10 í þessum biðröð.

275
00:14:08,220 --> 00:14:14,740
Allt sem við þurfum að gera núna er bara að færa
hala til að benda á 10 í stað þess að 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing er í raun
mjög svipuð pabbi

277
00:14:17,630 --> 00:14:21,710
frá stafla sem er
útfærður sem tengt listanum

278
00:14:21,710 --> 00:14:24,040
ef þú hefur séð stafla vídeó.

279
00:14:24,040 --> 00:14:27,280
Allt sem við þurfum að gera er að byrja á að
farin, finna annað frumefni,

280
00:14:27,280 --> 00:14:30,480
losa fyrsta þáttur,
og þá færa höfuðið

281
00:14:30,480 --> 00:14:32,930
til að benda á annað frumefni.

282
00:14:32,930 --> 00:14:37,920
Líklega betra að sjón það
bara til að vera sérstaklega skýr um það.

283
00:14:37,920 --> 00:14:39,230
Svo hér biðröð okkar aftur.

284
00:14:39,230 --> 00:14:42,600
12 er elsta þáttur
í biðröð okkar, höfuð.

285
00:14:42,600 --> 00:14:46,210
10 er nýjasta þáttur
í biðröð okkar, hali okkar.

286
00:14:46,210 --> 00:14:49,310
>> Og svo þegar við viljum
að dequeue stak,

287
00:14:49,310 --> 00:14:52,202
við viljum að fjarlægja elsta frumefni.

288
00:14:52,202 --> 00:14:52,910
Svo hvað eigum við að gera?

289
00:14:52,910 --> 00:14:55,243
Jæja við sett Traversal músina
sem byrjar á höfuðið,

290
00:14:55,243 --> 00:14:57,840
og við að færa það svo að það
bendir til annað frumefni

291
00:14:57,840 --> 00:15:02,290
þetta queue-- eitthvað með því að segja Trav
jafngildir Trav arrow næst, til dæmis,

292
00:15:02,290 --> 00:15:07,170
myndi færa Trav það til að benda á
15, sem, eftir að við dequeue 12,

293
00:15:07,170 --> 00:15:13,030
eða eftir að við fjarlægja 12, verður
verða þá elsta þáttur.

294
00:15:13,030 --> 00:15:16,360
>> Nú höfum við fengið að halda á fyrsta
þáttur um músina höfuðið

295
00:15:16,360 --> 00:15:19,440
og Annað þáttur
gegnum músina Trav.

296
00:15:19,440 --> 00:15:25,170
Við getum nú ókeypis höfuð, og þá getum við
segir ekkert kemur fyrir 15. lengur.

297
00:15:25,170 --> 00:15:29,990
Þannig að við getum breytt 15 er fyrri
bendillinn að benda á núll,

298
00:15:29,990 --> 00:15:31,874
og við að færa bara höfuð yfir.

299
00:15:31,874 --> 00:15:32,540
Og það sem við förum.

300
00:15:32,540 --> 00:15:35,840
Nú höfum við tekist
dequeued 12, og nú erum við

301
00:15:35,840 --> 00:15:39,180
hafa annað biðröð 4 þætti.

302
00:15:39,180 --> 00:15:41,700
Það er ansi mikið allt
það er að biðraðir,

303
00:15:41,700 --> 00:15:45,810
bæði array byggir og tengd-listi byggir.

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

305
00:15:46,860 --> 00:15:49,100
Þetta er CS 50.

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