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

2
00:00:05,204 --> 00:00:07,370
DOUG Lloyd: Joten jos olet
katseli videon pino,

3
00:00:07,370 --> 00:00:09,870
tämä on todennäköisesti aio tuntea
kuten hieman deja vu.

4
00:00:09,870 --> 00:00:13,850
Se tulee hyvin samanlainen käsite,
vain hieman kierre sitä.

5
00:00:13,850 --> 00:00:15,530
Aiomme puhua nyt noin jonoja.

6
00:00:15,530 --> 00:00:19,350
Niin jono, samanlainen pino,
on toisenlainen tietorakenteen

7
00:00:19,350 --> 00:00:22,412
että voimme käyttää säilyttää
tiedot järjestäytyneesti.

8
00:00:22,412 --> 00:00:24,120
Samanlainen pino,
se voidaan toteuttaa

9
00:00:24,120 --> 00:00:27,000
kuten array tai linkitetty lista.

10
00:00:27,000 --> 00:00:30,320
Toisin kuin pino, säännöt
että käytämme määrittää

11
00:00:30,320 --> 00:00:34,210
kun asiat saavat lisätään ja poistetaan
jono ovat hieman erilainen.

12
00:00:34,210 --> 00:00:36,590
>> Toisin kuin pino, joka
on LIFO rakenne,

13
00:00:36,590 --> 00:00:45,610
last in, first out, jono on FIFO
rakenne, FIFO, first in, first out.

14
00:00:45,610 --> 00:00:49,320
Nyt jonot, luultavasti
on analogisesti jonoja.

15
00:00:49,320 --> 00:00:52,820
Jos olet joskus ollut jonossa
huvipuisto tai pankissa,

16
00:00:52,820 --> 00:00:56,430
siellä on eräänlainen oikeudenmukaisuuden
täytäntöönpanojaostosta.

17
00:00:56,430 --> 00:00:59,160
Ensimmäinen henkilö jonossa
pankki on ensimmäinen henkilö

18
00:00:59,160 --> 00:01:00,760
kuka saa puhua pankkivirkailija.

19
00:01:00,760 --> 00:01:03,522
>> Olisi tavallaan rodun
pohjaan, jos ainoa tapa

20
00:01:03,522 --> 00:01:06,730
sinun täytyy puhua Teller at
pankki oli olla viimeinen henkilö linjassa.

21
00:01:06,730 --> 00:01:09,146
Kaikki haluavat aina
olevan viimeinen henkilö linjassa,

22
00:01:09,146 --> 00:01:12,580
ja henkilö, joka oli siellä ensin
joka on odottanut aikaa,

23
00:01:12,580 --> 00:01:14,715
voisi olla siellä tuntikausia,
ja tuntia, ja tuntia

24
00:01:14,715 --> 00:01:17,590
ennen kuin ne on mahdollisuus todella
nostaa rahaa pankissa.

25
00:01:17,590 --> 00:01:22,510
Ja niin jonot ovat tavallaan
oikeudenmukaisuus täytäntöönpanojaostosta.

26
00:01:22,510 --> 00:01:25,780
Mutta se ei välttämättä tarkoita
että pinot ovat huono asia, vain

27
00:01:25,780 --> 00:01:28,160
että jonot ovat toinen tapa tehdä se.

28
00:01:28,160 --> 00:01:32,420
Joten jälleen jono on ensimmäinen, ensimmäinen
ulos, vs. pino joka kestää vuonna,

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

30
00:01:34,440 --> 00:01:36,190
Samanlainen pino,
meillä on kaksi toimintaa

31
00:01:36,190 --> 00:01:38,470
että voimme tehdä on jonoja.

32
00:01:38,470 --> 00:01:43,910
Nimet ovat enqueue, joka on lisätä
uusi elementti jonon,

33
00:01:43,910 --> 00:01:47,330
ja dequeue, joka on
poistaa vanhimman

34
00:01:47,330 --> 00:01:49,670
elementti jonon.

35
00:01:49,670 --> 00:01:53,600
Joten aiomme lisätä elementtejä
päälle jonon,

36
00:01:53,600 --> 00:01:57,220
ja aiomme poistaa elementtejä
edestä jonossa.

37
00:01:57,220 --> 00:02:00,790
Jälleen kanssa pino, olimme lisäämällä
elementtejä pinon päälle

38
00:02:00,790 --> 00:02:03,380
ja poistamalla tekijät
ylhäältä pinon.

