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

2
00:00:05,204 --> 00:00:07,370
Doug LLOYD: Torej, če ste
gledal video na kupu,

3
00:00:07,370 --> 00:00:09,870
To je verjetno, da se počutijo
kot malo deja vu.

4
00:00:09,870 --> 00:00:13,850
To se dogaja na zelo podoben konceptu,
Samo z rahlim zavojem na njej.

5
00:00:13,850 --> 00:00:15,530
Bomo zdaj govorili o čakalnih vrst.

6
00:00:15,530 --> 00:00:19,350
Torej čakalne vrste, podobno kot kup,
je še ena vrsta strukture podatkov

7
00:00:19,350 --> 00:00:22,412
da bomo lahko uporabili za vzdrževanje
Podatki v organiziran način.

8
00:00:22,412 --> 00:00:24,120
Podobno kup,
ga je mogoče izvajati

9
00:00:24,120 --> 00:00:27,000
kot matrika ali povezani seznam.

10
00:00:27,000 --> 00:00:30,320
Za razliko od dimnika, pravila
ki jih uporabljamo za določanje

11
00:00:30,320 --> 00:00:34,210
ko se stvari dodal in odstraniti iz
čakalne vrste so nekoliko drugačni.

12
00:00:34,210 --> 00:00:36,590
>> Za razliko od dimnika, ki
je struktura LIFO,

13
00:00:36,590 --> 00:00:45,610
zadnji noter, prvi ven, čakalna vrsta je FIFO
struktura, FIFO, prvi noter, prvi ven.

14
00:00:45,610 --> 00:00:49,320
Zdaj čakalne vrste, ste verjetno
imajo analogijo do čakalnih vrst.

15
00:00:49,320 --> 00:00:52,820
Če ste že kdaj bili v vrsti
zabaviščni park ali na banki,

16
00:00:52,820 --> 00:00:56,430
tam je neke vrste pravičnosti
izvedbenih strukturo.

17
00:00:56,430 --> 00:00:59,160
Prva oseba v vrsti
banka je prva oseba

18
00:00:59,160 --> 00:01:00,760
kdo bo govoril na pripovedovalec.

19
00:01:00,760 --> 00:01:03,522
>> To bi bilo nekako dirki
do dna, če je edini način

20
00:01:03,522 --> 00:01:06,730
moraš govoriti z pripovedovalec na
banka naj bi bila zadnja oseba v vrsti.

21
00:01:06,730 --> 00:01:09,146
Vsi bi vedno želeli
da je zadnja oseba v vrsti,

22
00:01:09,146 --> 00:01:12,580
in oseba, ki je bila tam prvič
ki je čakala nekaj časa,

23
00:01:12,580 --> 00:01:14,715
bi bilo tam več ur,
in ure in ure

24
00:01:14,715 --> 00:01:17,590
preden so imeli priložnost, da dejansko
umakne denar na banki.

25
00:01:17,590 --> 00:01:22,510
In tako čakalne vrste so nekako od
pravičnost izvedbene strukture.

26
00:01:22,510 --> 00:01:25,780
Ampak ne, da ne pomeni nujno
da so nizov slaba stvar, samo

27
00:01:25,780 --> 00:01:28,160
da so čakalne vrste še en način, da to storite.

28
00:01:28,160 --> 00:01:32,420
Torej spet čakalna vrsta je prvi noter, prvi
ven, v primerjavi dimnika, ki traja leta,

29
00:01:32,420 --> 00:01:34,440
prvi ven.

30
00:01:34,440 --> 00:01:36,190
Podobno kup,
imamo dve operaciji

31
00:01:36,190 --> 00:01:38,470
da bomo lahko nastopili na čakalnih vrst.

32
00:01:38,470 --> 00:01:43,910
Imena so enqueue, ki je dodati
nov element na koncu prioritetnem vrstnem redu,

33
00:01:43,910 --> 00:01:47,330
in dequeue, ki je
odstraniti najstarejši

34
00:01:47,330 --> 00:01:49,670
Element s sprednje vrsti.

35
00:01:49,670 --> 00:01:53,600
Torej bomo dodali elemente
na koncu prioritetnem vrstnem redu,

36
00:01:53,600 --> 00:01:57,220
in bomo odstranili elemente
od prednjega dela vrsti.

37
00:01:57,220 --> 00:02:00,790
Ponovimo, da skladovnici, smo dodali
Elementi na vrhu kupa

