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

2
00:00:05,204 --> 00:00:07,370
Doug LLOYD: Dakle, ako ste
gledao video na stog,

3
00:00:07,370 --> 00:00:09,870
ovo je vjerojatno će se osjećati
kao malo deja vu.

4
00:00:09,870 --> 00:00:13,850
To će vrlo sličan konceptu,
samo uz blagi twist na njega.

5
00:00:13,850 --> 00:00:15,530
Idemo sada govoriti o redova.

6
00:00:15,530 --> 00:00:19,350
Pa red, slično kao stog,
je druga vrsta strukture podataka

7
00:00:19,350 --> 00:00:22,412
da možemo koristiti za održavanje
podataka u organizirani način.

8
00:00:22,412 --> 00:00:24,120
Slično stog,
može se provoditi

9
00:00:24,120 --> 00:00:27,000
kao polje ili popis povezan.

10
00:00:27,000 --> 00:00:30,320
Za razliku od hrpe, pravila
koje koristimo za određivanje

11
00:00:30,320 --> 00:00:34,210
kada stvari dobiti dodano i uklonjen iz
red su malo drugačiji.

12
00:00:34,210 --> 00:00:36,590
>> Za razliku od hrpe koja
je LIFO struktura,

13
00:00:36,590 --> 00:00:45,610
trajati u, prvi van, red je FIFO
Struktura, FIFO, prvi u, prvi van.

14
00:00:45,610 --> 00:00:49,320
Sada redovima, vjerojatno
ima analogiju u redu.

15
00:00:49,320 --> 00:00:52,820
Ako ste ikada bili u redu na
zabavni park ili u banci,

16
00:00:52,820 --> 00:00:56,430
postoji neka vrsta pravednosti
provedbenih struktura.

17
00:00:56,430 --> 00:00:59,160
Prva osoba u redu na
banka je prva osoba

18
00:00:59,160 --> 00:01:00,760
tko će razgovarati s pripovjedač.

19
00:01:00,760 --> 00:01:03,522
>> Bilo bi vrsta utrci
na dnu, ako je jedini način

20
00:01:03,522 --> 00:01:06,730
moraš razgovarati s pripovjedač Na
banka je trebala biti posljednja osoba u redu.

21
00:01:06,730 --> 00:01:09,146
Svatko bi uvijek žele
biti posljednja osoba u redu,

22
00:01:09,146 --> 00:01:12,580
a osoba koja je bila prije
koji je čekao neko vrijeme,

23
00:01:12,580 --> 00:01:14,715
mogao biti tamo satima,
i sati, a radno vrijeme

24
00:01:14,715 --> 00:01:17,590
prije nego što oni imaju priliku da se zapravo
povući novac u banci.

25
00:01:17,590 --> 00:01:22,510
I tako redovi su vrsta od
pravičnosti provedbu strukturu.

26
00:01:22,510 --> 00:01:25,780
No, to ne znači nužno
da hrpe su loša stvar, samo

27
00:01:25,780 --> 00:01:28,160
da redovi su još jedan način da to učinite.

28
00:01:28,160 --> 00:01:32,420
Pa opet red je prvi,
van, u odnosu na hrpu koja traje u,

29
00:01:32,420 --> 00:01:34,440
Prvo se.

30
00:01:34,440 --> 00:01:36,190
Slično stog,
imamo dvije operacije

31
00:01:36,190 --> 00:01:38,470
da možemo izvesti na redu.

32
00:01:38,470 --> 00:01:43,910
Imena su u red, koji je dodati
novi element na kraj reda,

33
00:01:43,910 --> 00:01:47,330
i dequeue, koji je
ukloniti najstariji

34
00:01:47,330 --> 00:01:49,670
Element s prednje red.

35
00:01:49,670 --> 00:01:53,600
Tako ćemo dodati elemente
na kraju reda,

36
00:01:53,600 --> 00:01:57,220
i mi ćemo ukloniti elemente
s prednje red.

37
00:01:57,220 --> 00:02:00,790
Opet, s stog, bili smo dodavanjem
Elementi na vrhu snopa

38
00:02:00,790 --> 00:02:03,380
i uklanjanje elemenata
s vrha dimnjaka.