39
00:02:03,380 --> 00:02:07,570
Joten enqueue, se lisäämällä
lopussa, poistaa edestä.

40
00:02:07,570 --> 00:02:10,639
Joten vanhin juttu siellä
on aina seuraava asia

41
00:02:10,639 --> 00:02:13,620
tulla ulos jos yritämme
ja dequeue jotain.

42
00:02:13,620 --> 00:02:18,330
>> Joten jälleen, jossa jonot, voimme
array-pohjainen toteutukset

43
00:02:18,330 --> 00:02:20,110
ja linkitetty-lista perustuu toteutuksissa.

44
00:02:20,110 --> 00:02:24,620
Aloitamme uudelleen
array-pohjainen toteutukset.

45
00:02:24,620 --> 00:02:27,070
Rakenteen määrittely
näyttää melko samanlaisia.

46
00:02:27,070 --> 00:02:30,720
Meillä on toinen joukko
siellä tietojen tyyppi arvo,

47
00:02:30,720 --> 00:02:32,690
joten se voi olla mielivaltaista tietotyyppejä.

48
00:02:32,690 --> 00:02:35,570
Olemme jälleen aio käyttää
kokonaisluvut tässä esimerkissä.

49
00:02:35,570 --> 00:02:39,830
>> Ja aivan kuten meidän
array-pohjainen pino täytäntöönpanon,

50
00:02:39,830 --> 00:02:42,340
koska käytämme
array, me välttämättä

51
00:02:42,340 --> 00:02:46,850
on, että rajoitus, että C tällaista
ja valvoo meitä, mikä on meidän

52
00:02:46,850 --> 00:02:51,670
ei ole dynaamisuutta meidän
kyky kasvaa ja kutistua jono.

53
00:02:51,670 --> 00:02:55,710
Meidän on päätettävä alussa
mikä on suurin määrä asioita

54
00:02:55,710 --> 00:02:59,300
että voimme tähän
jono, ja tässä tapauksessa,

55
00:02:59,300 --> 00:03:02,070
kapasiteetti olisi noin punta
määritelty jatkuva meidän koodi.

56
00:03:02,070 --> 00:03:05,430
Ja tämän
video, kapasiteetti tulee olemaan 10.

57
00:03:05,430 --> 00:03:07,690
>> Meidän täytyy seurata
jonon

58
00:03:07,690 --> 00:03:11,160
joten tiedämme, mitkä elementti
haluamme dequeue,

59
00:03:11,160 --> 00:03:15,070
ja meidän on myös seurata
jotain else-- alkioiden lukumäärä

60
00:03:15,070 --> 00:03:16,690
että meillä on jonossa.

61
00:03:16,690 --> 00:03:19,360
Huomaa, emme pitää kirjaa
lopussa jonon, vain

62
00:03:19,360 --> 00:03:21,150
koko jonon.

63
00:03:21,150 --> 00:03:24,310
Ja syy, joka toivottavasti
tullut hieman selkeämpi hetki.

64
00:03:24,310 --> 00:03:26,143
Kun olemme saattaneet
Tämän tyyppinen määritelmä,

65
00:03:26,143 --> 00:03:29,080
meillä on uusi tietotyyppi
nimeltään jono, joka voimme nyt

66
00:03:29,080 --> 00:03:30,630
julistaa muuttujat tietojen tyyppi.

67
00:03:30,630 --> 00:03:35,350
Ja hieman harhaanjohtavasti, olen päättänyt
kutsua tätä jonoon q, kirjain

68
00:03:35,350 --> 00:03:38,090
q sijasta tietotyyppi q.

69
00:03:38,090 --> 00:03:39,600
>> Joten tässä on meidän jono.

70
00:03:39,600 --> 00:03:40,700
Se on rakenne.

71
00:03:40,700 --> 00:03:45,730
Se sisältää kolme jäsentä tai kolme
kentät, taulukon koko KAPASITEETTI.

72
00:03:45,730 --> 00:03:47,340
Tässä tapauksessa, kapasiteetti on 10.

73
00:03:47,340 --> 00:03:49,580
Ja tämä joukko on
aikoo järjestää kokonaislukuja.

74
00:03:49,580 --> 00:03:55,240
Vihreä on edessä meidän jonossa,
seuraava elementti poistettava, ja punaisella

75
00:03:55,240 --> 00:03:58,610
on koko jonon,
kuinka monta elementtiä hetkellä

76
00:03:58,610 --> 00:04:01,190
olemassa olevat jonossa.