38
00:02:00,790 --> 00:02:03,380
in odstranjevanje elementov
z vrha dimnika.

39
00:02:03,380 --> 00:02:07,570
Torej z enqueue, to je tako, da
Konec, odstranjevanje od spredaj.

40
00:02:07,570 --> 00:02:10,639
Torej najstarejše stvar v tam
Vedno je naslednja stvar

41
00:02:10,639 --> 00:02:13,620
da pridejo ven, če bomo poskušali
in dequeue nekaj.

42
00:02:13,620 --> 00:02:18,330
>> Torej še enkrat, s čakalnih vrst, smo lahko
temelji na matrični izvedb

43
00:02:18,330 --> 00:02:20,110
in vezan seznam, ki temelji izvedb.

44
00:02:20,110 --> 00:02:24,620
Bomo spet začeli z
izvedb, ki temelji na matriki.

45
00:02:24,620 --> 00:02:27,070
Definicija struktura
izgleda precej podobno.

46
00:02:27,070 --> 00:02:30,720
Imamo še en niz
tam podatkov tipa vrednosti

47
00:02:30,720 --> 00:02:32,690
tako da lahko imajo poljubne vrste podatkov.

48
00:02:32,690 --> 00:02:35,570
Mi bo spet uporabljati
celih števil v tem primeru.

49
00:02:35,570 --> 00:02:39,830
>> In tako kot z našimi
izvedba dimnika, ki temelji na matrika,

50
00:02:39,830 --> 00:02:42,340
ker smo uporabo obrazca
matrika, smo nujno

51
00:02:42,340 --> 00:02:46,850
imajo to omejitev, da C vrsta
od uveljavlja na nas, ki smo

52
00:02:46,850 --> 00:02:51,670
nimajo nobene dinamiko v našem
sposobnost, da rastejo in se skrči array.

53
00:02:51,670 --> 00:02:55,710
Odločiti se moramo na začetku
kar je največje število stvari

54
00:02:55,710 --> 00:02:59,300
da bomo lahko v to
čakalna vrsta, in v tem primeru,

55
00:02:59,300 --> 00:03:02,070
Zmogljivost bi nekateri pound
opredeljena stalnica v našem kodeksu.

56
00:03:02,070 --> 00:03:05,430
In za namene tega
video, kapaciteta se bo 10.

57
00:03:05,430 --> 00:03:07,690
>> Moramo slediti
sprednji del čakalne vrste

58
00:03:07,690 --> 00:03:11,160
tako da bomo vedeli, kateri element
želimo dequeue,

59
00:03:11,160 --> 00:03:15,070
in moramo tudi, da bi spremljali
nekaj else-- število elementov

60
00:03:15,070 --> 00:03:16,690
da imamo v naši vrsti.

61
00:03:16,690 --> 00:03:19,360
Opazili nismo sledenja
Ob koncu prioritetnem vrstnem redu, samo

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

63
00:03:21,150 --> 00:03:24,310
In razlog za to bo, upajmo,
postane malo bolj jasno v trenutku.

64
00:03:24,310 --> 00:03:26,143
Ko smo zaključili
ta opredelitev tipa,

65
00:03:26,143 --> 00:03:29,080
imamo nov tip podatkov
imenovane čakalne vrste, kar smo lahko zdaj

66
00:03:29,080 --> 00:03:30,630
razglasi spremenljivke te vrste podatkov.

67
00:03:30,630 --> 00:03:35,350
In nekoliko zmedeno, sem se odločil,
poklicati te čakalne vrste q, črka

68
00:03:35,350 --> 00:03:38,090
q namesto podatkovnega tipa q.

69
00:03:38,090 --> 00:03:39,600
>> Torej, tukaj je naša čakalne vrste.

70
00:03:39,600 --> 00:03:40,700
To je struktura.

71
00:03:40,700 --> 00:03:45,730
Vsebuje tri člane ali tri
polja, paleto velikosti ZMOGLJIVOSTI.

72
00:03:45,730 --> 00:03:47,340
V tem primeru, zmogljivost pa je 10.

73
00:03:47,340 --> 00:03:49,580
In to array je
dogaja, da imajo cela števila.

74
00:03:49,580 --> 00:03:55,240
V zeleno je sprednji del našega vrsti je
Naslednji element je treba odstraniti, in rdeče