39
00:02:03,380 --> 00:02:07,570
Tako je s enqueue, to je dodao da
kraj, uklanjanje s prednje strane.

40
00:02:07,570 --> 00:02:10,639
Dakle, najstarija stvar u tu
Uvijek je sljedeća stvar

41
00:02:10,639 --> 00:02:13,620
izaći ako pokušamo
i dequeue nešto.

42
00:02:13,620 --> 00:02:18,330
>> Pa opet, sa redovima, možemo
implementacije array-based

43
00:02:18,330 --> 00:02:20,110
i povezao-lista temelji implementacije.

44
00:02:20,110 --> 00:02:24,620
Počet ćemo opet s
implementacije array-based.

45
00:02:24,620 --> 00:02:27,070
Definicija struktura
izgleda prilično slično.

46
00:02:27,070 --> 00:02:30,720
Imamo još niz
Postoji tipa podataka vrijednosti,

47
00:02:30,720 --> 00:02:32,690
tako da može držati proizvoljne vrste podataka.

48
00:02:32,690 --> 00:02:35,570
Mi opet ćemo koristiti
cijeli brojevi u ovom primjeru.

49
00:02:35,570 --> 00:02:39,830
>> I baš kao što je s našim
Provedba snop niz bazi,

50
00:02:39,830 --> 00:02:42,340
jer smo rabeći
polje, mi nužno

51
00:02:42,340 --> 00:02:46,850
imati taj ograničenje da je C vrsta
od provodi na nas, što je i mi

52
00:02:46,850 --> 00:02:51,670
nemaju dinamizam u našem
sposobnost da rastu i smanjiti niz.

53
00:02:51,670 --> 00:02:55,710
Moramo odlučiti na početku
što je najveći broj stvari

54
00:02:55,710 --> 00:02:59,300
koje možemo staviti u ovaj
red, au ovom slučaju,

55
00:02:59,300 --> 00:03:02,070
Kapacitet će biti neki funta
definirani konstanta u našem kodu.

56
00:03:02,070 --> 00:03:05,430
A za potrebe ovog
Video, kapacitet će biti 10.

57
00:03:05,430 --> 00:03:07,690
>> Moramo pratiti
prednji dio red

58
00:03:07,690 --> 00:03:11,160
tako da znamo što je element
želimo dequeue,

59
00:03:11,160 --> 00:03:15,070
i mi također treba pratiti
nešto else-- broj elemenata

60
00:03:15,070 --> 00:03:16,690
da smo u našem redu.

61
00:03:16,690 --> 00:03:19,360
Obavijest nismo praćenje
na kraju reda, samo

62
00:03:19,360 --> 00:03:21,150
veličina reda čekanja.

63
00:03:21,150 --> 00:03:24,310
A razlog za to će, nadamo se
postalo malo jasnije u trenutku.

64
00:03:24,310 --> 00:03:26,143
Nakon što smo završili
ovaj tip definicija,

65
00:03:26,143 --> 00:03:29,080
imamo novi tip podataka
zove red, koji sada možemo

66
00:03:29,080 --> 00:03:30,630
proglasiti varijable te vrste podataka.

67
00:03:30,630 --> 00:03:35,350
I pomalo zbunjujuće, odlučio sam
nazvati ovaj red q, pismo

68
00:03:35,350 --> 00:03:38,090
q umjesto tipa podataka q.

69
00:03:38,090 --> 00:03:39,600
>> Dakle, ovdje je naš red.

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

71
00:03:40,700 --> 00:03:45,730
Sadrži tri člana ili tri
polja, niz veličina kapaciteta.

72
00:03:45,730 --> 00:03:47,340
U ovom slučaju, kapacitet je 10.

73
00:03:47,340 --> 00:03:49,580
A ovo polje je
će održati prirodna broja.

74
00:03:49,580 --> 00:03:55,240
U zelenom je ispred naše red je
Sljedeći element biti uklonjena, a crveno

75
00:03:55,240 --> 00:03:58,610
će biti veličine redu,
koliko elementi su trenutno

76
00:03:58,610 --> 00:04:01,190
postoje u redu.

77
00:04:01,190 --> 00:04:05,300
Dakle, ako kažemo q.front jednaki
0, a veličina q.size jednak 0--