77
00:04:01,190 --> 00:04:05,300
Joten jos sanomme q.front tasavertaisten
0, ja q.size koko vastaa 0--

78
00:04:05,300 --> 00:04:07,120
me laitamme 0s osaksi näillä aloilla.

79
00:04:07,120 --> 00:04:11,070
Ja tässä vaiheessa, olemme melko paljon
valmis aloittamaan työtämme jonoon.

80
00:04:11,070 --> 00:04:14,140
>> Joten ensimmäinen operaatio voimme
tehdä on laittaa jonoon jotain,

81
00:04:14,140 --> 00:04:16,860
lisätä uuden elementin
jonon.

82
00:04:16,860 --> 00:04:19,089
No mitä meidän
tehdä yleisessä tapauksessa?

83
00:04:19,089 --> 00:04:23,690
No tämä toiminto laittaa jonoon tarpeisiin
hyväksymään osoitin meidän jonoon.

84
00:04:23,690 --> 00:04:26,370
Jälleen, jos meillä oli julistanut
meidän jono maailmanlaajuisesti,

85
00:04:26,370 --> 00:04:29,490
meidän ei tarvitse tehdä tätä
väistämättä, mutta yleisesti ottaen, me

86
00:04:29,490 --> 00:04:32,330
täytyy hyväksyä viitteitä
ja tietorakenteita

87
00:04:32,330 --> 00:04:35,040
näin, koska muuten,
olemme ohi value-- olemme

88
00:04:35,040 --> 00:04:38,140
ohimennen kopioita jonossa,
ja niin emme todella muuttuu

89
00:04:38,140 --> 00:04:41,050
jono että aiomme muuttaa.

90
00:04:41,050 --> 00:04:44,860
>> Toinen asia se tarvitsee vain hyväksyä
tieto on sopivaa tyyppiä.

91
00:04:44,860 --> 00:04:46,818
Jälleen tässä tapauksessa, se on
olemaan kokonaislukuja,

92
00:04:46,818 --> 00:04:49,330
mutta voit mielivaltaisesti
julistaa tietotyyppi kuin arvo

93
00:04:49,330 --> 00:04:51,160
ja käyttää tätä yleisemmin.

94
00:04:51,160 --> 00:04:56,030
Se on elementti haluamme laittaa jonoon,
haluamme lisätä loppuun jonossa.

95
00:04:56,030 --> 00:04:58,573
Sitten me todella haluavat
paikka, että tiedot jonossa.

96
00:04:58,573 --> 00:05:01,490
Tässä tapauksessa, laitat sen
oikea sijainti meidän array,

97
00:05:01,490 --> 00:05:05,040
ja sitten haluamme muuttaa kokoa
jonossa, kuinka monta elementtiä me

98
00:05:05,040 --> 00:05:07,050
tällä hetkellä.

99
00:05:07,050 --> 00:05:07,990
>> Joten pääset alkuun.

100
00:05:07,990 --> 00:05:10,890
Tässä on, jälleen, että yleinen
Form Function ilmoitus

101
00:05:10,890 --> 00:05:13,980
mitä enqueue voisi näyttää.

102
00:05:13,980 --> 00:05:14,910
Ja tässä sitä mennään.

103
00:05:14,910 --> 00:05:18,335
Katsotaanpa laittaa jonoon numero
28 jonoon.

104
00:05:18,335 --> 00:05:19,460
Joten mitä me teemme?

105
00:05:19,460 --> 00:05:23,390
No, edessä meidän jono on
0, ja koko meidän jonossa

106
00:05:23,390 --> 00:05:29,680
on 0, ja niin me luultavasti halua laittaa
numero 28 array elementti numero

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

108
00:05:31,124 --> 00:05:32,540
Joten olemme nyt sijoitettu, että siellä.

109
00:05:32,540 --> 00:05:34,820
Joten nyt mitä meidän täytyy muuttaa?

110
00:05:34,820 --> 00:05:37,090
Emme halua muuttaa
jonon,

111
00:05:37,090 --> 00:05:40,850
koska haluamme tietää, mitä elementti
meidän on ehkä dequeue myöhemmin.

112
00:05:40,850 --> 00:05:44,020
Joten syystä olemme Edessä
on eräänlainen indikaattori mitä

113
00:05:44,020 --> 00:05:46,439
vanhin asia jono.

114
00:05:46,439 --> 00:05:49,730
No vanhin asia array-- vuonna
Itse asiassa ainoa asia array oikeassa