75
00:03:55,240 --> 00:03:58,610
bo velikost prioritetnem vrstnem redu,
koliko elementi so trenutno

76
00:03:58,610 --> 00:04:01,190
Obstoječa v čakalni vrsti.

77
00:04:01,190 --> 00:04:05,300
Torej, če rečemo q.front Ene
0 in velikost q.size enaka 0--

78
00:04:05,300 --> 00:04:07,120
smo dajanje 0s na teh področjih.

79
00:04:07,120 --> 00:04:11,070
In na tej točki, da smo precej
pripravljeni, da začnejo delati z našo vrsto.

80
00:04:11,070 --> 00:04:14,140
>> Torej prva operacija moremo
izvesti je enqueue nekaj,

81
00:04:14,140 --> 00:04:16,860
da dodate nov element
Konec vrsti.

82
00:04:16,860 --> 00:04:19,089
No, kaj moramo
storiti v splošnem primeru?

83
00:04:19,089 --> 00:04:23,690
No, ta funkcija enqueue potrebe
da sprejme kazalec na naši vrsti.

84
00:04:23,690 --> 00:04:26,370
Še enkrat, če smo razglasila
naša čakalne vrste v svetu,

85
00:04:26,370 --> 00:04:29,490
mi ne bi bilo treba to storiti
nujno, vendar na splošno smo

86
00:04:29,490 --> 00:04:32,330
morali sprejeti kazalce
do podatkovnih struktur

87
00:04:32,330 --> 00:04:35,040
kot je ta, ker v nasprotnem primeru
smo mimo value-- smo

88
00:04:35,040 --> 00:04:38,140
poteka v kopijah čakalni vrsti,
in tako ne bomo dejansko spreminja

89
00:04:38,140 --> 00:04:41,050
čakalne vrste, da želimo spremeniti.

90
00:04:41,050 --> 00:04:44,860
>> Druga stvar, ki jo moramo storiti, je sprejeti
podatkovni element ustreznega tipa.

91
00:04:44,860 --> 00:04:46,818
Še enkrat, v tem primeru, da je
bo cela števila,

92
00:04:46,818 --> 00:04:49,330
vendar pa si lahko poljubno
razglasi podatkovni tip kot vrednost

93
00:04:49,330 --> 00:04:51,160
in bolj na splošno uporabljati.

94
00:04:51,160 --> 00:04:56,030
To je element želimo enqueue,
želimo dodati na koncu vrste.

95
00:04:56,030 --> 00:04:58,573
Potem smo dejansko želijo
postaviti, da so podatki v čakalni vrsti.

96
00:04:58,573 --> 00:05:01,490
V tem primeru je dajanje v
pravilna lega našega matrike,

97
00:05:01,490 --> 00:05:05,040
in potem želimo spremeniti velikost
v čakalni vrsti, koliko elementov smo

98
00:05:05,040 --> 00:05:07,050
trenutno imajo.

99
00:05:07,050 --> 00:05:07,990
>> Torej začnimo.

100
00:05:07,990 --> 00:05:10,890
Tukaj je, še enkrat, da je splošna
Izjava funkcija oblika

101
00:05:10,890 --> 00:05:13,980
Za kaj bi enqueue izgledal.

102
00:05:13,980 --> 00:05:14,910
In gremo.

103
00:05:14,910 --> 00:05:18,335
Oglejmo enqueue številko
28 v čakalno vrsto.

104
00:05:18,335 --> 00:05:19,460
Torej, kaj bomo storili?

105
00:05:19,460 --> 00:05:23,390
No, sprednji del našega vrsti je
pri 0 ° C, in velikost našega vrsti

106
00:05:23,390 --> 00:05:29,680
je na 0, in tako smo verjetno želeli postaviti
številka 28 število Elementa

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

108
00:05:31,124 --> 00:05:32,540
Tako smo zdaj postavljeni, da je tam.

109
00:05:32,540 --> 00:05:34,820
Torej, zdaj kaj moramo spremeniti?

110
00:05:34,820 --> 00:05:37,090
Mi ne želimo spremeniti
sprednji del čakalne vrste,

111
00:05:37,090 --> 00:05:40,850
ker želimo vedeti, kaj element
bomo morda morali kasneje dequeue.

112
00:05:40,850 --> 00:05:44,020
Torej razlog imamo spredaj tam
je nekakšen pokazatelj, kaj je

113
00:05:44,020 --> 00:05:46,439
najstarejša stvar v matriki.