78
00:04:05,300 --> 00:04:07,120
mi smo stavljajući 0s u tim područjima.

79
00:04:07,120 --> 00:04:11,070
I u ovom trenutku, mi smo prilično mnogo
spremni za početak rada s našim red.

80
00:04:11,070 --> 00:04:14,140
>> Dakle, prva operacija možemo
obavljaju je enqueue nešto,

81
00:04:14,140 --> 00:04:16,860
dodati novi element
kraj reda.

82
00:04:16,860 --> 00:04:19,089
Pa ono što trebamo
učiniti u općem slučaju?

83
00:04:19,089 --> 00:04:23,690
Pa ova funkcija enqueue potrebama
prihvatiti pokazivač na naš red.

84
00:04:23,690 --> 00:04:26,370
Opet, ako je proglasio
naš red na globalnoj razini,

85
00:04:26,370 --> 00:04:29,490
ne bi trebao to učiniti
nužno, ali općenito, što

86
00:04:29,490 --> 00:04:32,330
moraju prihvatiti naputke
strukturama podataka

87
00:04:32,330 --> 00:04:35,040
ovako, jer inače,
mi smo u prolazu value-- smo

88
00:04:35,040 --> 00:04:38,140
prolazi u kopijama redu,
pa nismo zapravo mijenja

89
00:04:38,140 --> 00:04:41,050
red koji namjeravamo mijenjati.

90
00:04:41,050 --> 00:04:44,860
>> Druga stvar što treba učiniti je prihvatiti
element podataka odgovarajućeg tipa.

91
00:04:44,860 --> 00:04:46,818
Opet, u ovom slučaju, to je
će biti cijeli brojevi,

92
00:04:46,818 --> 00:04:49,330
ali mogli proizvoljno
proglasiti tip podataka kao vrijednost

93
00:04:49,330 --> 00:04:51,160
i koristiti to općenito.

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

95
00:04:56,030 --> 00:04:58,573
Tada smo zapravo žele
staviti da su podaci u redu.

96
00:04:58,573 --> 00:05:01,490
U tom slučaju, stavljanje je u
točno mjesto naše ponude,

97
00:05:01,490 --> 00:05:05,040
a onda želimo promijeniti veličinu
u redu, koliko smo elemente

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

99
00:05:07,050 --> 00:05:07,990
>> Tako ćemo početi.

100
00:05:07,990 --> 00:05:10,890
Evo, opet, da je general
Obrazac funkcija izjava

101
00:05:10,890 --> 00:05:13,980
za ono u red moglo izgledati.

102
00:05:13,980 --> 00:05:14,910
I ovdje mi ići.

103
00:05:14,910 --> 00:05:18,335
Idemo enqueue broj
28 u redu.

104
00:05:18,335 --> 00:05:19,460
Pa što ćemo učiniti?

105
00:05:19,460 --> 00:05:23,390
Pa, ispred naše red je
na 0 ° C, te veličine našeg reda

106
00:05:23,390 --> 00:05:29,680
je na 0, i tako smo vjerojatno želite staviti
broj 28 u broj polja elemenata

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

108
00:05:31,124 --> 00:05:32,540
Dakle, sada smo postavljeni da postoji.

109
00:05:32,540 --> 00:05:34,820
Pa sad što nam treba mijenjati?

110
00:05:34,820 --> 00:05:37,090
Mi ne želimo mijenjati
prednji dio reda,

111
00:05:37,090 --> 00:05:40,850
jer želimo znati što elementa
ćemo možda morati dequeue kasnije.

112
00:05:40,850 --> 00:05:44,020
Dakle, razlog zbog kojeg smo se ispred se
je vrsta pokazatelj što je

113
00:05:44,020 --> 00:05:46,439
najstarija stvar u nizu.

114
00:05:46,439 --> 00:05:49,730
Pa najstarija stvar u array-- u
Zapravo, jedina stvar u nizu u pravu

115
00:05:49,730 --> 00:05:53,540
now-- je 28, što je
na polja lokaciji 0.

116
00:05:53,540 --> 00:05:56,160
Dakle, mi ne želimo
promijeniti da zeleni broj,