115
00:05:49,730 --> 00:05:53,540
now-- on 28, joka on
klo array sijainti 0.

116
00:05:53,540 --> 00:05:56,160
Joten emme halua
muuttaa että vihreä numero,

117
00:05:56,160 --> 00:05:57,910
koska se on vanhin elementti.

118
00:05:57,910 --> 00:06:00,510
Pikemminkin haluamme muuttaa kokoa.

119
00:06:00,510 --> 00:06:04,110
Joten tässä tapauksessa, käymme
Porrasvälin 1.

120
00:06:04,110 --> 00:06:08,430
>> Nyt yleinen eräänlainen käsitys siitä, mihin
seuraava elementti ei mene jonoon

121
00:06:08,430 --> 00:06:12,310
on lisätä näiden kahden numerot
yhdessä, edessä ja koko,

122
00:06:12,310 --> 00:06:16,390
ja että kerron sinulle missä seuraava
elementti jonossa on menossa.

123
00:06:16,390 --> 00:06:18,130
Joten Nyt laittaa jonoon toiseen numeroon.

124
00:06:18,130 --> 00:06:20,250
Katsotaanpa laittaa jonoon 33.

125
00:06:20,250 --> 00:06:24,480
Joten 33 on menossa mennä
array sijainti 0 + 1.

126
00:06:24,480 --> 00:06:26,840
Joten tässä tapauksessa, se tulee
mennä array sijainti 1,

127
00:06:26,840 --> 00:06:29,500
ja nyt koko meidän jono on 2.

128
00:06:29,500 --> 00:06:31,840
>> Jälleen, emme muuttuvat
edessä meidän jonossa,

129
00:06:31,840 --> 00:06:34,730
koska 28 on edelleen
vanhin elementti, ja me

130
00:06:34,730 --> 00:06:38,220
haluavat to-- kun me lopulta saada
ja dequeuing, poistamalla osia

131
00:06:38,220 --> 00:06:43,300
Tästä jonosta, haluamme tietää
jossa vanhin osa on.

132
00:06:43,300 --> 00:06:48,620
Ja niin me aina tarvitse säilyttää
jotkut indikaattori, jos se on.

133
00:06:48,620 --> 00:06:50,410
Niin, että mitä 0 on siellä.

134
00:06:50,410 --> 00:06:52,910
Sitähän edessä on siellä.

135
00:06:52,910 --> 00:06:55,022
>> Katsotaanpa vuonna enqueue yksi elementti, 19.

136
00:06:55,022 --> 00:06:56,980
Olen varma, että voit arvata
jossa 19 on menossa.

137
00:06:56,980 --> 00:06:59,860
Se tulee mennä
array Sijainti numero 2.

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

139
00:07:01,570 --> 00:07:03,199
Ja nyt koko meidän jono on 3.

140
00:07:03,199 --> 00:07:04,240
Meillä on 3 elementtejä se.

141
00:07:04,240 --> 00:07:08,490
Joten jos me, ja emme aio
juuri nyt, laittaa jonoon toinen elementti,

142
00:07:08,490 --> 00:07:11,370
se mennä array sijainti
numero 3, ja koko meidän jonossa

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

144
00:07:13,160 --> 00:07:15,279
Joten olemme enqueued useita tekijöitä nyt.

145
00:07:15,279 --> 00:07:16,570
Nyt aloitamme niiden poistamiseksi.

146
00:07:16,570 --> 00:07:19,450
Katsotaanpa dequeue ne jonosta.

147
00:07:19,450 --> 00:07:23,340
>> Niin samankaltaisia ​​pop, joka on eräänlainen
analogiset tämän pinojen,

148
00:07:23,340 --> 00:07:26,180
dequeue tarvitsee hyväksyä
osoitin queue-- uudelleen,

149
00:07:26,180 --> 00:07:28,140
ellei se maailmanlaajuisesti julistettu.

150
00:07:28,140 --> 00:07:31,610
Nyt haluamme muuttaa sijainti
n jonon.

151
00:07:31,610 --> 00:07:35,050
Tästä se tavallaan tulee
peliin, että edessä muuttuja,

152
00:07:35,050 --> 00:07:37,310
koska kerran poistamme
elementti, haluamme

153
00:07:37,310 --> 00:07:40,720
siirtää sen seuraavalle vanhin elementti.

154
00:07:40,720 --> 00:07:44,180
>> Sitten haluamme vähentää
koko jonon,