114
00:05:46,439 --> 00:05:49,730
No najstarejša stvar v array-- v
Dejstvo, edina stvar v matriki desno

115
00:05:49,730 --> 00:05:53,540
now-- je 28, ki je
na matrično mestu 0.

116
00:05:53,540 --> 00:05:56,160
Torej, ne želimo, da
spremeniti to zeleno številko,

117
00:05:56,160 --> 00:05:57,910
ker to je najstarejši element.

118
00:05:57,910 --> 00:06:00,510
Nasprotno, želimo spremeniti velikost.

119
00:06:00,510 --> 00:06:04,110
Torej, v tem primeru bomo
prirastek velikosti do 1.

120
00:06:04,110 --> 00:06:08,430
>> Zdaj splošno neke ideje, v kateri se
Naslednji element je šla v vrsti

121
00:06:08,430 --> 00:06:12,310
je, da se ti dve številki
skupaj spredaj in velikost,

122
00:06:12,310 --> 00:06:16,390
in da vam bom povedala, kje je naslednji
element v vrsti bo šel.

123
00:06:16,390 --> 00:06:18,130
Torej, zdaj pa enqueue drugo številko.

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

125
00:06:20,250 --> 00:06:24,480
Torej, 33 je šel v
Niz lokacija 0 in 1.

126
00:06:24,480 --> 00:06:26,840
Torej, v tem primeru, da se dogaja
da gredo v matrično lokaciji 1,

127
00:06:26,840 --> 00:06:29,500
in zdaj je velikost našega čakalne vrste je 2.

128
00:06:29,500 --> 00:06:31,840
>> Spet smo ne spreminja
sprednji del naše čakalne vrste,

129
00:06:31,840 --> 00:06:34,730
ker 28 je še vedno
Najstarejši element, in smo

130
00:06:34,730 --> 00:06:38,220
želim to-- ko smo na koncu dobili
da dequeuing, odstranjevanje elementov

131
00:06:38,220 --> 00:06:43,300
iz te čakalne vrste, želimo vedeti
kjer najstarejši element.

132
00:06:43,300 --> 00:06:48,620
In zato smo vedno morali ohraniti
nekatere pokazatelj, kje je to.

133
00:06:48,620 --> 00:06:50,410
Torej, to je tisto, 0 je tam.

134
00:06:50,410 --> 00:06:52,910
To je tisto, spredaj je tam.

135
00:06:52,910 --> 00:06:55,022
>> Naj v enqueue ena več elementov, 19.

136
00:06:55,022 --> 00:06:56,980
Prepričan sem, da lahko uganiti
kjer 19 je šla.

137
00:06:56,980 --> 00:06:59,860
To se dogaja, da gredo v
Niz lokacija številka 2.

138
00:06:59,860 --> 00:07:01,570
To je 0 plus 2.

139
00:07:01,570 --> 00:07:03,199
In zdaj je velikost našega vrsti je 3.

140
00:07:03,199 --> 00:07:04,240
Imamo 3 elementov v njem.

141
00:07:04,240 --> 00:07:08,490
Torej, če smo bili, da, in ne bomo
do zdaj, enqueue še en element,

142
00:07:08,490 --> 00:07:11,370
da bi šel v matrično lokacijo
številka 3, in velikost našega vrsti

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

144
00:07:13,160 --> 00:07:15,279
Torej smo enqueued več elementov zdaj.

145
00:07:15,279 --> 00:07:16,570
Zdaj pa začnimo, da jih odstranite.

146
00:07:16,570 --> 00:07:19,450
Dajmo jim dequeue iz čakalne vrste.

147
00:07:19,450 --> 00:07:23,340
>> Torej podobno pop, ki je nekako
analoga tega za kupe,

148
00:07:23,340 --> 00:07:26,180
dequeue treba kratkoročno sprejeti
kazalec na queue-- spet,

149
00:07:26,180 --> 00:07:28,140
razen če je to globalno razglašena.

150
00:07:28,140 --> 00:07:31,610
Sedaj želimo spremeniti lokacijo
sprednje vrsti.

151
00:07:31,610 --> 00:07:35,050
To je, če je nekako gre
v igro, da prednja spremenljivka,

152
00:07:35,050 --> 00:07:37,310
ker ko smo odstranili
element, želimo

153
00:07:37,310 --> 00:07:40,720
da ga premaknete na naslednjo najstarejši element.