117
00:05:56,160 --> 00:05:57,910
jer to je najstariji dio.

118
00:05:57,910 --> 00:06:00,510
Umjesto toga, želimo promijeniti veličinu.

119
00:06:00,510 --> 00:06:04,110
Dakle, u ovom slučaju, mi ćemo
povećajte veličinu do 1.

120
00:06:04,110 --> 00:06:08,430
>> Sada opći vrsta ideju gdje
Sljedeći element će ići u redu

121
00:06:08,430 --> 00:06:12,310
se dodati tih dva broja
zajedno, prednji i veličina,

122
00:06:12,310 --> 00:06:16,390
i da ću ti reći gdje je sljedeći
element u redu je ići.

123
00:06:16,390 --> 00:06:18,130
Dakle, sada ćemo enqueue drugi broj.

124
00:06:18,130 --> 00:06:20,250
Idemo u red 33.

125
00:06:20,250 --> 00:06:24,480
Dakle, 33 će ići u
Niz položaj 0 i 1.

126
00:06:24,480 --> 00:06:26,840
Dakle, u ovom slučaju, to se događa
ići u polja položaju 1,

127
00:06:26,840 --> 00:06:29,500
a sada je veličina našeg reda 2.

128
00:06:29,500 --> 00:06:31,840
>> Opet, mi ne mijenjamo
prednji našeg reda,

129
00:06:31,840 --> 00:06:34,730
jer 28 je i dalje
Najstariji je element, a mi

130
00:06:34,730 --> 00:06:38,220
Želite to-- kad smo na kraju dobiti
da dequeuing, uklanjanjem elemenata

131
00:06:38,220 --> 00:06:43,300
iz ovog reda, želimo znati
gdje je najstariji element.

132
00:06:43,300 --> 00:06:48,620
I tako smo uvijek treba održavati
neki pokazatelj gdje je to.

133
00:06:48,620 --> 00:06:50,410
Dakle, to je ono što je tu za 0.

134
00:06:50,410 --> 00:06:52,910
To je ono ispred je tamo.

135
00:06:52,910 --> 00:06:55,022
>> Idemo u enqueue još jedan element, 19.

136
00:06:55,022 --> 00:06:56,980
Siguran sam da možete pogoditi
gdje 19 će ići.

137
00:06:56,980 --> 00:06:59,860
To će ići u
Niz položaj broj 2.

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

139
00:07:01,570 --> 00:07:03,199
I sada je veličina našeg reda je 3.

140
00:07:03,199 --> 00:07:04,240
Imamo 3 elemente u njoj.

141
00:07:04,240 --> 00:07:08,490
Dakle, ako smo, a nećemo
upravo sada, u red još jedan element,

142
00:07:08,490 --> 00:07:11,370
to će ići u polja položaja
broj 3, a veličina našeg reda

143
00:07:11,370 --> 00:07:13,160
će biti 4.

144
00:07:13,160 --> 00:07:15,279
Tako smo enqueued nekoliko elemenata sada.

145
00:07:15,279 --> 00:07:16,570
Sada ćemo početi da ih ukloniti.

146
00:07:16,570 --> 00:07:19,450
Idemo ih dequeue iz reda čekanja.

147
00:07:19,450 --> 00:07:23,340
>> Dakle, slično kao pop, koja je vrsta
od analog to za dimnjaka,

148
00:07:23,340 --> 00:07:26,180
dequeue treba prihvatiti
pokazivač na queue-- opet,

149
00:07:26,180 --> 00:07:28,140
osim ako je na globalnoj razini je proglašen.

150
00:07:28,140 --> 00:07:31,610
Sada želimo promijeniti položaj
prednje reda.

151
00:07:31,610 --> 00:07:35,050
Ovo je mjesto gdje je vrsta u pitanju
u igru, da je prednji varijabla,

152
00:07:35,050 --> 00:07:37,310
jer jednom uklonimo
element, želimo

153
00:07:37,310 --> 00:07:40,720
ga premjestiti na sljedeću najstarijeg elementa.

154
00:07:40,720 --> 00:07:44,180
>> Zatim želimo smanjiti
veličina reda,

155
00:07:44,180 --> 00:07:47,130
a onda želimo vratiti vrijednost
koji je uklonjen iz reda.