155
00:07:44,180 --> 00:07:47,130
ja sitten haluamme palauttaa arvo
joka poistettiin jonosta.

156
00:07:47,130 --> 00:07:48,921
Jälleen, emme halua vain hävittää sen.

157
00:07:48,921 --> 00:07:51,170
Olemme oletettavasti purat
se queue-- olemme

158
00:07:51,170 --> 00:07:54,170
dequeuing sitä, koska emme välitä siitä.

159
00:07:54,170 --> 00:08:01,080
Joten haluamme tämän toiminnon palata
tieto tyypin arvo.

160
00:08:01,080 --> 00:08:04,360
Jälleen tässä tapauksessa arvo on kokonaisluku.

161
00:08:04,360 --> 00:08:05,670
>> Joten Nyt dequeue jotain.

162
00:08:05,670 --> 00:08:09,310
Katsotaanpa poistaa elementti jonosta.

163
00:08:09,310 --> 00:08:15,970
Jos sanomme int x vastaa & Q, et-merkki q--
jälleen se osoitin tähän q tiedot

164
00:08:15,970 --> 00:08:20,177
structure-- mitä elementti
aiotaan dequeued?

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

166
00:08:23,840 --> 00:08:29,480
Tässä tapauksessa, koska se on ensimmäinen
in, first out tietorakenne, FIFO,

167
00:08:29,480 --> 00:08:33,690
ensimmäinen asia me otetaan tämä
jono oli 28, ja niin tässä tapauksessa,

168
00:08:33,690 --> 00:08:37,245
aiomme ottaa 28 pois
jonossa, ei 19, joka on mitä

169
00:08:37,245 --> 00:08:38,870
olisimme tehneet jos tämä oli pino.

170
00:08:38,870 --> 00:08:42,220
Aiomme ottaa 28 ulos jonon.

171
00:08:42,220 --> 00:08:44,960
>> Samanlainen kuin mitä teimme kanssa
pino, emme ole oikeastaan

172
00:08:44,960 --> 00:08:47,345
menossa poistaa 28
jonosta itse,

173
00:08:47,345 --> 00:08:49,470
olemme juuri menossa eräänlainen
ja teeskennellä se ei ole siellä.

174
00:08:49,470 --> 00:08:51,678
Joten se tulee siellä
muistiin, mutta olemme vain

175
00:08:51,678 --> 00:08:57,820
menossa sellainen sivuuttaa sitä liikuttamalla
Kahdella muulla alalla meidän q tietojen

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

177
00:08:58,830 --> 00:09:00,230
Aiomme muuttaa edessä.

178
00:09:00,230 --> 00:09:04,290
Q.front on nyt menossa
olla 1, koska se on nyt

179
00:09:04,290 --> 00:09:07,740
vanhin osa meillä on
jono, koska olemme jo poistettu 28,

180
00:09:07,740 --> 00:09:10,460
joka oli entinen vanhin elementti.

181
00:09:10,460 --> 00:09:13,540
>> Ja nyt haluamme muuttaa
koko jonon

182
00:09:13,540 --> 00:09:15,780
kahteen elementtejä kolmen sijaan.

183
00:09:15,780 --> 00:09:20,450
Nyt muistaa aiemmin sanoin, kun
haluat lisätä elementtejä jono,

184
00:09:20,450 --> 00:09:26,000
me laittaa se joukko paikalla
joka on summa etu- ja koosta.

185
00:09:26,000 --> 00:09:29,050
Joten tässä tapauksessa, olemme yhä laskemisesta
se, seuraava osa jonossa,

186
00:09:29,050 --> 00:09:33,360
osaksi array sijainti 3, ja
näemme, että toinen.

187
00:09:33,360 --> 00:09:35,730
>> Joten olemme nyt dequeued meidän
ensimmäisen elementin jonosta.

188
00:09:35,730 --> 00:09:36,480
Tehdään se uudestaan.

189
00:09:36,480 --> 00:09:38,696
Katsotaanpa poistaa toinen
elementti jonosta.

190
00:09:38,696 --> 00:09:42,400
Vuonna tapauksessa nykyinen vanhin
elementti on array paikka 1.

191
00:09:42,400 --> 00:09:44,220
Sitähän q.front kertoo.

192
00:09:44,220 --> 00:09:46,980
Että vihreän laatikon kertoo, että
se vanhin elementti.

193
00:09:46,980 --> 00:09:49,310
Ja niin, X tulee 33.