154
00:07:40,720 --> 00:07:44,180
>> Potem želimo zmanjšati
velikost prioritetnem vrstnem redu,

155
00:07:44,180 --> 00:07:47,130
nato pa želimo vrniti vrednost
ki je bil odstranjen iz vrste.

156
00:07:47,130 --> 00:07:48,921
Še enkrat, ne želimo, da ga preprosto zavreči.

157
00:07:48,921 --> 00:07:51,170
Mi verjetno se izkopavajo
da iz queue-- sva

158
00:07:51,170 --> 00:07:54,170
ga dequeuing ker nam ni vseeno za njega.

159
00:07:54,170 --> 00:08:01,080
Zato želimo to funkcijo, da se vrnete
podatkovni element tipa vrednosti.

160
00:08:01,080 --> 00:08:04,360
Še enkrat, v tem primeru, vrednost je celo število.

161
00:08:04,360 --> 00:08:05,670
>> Torej, zdaj pa dequeue nekaj.

162
00:08:05,670 --> 00:08:09,310
Oglejmo odstraniti element iz čakalne vrste.

163
00:08:09,310 --> 00:08:15,970
Če rečemo, int x enak & q, ampersand -Q-
še enkrat, da je kazalec na tej q podatkov

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

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

166
00:08:23,840 --> 00:08:29,480
V tem primeru, ker gre za prvi
noter, prvi ven strukture podatkov, FIFO,

167
00:08:29,480 --> 00:08:33,690
prva stvar, ki jo dal v to
čakalna vrsta je 28, in tako v tem primeru,

168
00:08:33,690 --> 00:08:37,245
bomo vzeli 28 od
čakalne vrste, ne pa 19, kar je za kaj

169
00:08:37,245 --> 00:08:38,870
mi pa bi storili, če je bil ta kup.

170
00:08:38,870 --> 00:08:42,220
Bomo vzeli 28 od čakalne vrste.

171
00:08:42,220 --> 00:08:44,960
>> Podoben temu, kar smo naredili z
Sveženj, smo dejansko ni

172
00:08:44,960 --> 00:08:47,345
dogaja, da se črta 28
iz vrste samega

173
00:08:47,345 --> 00:08:49,470
smo le, da bo vrste
od pretvarjati, da ni tam.

174
00:08:49,470 --> 00:08:51,678
Tako se dogaja, da tam ostanejo
v spomin, vendar smo le

175
00:08:51,678 --> 00:08:57,820
tekoč, da ga nekako ignorirati s premikanjem
drugi dve področji našega q podatkov

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

177
00:08:58,830 --> 00:09:00,230
Bomo spremenili spredaj.

178
00:09:00,230 --> 00:09:04,290
Q.front se zdaj dogaja, da
je 1, ker je sedaj

179
00:09:04,290 --> 00:09:07,740
najstarejši element imamo v našem
čakalne vrste, saj smo že odstranili 28,

180
00:09:07,740 --> 00:09:10,460
ki je bil nekdanji najstarejši element.

181
00:09:10,460 --> 00:09:13,540
>> In zdaj, želimo spremeniti
velikost vrsti

182
00:09:13,540 --> 00:09:15,780
dveh elementov, namesto treh.

183
00:09:15,780 --> 00:09:20,450
Zdaj pa ne pozabite, prej sem rekel, ko smo
želite dodati elemente v čakalno vrsto,

184
00:09:20,450 --> 00:09:26,000
mi smo jih postavili v mestu matrike
ki je vsota spredaj in velikosti.

185
00:09:26,000 --> 00:09:29,050
Torej, v tem primeru, smo še vedno dajanje
da, naslednji element v čakalni vrsti,

186
00:09:29,050 --> 00:09:33,360
v matrično lokacijo 3, in
bomo videli, da je v sekundi.

187
00:09:33,360 --> 00:09:35,730
>> Tako smo zdaj dequeued naše
Prvi element iz vrste.

188
00:09:35,730 --> 00:09:36,480
Dajmo še enkrat.

189
00:09:36,480 --> 00:09:38,696
Oglejmo odstraniti drugo
element iz čakalne vrste.

190
00:09:38,696 --> 00:09:42,400
V primeru, trenutno najstarejši
element je matrika lokacija 1.

191
00:09:42,400 --> 00:09:44,220
To je tisto, kar q.front nam pove.