156
00:07:47,130 --> 00:07:48,921
Opet, mi ne želimo samo ga odbaciti.

157
00:07:48,921 --> 00:07:51,170
Mi vjerojatno su vađenje
to iz queue-- smo

158
00:07:51,170 --> 00:07:54,170
to dequeuing jer mi je stalo do nje.

159
00:07:54,170 --> 00:08:01,080
Dakle, želimo ova funkcija za povratak
element podataka tipa vrijednosti.

160
00:08:01,080 --> 00:08:04,360
Opet, u ovom slučaju, vrijednost broj.

161
00:08:04,360 --> 00:08:05,670
>> Dakle, sada ćemo dequeue nešto.

162
00:08:05,670 --> 00:08:09,310
Idemo uklanjanje element iz reda čekanja.

163
00:08:09,310 --> 00:08:15,970
Ako kažemo int x jednak & q, znak za struju q--
opet to je pointer na ovom q podataka

164
00:08:15,970 --> 00:08:20,177
structure-- što je element
će se dequeued?

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

166
00:08:23,840 --> 00:08:29,480
U ovom slučaju, jer je prvi
u, prvi van strukture podataka, FIFO,

167
00:08:29,480 --> 00:08:33,690
prva stvar koju smo stavili u ovu
red je 28, pa u ovom slučaju,

168
00:08:33,690 --> 00:08:37,245
ćemo uzeti 28 iz
red, a ne 19, što je ono

169
00:08:37,245 --> 00:08:38,870
bismo učinili ako je to hrpa.

170
00:08:38,870 --> 00:08:42,220
Idemo uzeti 28 iz reda.

171
00:08:42,220 --> 00:08:44,960
>> Slično onome što smo učinili s
stog, nismo zapravo

172
00:08:44,960 --> 00:08:47,345
će izbrisati 28
iz samog reda,

173
00:08:47,345 --> 00:08:49,470
samo ćemo se vrste
od pretvarati da ne postoji.

174
00:08:49,470 --> 00:08:51,678
Dakle, to će ostati tamo
u memoriji, ali mi smo samo

175
00:08:51,678 --> 00:08:57,820
ide vrsta ignorirati pomicanjem
druga dva područja naše q podataka

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

177
00:08:58,830 --> 00:09:00,230
Idemo mijenjati ispred.

178
00:09:00,230 --> 00:09:04,290
Q.front sada će
biti 1, zato što je sada

179
00:09:04,290 --> 00:09:07,740
najstariji elemenat imamo u našem
red, jer smo već uklonjena 28,

180
00:09:07,740 --> 00:09:10,460
koji je bio bivši najstariji elemenat.

181
00:09:10,460 --> 00:09:13,540
>> A sada, želimo promijeniti
veličina reda

182
00:09:13,540 --> 00:09:15,780
dva elementa umjesto tri.

183
00:09:15,780 --> 00:09:20,450
Zapamti ranije sam rekao kad smo
želite dodati elemente na red,

184
00:09:20,450 --> 00:09:26,000
smo ga stavili na lokaciji polja
koja je zbroj prednje i veličine.

185
00:09:26,000 --> 00:09:29,050
Dakle, u ovom slučaju, mi smo još uvijek stavljajući
to, sljedeći element u redu,

186
00:09:29,050 --> 00:09:33,360
u položaju 3 polja, i
vidjet ćemo da je u sekundi.

187
00:09:33,360 --> 00:09:35,730
>> Dakle, sada smo dequeued naše
Prvi element iz reda čekanja.

188
00:09:35,730 --> 00:09:36,480
Idemo to učiniti opet.

189
00:09:36,480 --> 00:09:38,696
Idemo uklanjanje drugi
element iz reda.

190
00:09:38,696 --> 00:09:42,400
U tom slučaju, struja najstariji
element je niz lokacija 1.

191
00:09:42,400 --> 00:09:44,220
To je ono što q.front nam govori.

192
00:09:44,220 --> 00:09:46,980
To zelena kutija nam govori da
to je najstariji dio.

193
00:09:46,980 --> 00:09:49,310
I tako, x će postati 33.

194
00:09:49,310 --> 00:09:52,130
Mi ćemo samo vrsta zaboraviti
da 33 postoji u nizu,