194
00:09:49,310 --> 00:09:52,130
Me vain eräänlainen unohtaa
että 33 olemassa jono,

195
00:09:52,130 --> 00:09:55,100
ja me sanomme, että nyt,
uusi vanhin elementti jonossa

196
00:09:55,100 --> 00:09:58,900
on joukko sijainti 2, ja koko
jonossa, elementtien määrä

197
00:09:58,900 --> 00:10:02,152
meillä on jonossa, on 1.

198
00:10:02,152 --> 00:10:05,110
Nyt laittaa jonoon jotain, ja minä
eräänlainen antoi tämän pois toinen sitten,

199
00:10:05,110 --> 00:10:10,340
mutta jos haluamme laittaa 40 osaksi
jono, jossa on 40 menossa?

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

201
00:10:12,880 --> 00:10:17,730
No olemme laittoi pallon
vuonna q.front plus jonossa koko,

202
00:10:17,730 --> 00:10:20,850
ja niin on järkevää
todella laittaa 40 tänne.

203
00:10:20,850 --> 00:10:22,840
Nyt huomaa, että
jossain vaiheessa, aiomme

204
00:10:22,840 --> 00:10:27,980
päästä loppuun
meidän valikoima sisällä q,

205
00:10:27,980 --> 00:10:32,010
mutta hiipui pois 28 ja 33--
he todella, teknisesti

206
00:10:32,010 --> 00:10:33,300
aukiot, eikö?

207
00:10:33,300 --> 00:10:36,040
Ja niin, voimme eventually--
että sääntö lisätä

208
00:10:36,040 --> 00:10:40,390
nämä kaksi together-- me voi lopulta
täytyy mod koon kapasiteetin

209
00:10:40,390 --> 00:10:41,410
jotta voimme Ulottumamitan.

210
00:10:41,410 --> 00:10:43,620
>> Joten jos saamme elementtiin
numero 10, jos olemme

211
00:10:43,620 --> 00:10:48,790
korvaamalla se elementti numero 10, olimme
tosiasiallisesti se array sijainti 0.

212
00:10:48,790 --> 00:10:50,997
Ja jos me aioimme
array location-- anteeksi,

213
00:10:50,997 --> 00:10:53,080
jos lisäsimme niitä yhteen,
ja saimme numero

214
00:10:53,080 --> 00:10:56,330
11 olisi, jos olisimme laittaa
se, joka ei ole tässä array--

215
00:10:56,330 --> 00:10:58,200
se olisi menossa ulos pelikentältä.

216
00:10:58,200 --> 00:11:03,367
Voisimme mod 10 ja laittaa
se array paikka 1.

217
00:11:03,367 --> 00:11:04,450
Niin, että miten jonot toimivat.

218
00:11:04,450 --> 00:11:08,540
He aina mene vasemmalta
oikealle ja mahdollisesti kääri ympärille.

219
00:11:08,540 --> 00:11:11,280
Ja te tiedätte, että he
täysi jos koko, että punainen laatikko,

220
00:11:11,280 --> 00:11:13,710
tulee yhtä suuri kapasiteetti.

221
00:11:13,710 --> 00:11:16,720
Ja niin sen jälkeen olemme lisänneet 40
jono, hyvin mitä meidän täytyy tehdä?

222
00:11:16,720 --> 00:11:19,890
No, vanhin elementti
jonossa on edelleen 19,

223
00:11:19,890 --> 00:11:21,990
joten emme halua muuttaa
jonon,

224
00:11:21,990 --> 00:11:23,820
mutta nyt meillä on kaksi
elementtejä jonossa,

225
00:11:23,820 --> 00:11:28,710
ja niin haluamme lisätä
meidän koko 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Se on aika paljon se
kanssa array-pohjainen jonot,

227
00:11:31,820 --> 00:11:33,630
ja samanlainen pino,
on myös tapa

228
00:11:33,630 --> 00:11:36,450
toteuttamaan jono linkitettynä listana.

229
00:11:36,450 --> 00:11:40,150
Nyt jos tämä tieto rakenne tyyppi
näyttää tutulta, se on.

230
00:11:40,150 --> 00:11:43,780
Se ei ole yksin linkitetyn listan,
se on kaksin verroin linkitetty lista.

231
00:11:43,780 --> 00:11:46,790
Ja nyt, koska syrjään, se on
todella mahdollista toteuttaa

232
00:11:46,790 --> 00:11:50,160
jono kuin yksittäin linkitetty lista, mutta
Mielestäni kannalta visualisointi,