192
00:09:44,220 --> 00:09:46,980
To zeleno polje nam pove, da
da je najstarejši element.

193
00:09:46,980 --> 00:09:49,310
In tako bo x postala 33.

194
00:09:49,310 --> 00:09:52,130
Bomo le nekako pozabil
da 33 obstaja v matriki,

195
00:09:52,130 --> 00:09:55,100
in bomo rekli, da je sedaj,
Novi najstarejši element v vrsti

196
00:09:55,100 --> 00:09:58,900
je na diod mestu 2, in velikost
po prioritetnem vrstnem redu, število elementov

197
00:09:58,900 --> 00:10:02,152
imamo v čakalni vrsti, je 1.

198
00:10:02,152 --> 00:10:05,110
Zdaj pa enqueue nekaj, in jaz
nekako to dal proč drugo nazaj,

199
00:10:05,110 --> 00:10:10,340
vendar če želimo postaviti 40 Into The
čakalne vrste, kjer je 40 šli?

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

201
00:10:12,880 --> 00:10:17,730
Pa smo se ga je dala
v q.front plus čakalne vrste velikosti,

202
00:10:17,730 --> 00:10:20,850
in zato je smiselno, da se
dejansko dal 40 tukaj.

203
00:10:20,850 --> 00:10:22,840
Zdaj opazili, da na
neki točki, gremo

204
00:10:22,840 --> 00:10:27,980
priti do konca
naša matrika znotraj q,

205
00:10:27,980 --> 00:10:32,010
ampak da zbledijo 28 in 33--
oni so dejansko, tehnično

206
00:10:32,010 --> 00:10:33,300
odprti prostori, kajne?

207
00:10:33,300 --> 00:10:36,040
In tako bomo lahko eventually--
to pravilo dodajanja

208
00:10:36,040 --> 00:10:40,390
ti dve together-- bomo lahko sčasoma
morali mod z velikostjo zmogljivosti

209
00:10:40,390 --> 00:10:41,410
tako da bomo lahko ovijte okoli.

210
00:10:41,410 --> 00:10:43,620
>> Torej, če želimo priti do elementa
številka 10, če smo

211
00:10:43,620 --> 00:10:48,790
ga nadomešča v številu elementov 10, bi bili
dejansko dal v matrično mestu 0.

212
00:10:48,790 --> 00:10:50,997
In če smo bili, da bo
Niz me location-- oprostite,

213
00:10:50,997 --> 00:10:53,080
če jih bomo sešteli skupaj,
in smo prišli do števila

214
00:10:53,080 --> 00:10:56,330
11 bi bilo, ko bi morali dati
je, ki ne obstaja v tem array--

215
00:10:56,330 --> 00:10:58,200
da bi šli ven iz igrišča.

216
00:10:58,200 --> 00:11:03,367
Mi lahko mod s 10. in dal
je v matrično lokaciji 1.

217
00:11:03,367 --> 00:11:04,450
Torej, to je, kako čakalne vrste delo.

218
00:11:04,450 --> 00:11:08,540
Oni gredo vedno z leve
na desno in morda ovijte okoli.

219
00:11:08,540 --> 00:11:11,280
In veš, da oni
celoti, če velikost, da rdeči škatli,

220
00:11:11,280 --> 00:11:13,710
postane enako kapaciteto.

221
00:11:13,710 --> 00:11:16,720
In tako, ko smo dodali 40 do
čakalne vrste, dobro kaj moramo storiti?

222
00:11:16,720 --> 00:11:19,890
No, najstarejši element
v vrsti še 19,

223
00:11:19,890 --> 00:11:21,990
zato ne želimo spremeniti
sprednji del čakalne vrste,

224
00:11:21,990 --> 00:11:23,820
ampak zdaj imamo dva
Elementi v čakalni vrsti,

225
00:11:23,820 --> 00:11:28,710
in zato želimo povečati
naše velikosti od 1 do 2.

226
00:11:28,710 --> 00:11:31,820
>> To je precej ga z
delo s temelji na matrični čakalnih vrst,

227
00:11:31,820 --> 00:11:33,630
in podobno nakladanje,
obstaja tudi način

228
00:11:33,630 --> 00:11:36,450
izvajati čakalne vrste kot povezan seznam.

229
00:11:36,450 --> 00:11:40,150
Zdaj, če je ta vrsta podatkovne strukture
izgleda znano, da vas je.