195
00:09:52,130 --> 00:09:55,100
a mi ćemo reći da danas,
Novi najstariji element u redu

196
00:09:55,100 --> 00:09:58,900
je na položaju 2, polja i veličine
u redu, broj elemenata

197
00:09:58,900 --> 00:10:02,152
imamo u redu, je 1.

198
00:10:02,152 --> 00:10:05,110
Sada enqueue nešto, a ja
vrsta je dao to daleko prije sekundu,

199
00:10:05,110 --> 00:10:10,340
ali ako želimo staviti 40 u
red, gdje je 40 će ići?

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

201
00:10:12,880 --> 00:10:17,730
Pa smo ga stavljajući
u q.front plus red veličine,

202
00:10:17,730 --> 00:10:20,850
pa ima smisla
zapravo staviti 40 ovdje.

203
00:10:20,850 --> 00:10:22,840
Sada primijetite da u
nekom trenutku, idemo

204
00:10:22,840 --> 00:10:27,980
doći do kraja
naš niz unutar q,

205
00:10:27,980 --> 00:10:32,010
ali to izblijedi iz 28 i 33--
oni su zapravo, tehnički

206
00:10:32,010 --> 00:10:33,300
otvoreni prostori, zar ne?

207
00:10:33,300 --> 00:10:36,040
I tako, možemo eventually--
to pravilo dodavanja

208
00:10:36,040 --> 00:10:40,390
ta dva together-- možda ćemo na kraju
trebate mod po veličini kapaciteta

209
00:10:40,390 --> 00:10:41,410
tako da možemo omotati oko.

210
00:10:41,410 --> 00:10:43,620
>> Dakle, ako smo dobili na elementu
broj 10, ako smo

211
00:10:43,620 --> 00:10:48,790
zamjenjuje ga u elementu brojem 10, što bi
zapravo ga staviti u polja položaj 0.

212
00:10:48,790 --> 00:10:50,997
I ako su idući u
Niz mjesto-- me ispričati,

213
00:10:50,997 --> 00:10:53,080
ako ih zbroje zajedno,
i moramo broj

214
00:10:53,080 --> 00:10:56,330
11 će biti u kojoj ćemo morati staviti
on, koji ne postoji u ovom array--

215
00:10:56,330 --> 00:10:58,200
to bi se događa izvan granica.

216
00:10:58,200 --> 00:11:03,367
Mogli bismo mod za 10 i staviti
to u polja položaj 1.

217
00:11:03,367 --> 00:11:04,450
Dakle, to je kako redovi rade.

218
00:11:04,450 --> 00:11:08,540
Uvijek ići s lijeva
na desno i eventualno zaokrenuti.

219
00:11:08,540 --> 00:11:11,280
A ti znaš da su oni
pune veličine, ako, kako crvenoj kutiji,

220
00:11:11,280 --> 00:11:13,710
postaje jednak kapacitetu.

221
00:11:13,710 --> 00:11:16,720
I tako, nakon što smo je dodao 40 do
red, i što trebamo učiniti?

222
00:11:16,720 --> 00:11:19,890
Pa, najstariji elemenat
u redu je još uvijek 19,

223
00:11:19,890 --> 00:11:21,990
pa ne želimo mijenjati
prednji dio reda,

224
00:11:21,990 --> 00:11:23,820
ali sada imamo dva
elementi u redu,

225
00:11:23,820 --> 00:11:28,710
i tako želimo povećati
Naša veličina od 1 do 2.

226
00:11:28,710 --> 00:11:31,820
>> To je uglavnom to s
rad s redovima array-based,

227
00:11:31,820 --> 00:11:33,630
i slično stog,
tu je i način

228
00:11:33,630 --> 00:11:36,450
provoditi red kao popis povezane.

229
00:11:36,450 --> 00:11:40,150
Sada, ako je ova vrsta struktura podataka
izgleda upoznat s tobom, to je.

230
00:11:40,150 --> 00:11:43,780
To nije popis s pojedinačno povezani,
to je popis s dvostruko povezani.

231
00:11:43,780 --> 00:11:46,790
I sada, kao na stranu, to je
zapravo moguće provesti