233
00:11:50,160 --> 00:11:53,350
se todella voi auttaa katsella
tätä kaksin verroin linkitetty lista.

234
00:11:53,350 --> 00:11:56,850
Mutta se on ehdottomasti mahdollista
tehdä tämän yksin linkitetyn listan.

235
00:11:56,850 --> 00:12:00,110
>> Joten vilkaista
mitä tämä voisi näyttää.

236
00:12:00,110 --> 00:12:02,750
Jos haluamme enquue--
niin nyt, jälleen olemme

237
00:12:02,750 --> 00:12:05,360
vaihtamalla linkitetty-lista
mallia täällä.

238
00:12:05,360 --> 00:12:08,420
Jos haluamme laittaa jonoon, haluamme
lisätä uusi elementti, hyvin

239
00:12:08,420 --> 00:12:09,730
mitä meidän täytyy tehdä?

240
00:12:09,730 --> 00:12:12,770
No, ensinnäkin, koska
lisäämme loppuun

241
00:12:12,770 --> 00:12:15,520
ja poistamalla
alkaa, emme todennäköisesti

242
00:12:15,520 --> 00:12:20,050
haluavat säilyttää viitteitä sekä
pää ja pyrstö linkitetyn listan?

243
00:12:20,050 --> 00:12:22,660
Häntä on toinen termi
loppuun linkitetyn listan,

244
00:12:22,660 --> 00:12:24,496
viimeinen elementti linkitetty lista.

245
00:12:24,496 --> 00:12:26,620
Ja nämä luultavasti,
uudelleen, hyödyttää meitä

246
00:12:26,620 --> 00:12:28,477
jos ne ovat globaaleja muuttujia.

247
00:12:28,477 --> 00:12:31,060
Mutta nyt jos haluamme lisätä uuden
elementti mitä meidän täytyy tehdä?

248
00:12:31,060 --> 00:12:35,262
Mitä me vain [? Malak?] tai dynaamisesti
kohdentaa uusi solmu itsellemme.

249
00:12:35,262 --> 00:12:38,220
Ja sitten, aivan kuten silloin yhdenkään
elementti kaksinkertaisesti linkitetty lista me,

250
00:12:38,220 --> 00:12:40,410
vain lajitella of--
Nuo viimeiset kolme vaihetta täällä

251
00:12:40,410 --> 00:12:43,330
ovat vain kaikki muuttoa
viitteitä oikealla tavalla

252
00:12:43,330 --> 00:12:46,710
niin että elementti saa lisätä
ketju rikkomatta ketjua

253
00:12:46,710 --> 00:12:49,580
tai tehdä jonkinlainen virhe
tai ottaa jonkinlainen onnettomuus

254
00:12:49,580 --> 00:12:54,505
tapahtua jolloin me vahingossa
orpo joitakin osia meidän jonossa.

255
00:12:54,505 --> 00:12:55,880
Tässä mitä tämä voisi näyttää.

256
00:12:55,880 --> 00:13:00,980
Haluamme lisätä elementtiin
10 loppuun tämän jonon.

257
00:13:00,980 --> 00:13:03,380
Joten vanhin elementti täällä
edustaa pää.

258
00:13:03,380 --> 00:13:06,800
Se on ensimmäinen asia laitoimme
tähän hypoteettinen jono täällä.

259
00:13:06,800 --> 00:13:10,430
Ja hännän, 13, on kaikkein
viimeksi lisätyt elementti.

260
00:13:10,430 --> 00:13:17,030
Joten jos haluamme laittaa jonoon 10 kielelle
tämä jono, haluamme laittaa sen jälkeen 13.

261
00:13:17,030 --> 00:13:19,860
Ja niin aiomme dynaamisesti
jakaa tilaa uusi solmu

262
00:13:19,860 --> 00:13:23,280
ja tarkista for varmistaa
meillä ei ole muisti vika.

263
00:13:23,280 --> 00:13:27,040
Sitten aiomme
pannaan 10 tuohon solmu,

264
00:13:27,040 --> 00:13:30,030
ja nyt meidän on oltava varovainen
miten järjestämme osoittimet

265
00:13:30,030 --> 00:13:32,180
joten emme katkaisemiseksi.

266
00:13:32,180 --> 00:13:38,910
>> Voimme asettaa 10: n edellinen kenttä
osoittamaan takaisin vanhaan häntää,