230
00:11:40,150 --> 00:11:43,780
To ni posamično povezani seznam,
to je dvojno povezani seznam.

231
00:11:43,780 --> 00:11:46,790
In zdaj, kot prahi, je
dejansko mogoče izvajati

232
00:11:46,790 --> 00:11:50,160
čakalna vrsta kot posamezno povezani seznam, vendar
Mislim, da v smislu vizualizacije,

233
00:11:50,160 --> 00:11:53,350
to lahko dejansko pomaga, da si ogledate
to kot dvojno povezani seznam.

234
00:11:53,350 --> 00:11:56,850
Vendar je vsekakor mogoče
To storite tako, kot posamezno povezani seznam.

235
00:11:56,850 --> 00:12:00,110
>> Torej, kaj je imeti poglej
kaj bi to izgledal.

236
00:12:00,110 --> 00:12:02,750
Če želimo enquue--
tako da sedaj spet smo

237
00:12:02,750 --> 00:12:05,360
prehod na povezanem seznamu
Modelska tukaj.

238
00:12:05,360 --> 00:12:08,420
Če želimo enqueue, želimo
dodati nov element, dobro

239
00:12:08,420 --> 00:12:09,730
Kaj moramo storiti?

240
00:12:09,730 --> 00:12:12,770
No, najprej, ker
smo dodali do konca

241
00:12:12,770 --> 00:12:15,520
in odstranitev iz
začenja, bomo verjetno

242
00:12:15,520 --> 00:12:20,050
želijo ohraniti napotke za oba
glava in rep povezani seznam?

243
00:12:20,050 --> 00:12:22,660
Rep pa drug izraz za
Konec povezani seznam,

244
00:12:22,660 --> 00:12:24,496
zadnji element v povezanem seznamu.

245
00:12:24,496 --> 00:12:26,620
In to se bo verjetno
še enkrat, bo koristno za nas

246
00:12:26,620 --> 00:12:28,477
če so globalne spremenljivke.

247
00:12:28,477 --> 00:12:31,060
Ampak zdaj, če želimo dodati novo
element kaj moramo storiti?

248
00:12:31,060 --> 00:12:35,262
Kaj smo pravkar [? Malak?] ali dinamično
dodeliti našo novo vozlišče za nas.

249
00:12:35,262 --> 00:12:38,220
In potem, samo všeč, ko smo dodali koli
element z dvojno povezanega seznama mi,

250
00:12:38,220 --> 00:12:40,410
morali razvrstiti of--
ti zadnji trije koraki tukaj

251
00:12:40,410 --> 00:12:43,330
so prav vsi približno gibljejo
kazalci na pravilen način

252
00:12:43,330 --> 00:12:46,710
tako da dobi element doda
veriga ne da bi poškodovali verigo

253
00:12:46,710 --> 00:12:49,580
ali izdelavo nekakšne napake
ali imajo neke vrste nesreč

254
00:12:49,580 --> 00:12:54,505
zgodilo pri čemer smo po naključju
sirote nekatere elemente naše vrste.

255
00:12:54,505 --> 00:12:55,880
Evo, kaj bi to izgledal.

256
00:12:55,880 --> 00:13:00,980
Želimo, da dodate element
10 na koncu te vrste.

257
00:13:00,980 --> 00:13:03,380
Torej najstarejši element tukaj
predstavlja glavi.

258
00:13:03,380 --> 00:13:06,800
To je prva stvar, ki smo mu
v tem hipotetičnem čakalne vrste tukaj.

259
00:13:06,800 --> 00:13:10,430
In rep, 13, je najbolj
Nedavno dodani element.

260
00:13:10,430 --> 00:13:17,030
In zato, če želimo, da enqueue 10 v
to čakalno vrsto, želimo, da bi ga po 13.

261
00:13:17,030 --> 00:13:19,860
In tako bomo dinamično
dodeliti prostor za novo vozlišče

262
00:13:19,860 --> 00:13:23,280
in preverite null se prepričajte,
nimamo okvare spomina.

263
00:13:23,280 --> 00:13:27,040
Potem bomo
postaviti 10 v to vozlišče,

264
00:13:27,040 --> 00:13:30,030
in zdaj moramo biti previdni
o tem, kako organizirati kazalce

265
00:13:30,030 --> 00:13:32,180
tako da ne bomo prekinili verigo.

266
00:13:32,180 --> 00:13:38,910
>> Mi lahko nastavite 10 na prejšnje polje
izpostaviti nazaj na staro rep,