232
00:11:46,790 --> 00:11:50,160
red kao popis za pojedinačno povezani, ali
Mislim u smislu vizualizacije,

233
00:11:50,160 --> 00:11:53,350
to zapravo može pomoći kako bi vidjeli
ovo kao popis dvostruko povezani.

234
00:11:53,350 --> 00:11:56,850
Ali, to je svakako moguće
to što je popis za pojedinačno povezane.

235
00:11:56,850 --> 00:12:00,110
>> Tako ćemo imati pogled na
što bi to moglo izgledati.

236
00:12:00,110 --> 00:12:02,750
Ako želimo enquue--
pa sad, opet smo

237
00:12:02,750 --> 00:12:05,360
prebacivanje na povezanom-liste
temelji modela ovdje.

238
00:12:05,360 --> 00:12:08,420
Ako želimo u red, želimo
dodati novi element, i

239
00:12:08,420 --> 00:12:09,730
ono što trebamo učiniti?

240
00:12:09,730 --> 00:12:12,770
Pa, prije svega, jer je
mi smo dodajući da do kraja

241
00:12:12,770 --> 00:12:15,520
i uklanjanje iz
početak, vjerojatno ćemo

242
00:12:15,520 --> 00:12:20,050
želite zadržati upućuje na obje
glava i rep popisa povezane?

243
00:12:20,050 --> 00:12:22,660
Rep je drugi izraz za
kraj popisa povezani,

244
00:12:22,660 --> 00:12:24,496
posljednji element u popisu povezane.

245
00:12:24,496 --> 00:12:26,620
A to će vjerojatno,
opet, biti koristan za nas

246
00:12:26,620 --> 00:12:28,477
ako su globalne varijable.

247
00:12:28,477 --> 00:12:31,060
Ali sada, ako želimo dodati novi
Element što moramo učiniti?

248
00:12:31,060 --> 00:12:35,262
Ono što smo upravo [? Malak?] ili dinamički
izdvojiti naš novi čvor za sebe.

249
00:12:35,262 --> 00:12:38,220
A onda, baš kao i kada smo dodali bilo
element dvostruko povezane liste mi,

250
00:12:38,220 --> 00:12:40,410
samo morati sortirati of--
one posljednje tri koraka ovdje

251
00:12:40,410 --> 00:12:43,330
samo su sve o pomicanjem
upućuje na ispravan način

252
00:12:43,330 --> 00:12:46,710
tako da element dodaje na
lanac bez razbijanje lanca

253
00:12:46,710 --> 00:12:49,580
ili stvaranje neke vrste pogreške
ili imaju neku vrstu nesreće

254
00:12:49,580 --> 00:12:54,505
dogoditi pri čemu smo se slučajno
siroče neke elemente našeg reda.

255
00:12:54,505 --> 00:12:55,880
Evo što bi to moglo izgledati.

256
00:12:55,880 --> 00:13:00,980
Želimo dodati element
10 do kraja ovog reda.

257
00:13:00,980 --> 00:13:03,380
Dakle, najstariji elemenat ovdje
zastupa glavu.

258
00:13:03,380 --> 00:13:06,800
To je prva stvar smo stavili
u tom hipotetskom red ovdje.

259
00:13:06,800 --> 00:13:10,430
I rep, 13, je najviše
Nedavno dodano element.

260
00:13:10,430 --> 00:13:17,030
I tako, ako želimo u red 10 u
ovaj red, želimo ga staviti nakon 13 godina.

261
00:13:17,030 --> 00:13:19,860
I tako ćemo dinamički
izdvojiti prostor za novi čvor

262
00:13:19,860 --> 00:13:23,280
i provjerite null bi bili sigurni
nemamo neuspjeh memorije.

263
00:13:23,280 --> 00:13:27,040
Onda ćemo
staviti 10 u taj čvor,

264
00:13:27,040 --> 00:13:30,030
a sada moramo biti oprezni
o tome kako organiziramo upućuje

265
00:13:30,030 --> 00:13:32,180
tako da ne razbiti lanac.

266
00:13:32,180 --> 00:13:38,910
>> Možemo postaviti 10 je prethodno polje
ukazati natrag na stari rep,