267
00:13:38,910 --> 00:13:41,620
ja koska '10 on
uusi häntä jossain vaiheessa

268
00:13:41,620 --> 00:13:44,459
mennessä kaikki nämä
ketjut on kytketty,

269
00:13:44,459 --> 00:13:46,250
mikään ei tulossa
kun 10 nyt.

270
00:13:46,250 --> 00:13:49,880
Ja niin 10 seuraava osoitin
tulee kohta null,

271
00:13:49,880 --> 00:13:53,580
ja sitten kun me teemme tämän, kun olemme
liitetty 10 taaksepäin ketjun,

272
00:13:53,580 --> 00:13:57,780
voimme ottaa vanha pää, tai tekosyy
minua, vanha hännän jonossa.

273
00:13:57,780 --> 00:14:02,980
Vanha jonon,
13, ja sen osoittamaan 10.

274
00:14:02,980 --> 00:14:08,220
Ja nyt, tässä vaiheessa, olemme
enqueued numero 10 tähän jonoon.

275
00:14:08,220 --> 00:14:14,740
Kaikki meidän täytyy tehdä nyt on vain siirtää
tail viitata 10 sijasta 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing on oikeastaan
hyvin samankaltainen popping

277
00:14:17,630 --> 00:14:21,710
pinosta joka on
toteutetaan linkitettynä listana

278
00:14:21,710 --> 00:14:24,040
jos olet nähnyt pinot video.

279
00:14:24,040 --> 00:14:27,280
Meidän tarvitsee vain alkaa
alkaa, löytää toinen elementti,

280
00:14:27,280 --> 00:14:30,480
vapauttaa ensimmäinen elementti,
ja sitten siirtyä pää

281
00:14:30,480 --> 00:14:32,930
osoittamaan toinen elementti.

282
00:14:32,930 --> 00:14:37,920
Luultavasti parempi visualisoida sitä
vain olla erityisen selkeä siitä.

283
00:14:37,920 --> 00:14:39,230
Joten tässä on meidän jono uudelleen.

284
00:14:39,230 --> 00:14:42,600
12 on vanhin elementti
meidän jonossa, pää.

285
00:14:42,600 --> 00:14:46,210
10 on uusin elementti
meidän jonossa, meidän häntä.

286
00:14:46,210 --> 00:14:49,310
>> Ja niin kun haluamme
jotta dequeue elementti,

287
00:14:49,310 --> 00:14:52,202
haluamme poistaa vanhimman elementti.

288
00:14:52,202 --> 00:14:52,910
Joten mitä me teemme?

289
00:14:52,910 --> 00:14:55,243
No asetamme läpikäynti osoitin
että alkaa pää,

290
00:14:55,243 --> 00:14:57,840
ja siirrymme niin, että se
viittaa toinen elementti

291
00:14:57,840 --> 00:15:02,290
Tämän queue-- jotain sanomalla Trav
vastaa trav nuolta, esimerkiksi,

292
00:15:02,290 --> 00:15:07,170
siirtyisi trav siellä osoittamaan
15, joka, sen jälkeen kun me dequeue 12,

293
00:15:07,170 --> 00:15:13,030
tai sen jälkeen poistamme 12, tulee
tulee sitten vanhin elementti.

294
00:15:13,030 --> 00:15:16,360
>> Nyt meillä otteen ensimmäinen
elementti kautta osoitin pää

295
00:15:16,360 --> 00:15:19,440
ja toinen elementti
kautta osoitin Trav.

296
00:15:19,440 --> 00:15:25,170
Voimme nyt vapaa pää, ja sitten voimme
sano mitään tulee ennen 15 enää.

297
00:15:25,170 --> 00:15:29,990
Jotta voimme muuttaa 15: n edellinen
osoitin osoittamaan null,

298
00:15:29,990 --> 00:15:31,874
ja me vain siirtää pään yli.

299
00:15:31,874 --> 00:15:32,540
Ja siellä mennään.

300
00:15:32,540 --> 00:15:35,840
Nyt meillä on onnistuneesti
dequeued 12, ja nyt me

301
00:15:35,840 --> 00:15:39,180
on toinen jono 4 elementtejä.

302
00:15:39,180 --> 00:15:41,700
Se on aika paljon kaikki
on jonoja,

303
00:15:41,700 --> 00:15:45,810
molemmat array-pohjainen ja linkitetty-lista perustuu.

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

305
00:15:46,860 --> 00:15:49,100
Tämä on CS 50.

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