267
00:13:38,910 --> 00:13:41,620
in ker '10 bo
Nov rep na neki točki

268
00:13:41,620 --> 00:13:44,459
do takrat, ko vsi ti
verige so povezani,

269
00:13:44,459 --> 00:13:46,250
nič ne dogaja, da pridejo
po 10 zdaj.

270
00:13:46,250 --> 00:13:49,880
In tako 10 ali na naslednji kazalec
bo opozarjajo na ničlo,

271
00:13:49,880 --> 00:13:53,580
in potem, ko smo to naredili, ko smo jih
povezan 10 nazaj do verige

272
00:13:53,580 --> 00:13:57,780
lahko vzamemo stare glavo, oziroma izgovora
me, stari rep čakalne vrste.

273
00:13:57,780 --> 00:14:02,980
Stara konec čakalne vrste,
13, in da je poudariti, da 10.

274
00:14:02,980 --> 00:14:08,220
In zdaj, na tej točki, imamo
enqueued številko 10 v tej vrsti.

275
00:14:08,220 --> 00:14:14,740
Vse kar morate storiti zdaj je le premikanje
rep do točke na 10 namesto na 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing je dejansko
Zelo podobna popping

277
00:14:17,630 --> 00:14:21,710
iz dimnika, ki je
izvaja kot povezan seznam

278
00:14:21,710 --> 00:14:24,040
če ste videli video nizov.

279
00:14:24,040 --> 00:14:27,280
Vse kar morate storiti je začeti izvajati
začenja, najti drugega elementa,

280
00:14:27,280 --> 00:14:30,480
sprostiti prvi element,
in nato premakniti glavo

281
00:14:30,480 --> 00:14:32,930
da kaže na drugi element.

282
00:14:32,930 --> 00:14:37,920
Verjetno bolje, da ga vizualizirati
samo, da je ekstra jasno o tem.

283
00:14:37,920 --> 00:14:39,230
Torej, tukaj je naša čakalne vrste znova.

284
00:14:39,230 --> 00:14:42,600
12 je najstarejši element
V naši vrsti, glavi.

285
00:14:42,600 --> 00:14:46,210
10 je najnovejši element
V naši vrsti, naši rep.

286
00:14:46,210 --> 00:14:49,310
>> In tako, ko želimo
da dequeue element,

287
00:14:49,310 --> 00:14:52,202
želimo odstraniti najstarejši element.

288
00:14:52,202 --> 00:14:52,910
Torej, kaj naj naredimo?

289
00:14:52,910 --> 00:14:55,243
No, smo si zastavili prečkanje kazalec
ki se začne v glavi,

290
00:14:55,243 --> 00:14:57,840
in mi ga premakniti, tako da je
opozarja na drugem elementu

291
00:14:57,840 --> 00:15:02,290
to queue-- kaj z besedami, trav
enaka trav puščico zraven, na primer,

292
00:15:02,290 --> 00:15:07,170
bi premakniti trav je poudariti, da
15, ki je, potem ko smo dequeue 12,

293
00:15:07,170 --> 00:15:13,030
ali po tem, ko smo odstranili 12, bo
postal takrat najstarejši element.

294
00:15:13,030 --> 00:15:16,360
>> Zdaj imamo držite na prvi
Element preko kazalca glave

295
00:15:16,360 --> 00:15:19,440
in drugi element
prek kazalca trav.

296
00:15:19,440 --> 00:15:25,170
Mi lahko sedaj prosto glavo, in potem bomo lahko
pravijo, nič ne pride pred 15. anymore.

297
00:15:25,170 --> 00:15:29,990
Tako bomo lahko spremenili 15 je prejšnja
kazalec, da kaže na ničlo,

298
00:15:29,990 --> 00:15:31,874
in smo samo premaknete nad glavo.

299
00:15:31,874 --> 00:15:32,540
In tam gremo.

300
00:15:32,540 --> 00:15:35,840
Zdaj imamo uspešno
dequeued 12, in zdaj smo

301
00:15:35,840 --> 00:15:39,180
še eno čakalno vrsto 4 elementov.

302
00:15:39,180 --> 00:15:41,700
To je zal veliko vse
je na čakalnih vrst,

303
00:15:41,700 --> 00:15:45,810
tako temelji na paleto in vezan seznam, ki temelji.

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

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

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