267
00:13:38,910 --> 00:13:41,620
a od '10 će biti
Novi rep u nekom trenutku

268
00:13:41,620 --> 00:13:44,459
u vrijeme svih tih
lanci su povezani,

269
00:13:44,459 --> 00:13:46,250
ništa ne će doći
Nakon 10 sada.

270
00:13:46,250 --> 00:13:49,880
I tako 10 je sljedeći pokazivač
će ukazati na null,

271
00:13:49,880 --> 00:13:53,580
a onda nakon što smo to učinili, nakon što imamo
povezano 10 unatrag lancu,

272
00:13:53,580 --> 00:13:57,780
možemo uzeti staru glavu, ili, oprostite
ja, stari rep red.

273
00:13:57,780 --> 00:14:02,980
Stari kraj reda,
13, a čine ga istaknuti do 10.

274
00:14:02,980 --> 00:14:08,220
I sada, u ovom trenutku, imamo
enqueued broj 10 u ovaj red.

275
00:14:08,220 --> 00:14:14,740
Sve što trebate učiniti sada je samo premjestiti
Rep ukazati na 10, umjesto na 13 godina.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing je zapravo
Vrlo slično iskakanje

277
00:14:17,630 --> 00:14:21,710
iz dimnjaka koji je
provodi kao popis povezan

278
00:14:21,710 --> 00:14:24,040
Ako ste vidjeli hrpe videa.

279
00:14:24,040 --> 00:14:27,280
Sve što trebate učiniti je početi na
početak, pronaći drugi element,

280
00:14:27,280 --> 00:14:30,480
oslobodi prvi element,
a zatim pomaknite glavu

281
00:14:30,480 --> 00:14:32,930
ukazati na drugom elementu.

282
00:14:32,930 --> 00:14:37,920
Vjerojatno bolje da ga vizualizirati
samo da bude extra jasno o tome.

283
00:14:37,920 --> 00:14:39,230
Dakle, ovdje je naš red opet.

284
00:14:39,230 --> 00:14:42,600
12 je najstariji elemenat
u našem redu, glave.

285
00:14:42,600 --> 00:14:46,210
10 je najnoviji elementa
u našem redu, naše rep.

286
00:14:46,210 --> 00:14:49,310
>> I tako, kada želimo
za dequeue element,

287
00:14:49,310 --> 00:14:52,202
želimo ukloniti najstariji element.

288
00:14:52,202 --> 00:14:52,910
Dakle, što nam je činiti?

289
00:14:52,910 --> 00:14:55,243
Pa smo postavili obuhvaćanje pokazivač
koja počinje u glavi,

290
00:14:55,243 --> 00:14:57,840
a mi ga premjestiti tako da
ukazuje na drugi element

291
00:14:57,840 --> 00:15:02,290
to queue-- nešto rekavši Trav
jednako Trav strelicu uz, primjerice,

292
00:15:02,290 --> 00:15:07,170
će preseliti Trav ima ukazati na
15, koji je, nakon što smo dequeue 12,

293
00:15:07,170 --> 00:15:13,030
ili nakon što smo uklonili 12, će se
postati tada najstarija elementa.

294
00:15:13,030 --> 00:15:16,360
>> Sada imamo držite na prvi
Element putem pokazivač glavu

295
00:15:16,360 --> 00:15:19,440
a drugi element
putem pokazivač Trav.

296
00:15:19,440 --> 00:15:25,170
Mi sada mogu slobodno glavu, a onda možemo
kažu ništa ne dolazi prije 15 više.

297
00:15:25,170 --> 00:15:29,990
Tako možemo promijeniti 15 prethodnih
pokazivač ukazati na null,

298
00:15:29,990 --> 00:15:31,874
a mi samo premjestiti nad glavom.

299
00:15:31,874 --> 00:15:32,540
I tamo idemo.

300
00:15:32,540 --> 00:15:35,840
Sada smo uspješno
dequeued 12, a sada smo

301
00:15:35,840 --> 00:15:39,180
još jedan red 4 elemenata.

302
00:15:39,180 --> 00:15:41,700
To je ljepušan velik dio sve
tu je redovima,

303
00:15:41,700 --> 00:15:45,810
i niz bazi i povezani-lista temelji.

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

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

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