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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Deci, dacă ați
vizionat video de pe stivă,

3
00:00:07,370 --> 00:00:09,870
Aceasta este, probabil va simti
ca un pic de deja vu.

4
00:00:09,870 --> 00:00:13,850
Se va un concept foarte asemănătoare,
doar cu o ușoară poftă de mâncare pe el.

5
00:00:13,850 --> 00:00:15,530
Vom vorbi acum despre cozile.

6
00:00:15,530 --> 00:00:19,350
Deci, o coadă, similar cu un stack,
este un alt fel de structură de date

7
00:00:19,350 --> 00:00:22,412
pe care le putem folosi pentru a menține
date într-un mod organizat.

8
00:00:22,412 --> 00:00:24,120
Similar cu o stivă,
acesta poate fi pus în aplicare

9
00:00:24,120 --> 00:00:27,000
ca o matrice sau o listă de legat.

10
00:00:27,000 --> 00:00:30,320
Spre deosebire de o stivă, regulile
pe care le folosim pentru a determina

11
00:00:30,320 --> 00:00:34,210
atunci când lucrurile se adaugă și se îndepărtează de la
o coadă sunt un pic diferit.

12
00:00:34,210 --> 00:00:36,590
>> Spre deosebire de o stivă, care
este o structură LIFO,

13
00:00:36,590 --> 00:00:45,610
ultimul intrat, primul ieșit, o coadă este un FIFO
structura, FIFO, primul intrat, primul ieșit.

14
00:00:45,610 --> 00:00:49,320
Acum cozi, probabil
au o analogie cu cozile.

15
00:00:49,320 --> 00:00:52,820
Dacă ați fost vreodată la coadă la
un parc de distracții sau la o bancă,

16
00:00:52,820 --> 00:00:56,430
există un fel de echitate
de punere în aplicare structura.

17
00:00:56,430 --> 00:00:59,160
Prima persoană la coadă la
banca este prima persoana

18
00:00:59,160 --> 00:01:00,760
Șansă de a vorbi la povestitor.

19
00:01:00,760 --> 00:01:03,522
>> Ar fi un fel de cursă
la partea de jos în cazul în care singura cale

20
00:01:03,522 --> 00:01:06,730
ai să vorbești cu casierul de la
banca a fost de a fi ultima persoană în linie.

21
00:01:06,730 --> 00:01:09,146
Toata lumea ar dori întotdeauna
pentru a fi ultima persoană în linie,

22
00:01:09,146 --> 00:01:12,580
și persoana care a fost acolo primul
care a fost de așteptare pentru un timp,

23
00:01:12,580 --> 00:01:14,715
ar putea fi acolo pentru ore,
și ore și ore

24
00:01:14,715 --> 00:01:17,590
înainte de a avea o șansă de a efectiv
retrage bani de la bancă.

25
00:01:17,590 --> 00:01:22,510
Și astfel cozile sunt un fel de
corectitudine de punere în aplicare structura.

26
00:01:22,510 --> 00:01:25,780
Dar asta nu înseamnă neapărat
că stive sunt un lucru rău, doar

27
00:01:25,780 --> 00:01:28,160
că cozile sunt un alt mod de a face acest lucru.

28
00:01:28,160 --> 00:01:32,420
Deci, din nou, o coadă este primul intrat, primul
out, comparativ cu o stivă care ultimul în,

29
00:01:32,420 --> 00:01:34,440
primul ieșit.

30
00:01:34,440 --> 00:01:36,190
Similar cu o stivă,
avem două operațiuni

31
00:01:36,190 --> 00:01:38,470
pe care le poate efectua pe cozile.

32
00:01:38,470 --> 00:01:43,910
Numele sunt Puneți în coadă, care este de a adăuga
un nou element la sfârșitul listei,

33
00:01:43,910 --> 00:01:47,330
și dequeue, care este
pentru a elimina cele mai vechi

34
00:01:47,330 --> 00:01:49,670
Element din fata a cozii.

35
00:01:49,670 --> 00:01:53,600
Deci vom adăuga elemente
pe capătul cozii,

36
00:01:53,600 --> 00:01:57,220
si vom elimina elemente
din partea din față a cozii.

37
00:01:57,220 --> 00:02:00,790
Din nou, cu stiva, am fost adăugarea de
elemente la vârful stivei

38
00:02:00,790 --> 00:02:03,380
și eliminarea elementelor
din partea de sus a stivei.

39
00:02:03,380 --> 00:02:07,570
Deci, cu Puneți în coadă, este adăugarea la
sfârșitul, eliminarea din față.

40
00:02:07,570 --> 00:02:10,639
Deci cel mai vechi lucru acolo
este întotdeauna următorul lucru

41
00:02:10,639 --> 00:02:13,620
pentru a ieși dacă vom încerca
și dequeue ceva.

42
00:02:13,620 --> 00:02:18,330
>> Deci, din nou, cu cozile, putem
implementari bazate pe matrice

43
00:02:18,330 --> 00:02:20,110
și lista de legat pe bază de implementări.

44
00:02:20,110 --> 00:02:24,620
Vom începe din nou cu
implementari bazate pe matrice.

45
00:02:24,620 --> 00:02:27,070
Definiția structurii
pare destul de asemănătoare.

46
00:02:27,070 --> 00:02:30,720
Avem un alt array
acolo de date valoare de tip,

47
00:02:30,720 --> 00:02:32,690
astfel încât să poată ține tipuri de date arbitrare.

48
00:02:32,690 --> 00:02:35,570
Vom din nou de gând să utilizeze
numere întregi în acest exemplu.

49
00:02:35,570 --> 00:02:39,830
>> Și, la fel ca și cu nostru
punerea în aplicare a stack-based matrice,

50
00:02:39,830 --> 00:02:42,340
pentru că suntem folosind un
matrice, am neapărat

51
00:02:42,340 --> 00:02:46,850
au această limitare că C gen
de impune pe noi, care ne este

52
00:02:46,850 --> 00:02:51,670
nu au nici dinamism în nostru
capacitatea de a dezvolta și reduce matrice.

53
00:02:51,670 --> 00:02:55,710
Trebuie să decidă la începutul
ceea ce este numărul maxim de lucruri

54
00:02:55,710 --> 00:02:59,300
pe care le putem pune în această
coadă, și în acest caz,

55
00:02:59,300 --> 00:03:02,070
Capacitate ar fi unele de lire
definit constant în codul nostru.

56
00:03:02,070 --> 00:03:05,430
Și în sensul prezentului
video, capacitatea va fi de 10.

57
00:03:05,430 --> 00:03:07,690
>> Avem nevoie pentru a urmări
partea din față a cozii

58
00:03:07,690 --> 00:03:11,160
așa că știm care element de
vrem să dequeue,

59
00:03:11,160 --> 00:03:15,070
și avem nevoie, de asemenea, pentru a urmări
ceva else-- numărul de elemente

60
00:03:15,070 --> 00:03:16,690
că avem în coadă nostru.

61
00:03:16,690 --> 00:03:19,360
Observați că nu te urmărirea
de la sfârșitul cozii, doar

62
00:03:19,360 --> 00:03:21,150
dimensiunea cozii.

63
00:03:21,150 --> 00:03:24,310
Și motivul pentru care va sperăm
deveni un pic mai clar într-o clipă.

64
00:03:24,310 --> 00:03:26,143
După am finalizat
această definiție tip,

65
00:03:26,143 --> 00:03:29,080
avem un nou tip de date
numit coada, care putem acum

66
00:03:29,080 --> 00:03:30,630
declara variabile de acest tip de date.

67
00:03:30,630 --> 00:03:35,350
Și oarecum confuz, m-am hotărât
pentru a apela acest coadă q, litera

68
00:03:35,350 --> 00:03:38,090
q în loc de tip de date q.

69
00:03:38,090 --> 00:03:39,600
>> Deci, aici este coada noastră.

70
00:03:39,600 --> 00:03:40,700
Este o structură.

71
00:03:40,700 --> 00:03:45,730
Acesta conține trei membri sau trei
domenii, o serie de dimensiuni capacitate.

72
00:03:45,730 --> 00:03:47,340
În acest caz, capacitatea este de 10.

73
00:03:47,340 --> 00:03:49,580
Și această matrice este
va ține întregi.

74
00:03:49,580 --> 00:03:55,240
În verde este partea din față a coada noastre,
Element de lângă fie eliminate, iar în roșu

75
00:03:55,240 --> 00:03:58,610
va fi de mărimea cozii,
cât de multe elemente sunt în prezent

76
00:03:58,610 --> 00:04:01,190
existente în coada de așteptare.

77
00:04:01,190 --> 00:04:05,300
Deci, dacă spunem egali q.front
0, și dimensiunea q.size egal 0--

78
00:04:05,300 --> 00:04:07,120
suntem punerea 0s în aceste domenii.

79
00:04:07,120 --> 00:04:11,070
Și în acest moment, noi suntem destul de mult
gata pentru a începe lucrul cu coada noastră.

80
00:04:11,070 --> 00:04:14,140
>> Deci prima operație putem
efectua este de a Puneți în coadă ceva,

81
00:04:14,140 --> 00:04:16,860
pentru a adăuga un element nou la
capătul cozii.

82
00:04:16,860 --> 00:04:19,089
Ei bine, ceea ce avem nevoie pentru a
face în cazul general?

83
00:04:19,089 --> 00:04:23,690
Ei bine, această funcție are nevoie Puneți în coadă
să accepte un pointer la coadă nostru.

84
00:04:23,690 --> 00:04:26,370
Din nou, dacă am fi declarat
coadă nostru la nivel global,

85
00:04:26,370 --> 00:04:29,490
nu am nevoie pentru a face acest lucru
neapărat, dar, în general, ne

86
00:04:29,490 --> 00:04:32,330
trebuie să accepte indicii
la structuri de date

87
00:04:32,330 --> 00:04:35,040
în acest fel, pentru că în caz contrar,
suntem trece prin value-- suntem

88
00:04:35,040 --> 00:04:38,140
trecând în copii ale coadă,
și așa nu suntem de fapt în schimbare

89
00:04:38,140 --> 00:04:41,050
coada care ne-am propus să se schimbe.

90
00:04:41,050 --> 00:04:44,860
>> Un alt lucru de care are nevoie să faceți este să accepte
un element de date de tip corespunzătoare.

91
00:04:44,860 --> 00:04:46,818
Din nou, în acest caz, este
O să fie numere întregi,

92
00:04:46,818 --> 00:04:49,330
Dar ai putea arbitrar
declara tipul de date ca valoare

93
00:04:49,330 --> 00:04:51,160
și de a folosi acest lucru mai general.

94
00:04:51,160 --> 00:04:56,030
Asta e elementul vrem să Puneți în coadă,
dorim să adăugăm la sfârșitul cozii de așteptare.

95
00:04:56,030 --> 00:04:58,573
Apoi ne-am dori de fapt să
plasa că datele în coada de așteptare.

96
00:04:58,573 --> 00:05:01,490
În acest caz, se fi introduse în
Locul de amplasare corectă a matrice noastre,

97
00:05:01,490 --> 00:05:05,040
și apoi ne-o dorim pentru a schimba dimensiunea
de coada, cât de multe elemente noi,

98
00:05:05,040 --> 00:05:07,050
în prezent au.

99
00:05:07,050 --> 00:05:07,990
>> Deci, să începem.

100
00:05:07,990 --> 00:05:10,890
Iată, din nou, că generalul
Declarația funcție formă

101
00:05:10,890 --> 00:05:13,980
pentru ceea ce ar putea arata ca Puneți în coadă.

102
00:05:13,980 --> 00:05:14,910
Și aici vom merge.

103
00:05:14,910 --> 00:05:18,335
Să Puneți în coadă numărul
28 în coada de așteptare.

104
00:05:18,335 --> 00:05:19,460
Deci, ce ne facem?

105
00:05:19,460 --> 00:05:23,390
Ei bine, partea din față a coada nostru este
la 0, iar mărimea cozii noastre

106
00:05:23,390 --> 00:05:29,680
este la 0, și așa, probabil, ne-o dorim pentru a pune
numărul 28 în matrice număr element de

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

108
00:05:31,124 --> 00:05:32,540
Așa că am pus acum că acolo.

109
00:05:32,540 --> 00:05:34,820
Deci, acum ce avem nevoie pentru a schimba?

110
00:05:34,820 --> 00:05:37,090
Noi nu vrem să se schimbe
partea din față a cozii,

111
00:05:37,090 --> 00:05:40,850
pentru că vrem să știm ce elemente
s-ar putea nevoie pentru a dequeue mai târziu.

112
00:05:40,850 --> 00:05:44,020
Deci, motivul pentru care avem față acolo
este un fel de un indicator a ceea ce este

113
00:05:44,020 --> 00:05:46,439
cel mai vechi lucru din matrice.

114
00:05:46,439 --> 00:05:49,730
Ei bine, cel mai vechi lucru din array-- în
De fapt, singurul lucru în matrice dreapta

115
00:05:49,730 --> 00:05:53,540
now-- este 28, care este
la matrice locație 0.

116
00:05:53,540 --> 00:05:56,160
Deci nu vrem să
schimba acest număr verde,

117
00:05:56,160 --> 00:05:57,910
pentru că asta e cea mai veche elementul.

118
00:05:57,910 --> 00:06:00,510
Mai degrabă, vrem sa schimbam dimensiunea.

119
00:06:00,510 --> 00:06:04,110
Deci, în acest caz, vom
incrementa dimensiune la 1.

120
00:06:04,110 --> 00:06:08,430
>> Acum un fel generală a ideii de unde
element de lângă este de gând să meargă într-o coadă

121
00:06:08,430 --> 00:06:12,310
este de a adăuga aceste două numere
împreună, față și dimensiunea,

122
00:06:12,310 --> 00:06:16,390
și că voi spune unde următoarea
element din coada este de gând să meargă.

123
00:06:16,390 --> 00:06:18,130
Deci, acum hai sa Puneți în coadă un alt număr.

124
00:06:18,130 --> 00:06:20,250
Să Puneți în coadă 33.

125
00:06:20,250 --> 00:06:24,480
Deci, 33 este de gând să meargă în
matrice Localizare 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Deci, în acest caz, va
pentru a merge în matrice locație 1,

127
00:06:26,840 --> 00:06:29,500
și acum dimensiunea coada nostru este de 2.

128
00:06:29,500 --> 00:06:31,840
>> Din nou, nu suntem schimbarea
partea din față a coada noastre,

129
00:06:31,840 --> 00:06:34,730
pentru că 28 este încă
cel mai vechi element și noi

130
00:06:34,730 --> 00:06:38,220
vreau sa-- când ajungem în cele din urmă
la dequeuing, eliminarea elementelor

131
00:06:38,220 --> 00:06:43,300
din acest coada, vrem să știm
în cazul în care cel mai vechi element este.

132
00:06:43,300 --> 00:06:48,620
Și așa am mereu nevoie pentru a menține
un indicator de unde este.

133
00:06:48,620 --> 00:06:50,410
Deci, asta e ceea ce este acolo pentru 0.

134
00:06:50,410 --> 00:06:52,910
Asta e ceea ce fata este acolo pentru.

135
00:06:52,910 --> 00:06:55,022
>> Să în Puneți în coadă o mai multe elemente, 19.

136
00:06:55,022 --> 00:06:56,980
Sunt sigur că puteți ghici
în cazul în care 19 este de gând să meargă.

137
00:06:56,980 --> 00:06:59,860
O să meargă în
matrice locație numărul 2.

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

139
00:07:01,570 --> 00:07:03,199
Și acum dimensiunea coada nostru este de 3.

140
00:07:03,199 --> 00:07:04,240
Avem 3 elemente în ea.

141
00:07:04,240 --> 00:07:08,490
Deci, dacă ar fi să, și nu vom
chiar acum, Puneți în coadă un alt element,

142
00:07:08,490 --> 00:07:11,370
ar intra în locație matrice
numărul 3, iar mărimea cozii noastre

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

144
00:07:13,160 --> 00:07:15,279
Deci ne-am enqueued mai multe elemente acum.

145
00:07:15,279 --> 00:07:16,570
Acum să începem pentru a le elimina.

146
00:07:16,570 --> 00:07:19,450
Să le dequeue din coadă.

147
00:07:19,450 --> 00:07:23,340
>> Atât de asemănătoare cu pop, care este un fel
a analogului de acest lucru pentru stive,

148
00:07:23,340 --> 00:07:26,180
dequeue trebuie să accepte o
pointer la queue-- din nou,

149
00:07:26,180 --> 00:07:28,140
excepția cazului în care este declarat la nivel global.

150
00:07:28,140 --> 00:07:31,610
Acum vrem pentru a schimba locația
a cozii de așteptare.

151
00:07:31,610 --> 00:07:35,050
Acest lucru este în cazul în care un fel de vorba
în joc, că variabila față,

152
00:07:35,050 --> 00:07:37,310
pentru că odată ce vom elimina
un element, dorim

153
00:07:37,310 --> 00:07:40,720
să-l mute la următorul cel mai vechi element.

154
00:07:40,720 --> 00:07:44,180
>> Apoi ne-am dori să scadă
mărimea cozii,

155
00:07:44,180 --> 00:07:47,130
și apoi ne-am dori să se întoarcă la valoarea
care a fost scos din coada.

156
00:07:47,130 --> 00:07:48,921
Din nou, nu vrem să se debaraseze doar.

157
00:07:48,921 --> 00:07:51,170
Suntem probabil sunt extragerea
l din queue-- suntem

158
00:07:51,170 --> 00:07:54,170
dequeuing pentru că ne pasă de ea.

159
00:07:54,170 --> 00:08:01,080
Deci, vrem să se întoarcă această funcție
un element de date din valoarea de tip.

160
00:08:01,080 --> 00:08:04,360
Din nou, în acest caz, valoarea este întreg.

161
00:08:04,360 --> 00:08:05,670
>> Deci, acum hai să dequeue ceva.

162
00:08:05,670 --> 00:08:09,310
Să elimina un element din coadă.

163
00:08:09,310 --> 00:08:15,970
Dacă spunem int x este egal cu & q, ampersand q--
din nou că este un pointer la aceste date q

164
00:08:15,970 --> 00:08:20,177
structure-- ce element de
va fi dequeued?

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

166
00:08:23,840 --> 00:08:29,480
În acest caz, pentru că este o prima
în, primul ieșit structura de date, FIFO,

167
00:08:29,480 --> 00:08:33,690
primul lucru pe care am pus în această
coadă a fost 28, și așa mai departe în acest caz,

168
00:08:33,690 --> 00:08:37,245
vom lua 28 din
coada, nu 19, care este ceea ce

169
00:08:37,245 --> 00:08:38,870
ne-ar fi făcut dacă acest lucru a fost o stivă.

170
00:08:38,870 --> 00:08:42,220
Vom lua 28 din coada.

171
00:08:42,220 --> 00:08:44,960
>> Similar cu ceea ce am făcut cu
o stivă, nu suntem de fapt

172
00:08:44,960 --> 00:08:47,345
O să ștergeți 28
din coada în sine,

173
00:08:47,345 --> 00:08:49,470
vom merge la fel doar
de pretinde că nu este acolo.

174
00:08:49,470 --> 00:08:51,678
Deci o să rămână acolo
în memorie, dar suntem doar

175
00:08:51,678 --> 00:08:57,820
O să-l ignore fel de prin mutarea
celelalte două domenii de datele noastre q

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

177
00:08:58,830 --> 00:09:00,230
Vom schimba în față.

178
00:09:00,230 --> 00:09:04,290
Q.front este acum de gând să
fie 1, pentru că acum este

179
00:09:04,290 --> 00:09:07,740
cea mai veche elementul avem în nostru
coada, pentru că ne-am îndepărtat deja 28,

180
00:09:07,740 --> 00:09:10,460
care a fost fostul mai vechi element.

181
00:09:10,460 --> 00:09:13,540
>> Și acum, vrem să schimbăm
mărimea cozii

182
00:09:13,540 --> 00:09:15,780
a două elemente în loc de trei.

183
00:09:15,780 --> 00:09:20,450
Acum amintiți-vă mai devreme i-am spus atunci când am
doriți să adăugați elemente la coadă,

184
00:09:20,450 --> 00:09:26,000
l-am pus într-o locație matrice
care este suma față și dimensiuni.

185
00:09:26,000 --> 00:09:29,050
Deci, în acest caz, suntem încă punerea
aceasta, următorul element în coada de așteptare,

186
00:09:29,050 --> 00:09:33,360
în matrice locație 3, și
vom vedea că într-o secundă.

187
00:09:33,360 --> 00:09:35,730
>> Deci ne-am dequeued acum nostru
prim element din coada.

188
00:09:35,730 --> 00:09:36,480
Să o facem din nou.

189
00:09:36,480 --> 00:09:38,696
Să sterge alt
elementul din coada.

190
00:09:38,696 --> 00:09:42,400
În acest caz, curentul mai vechi
element este matrice locație 1.

191
00:09:42,400 --> 00:09:44,220
Asta e ceea ce ne spune q.front.

192
00:09:44,220 --> 00:09:46,980
Cutia verde ne spune că
asta e cea mai veche elementul.

193
00:09:46,980 --> 00:09:49,310
Și astfel, X va deveni 33.

194
00:09:49,310 --> 00:09:52,130
Vom doar un fel de uitat
care 33 există în matrice,

195
00:09:52,130 --> 00:09:55,100
și vom spune că acest moment,
nou cel mai vechi element din coada de așteptare

196
00:09:55,100 --> 00:09:58,900
este la matrice locație 2, și dimensiunea
al cozii, numărul de elemente

197
00:09:58,900 --> 00:10:02,152
avem în coada de așteptare, este de 1.

198
00:10:02,152 --> 00:10:05,110
Acum, haideți să Puneți în coadă ceva, și eu
un fel de a dat acest departe acum un al doilea,

199
00:10:05,110 --> 00:10:10,340
dar dacă vrem să 40 în
coadă, în cazul în care se 40 va merge?

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

201
00:10:12,880 --> 00:10:17,730
Ei bine, am fost inscrie
în plus q.front coadă dimensiune,

202
00:10:17,730 --> 00:10:20,850
și deci are sens să
de fapt, pentru a pune 40 aici.

203
00:10:20,850 --> 00:10:22,840
Acum, observați că, la
un moment dat, vom

204
00:10:22,840 --> 00:10:27,980
pentru a ajunge la sfârșitul anului
gama noastră interiorul Q,

205
00:10:27,980 --> 00:10:32,010
dar că stins 28 și 33--
ele sunt de fapt, punct de vedere tehnic

206
00:10:32,010 --> 00:10:33,300
spații deschise, nu?

207
00:10:33,300 --> 00:10:36,040
Și astfel, am putea eventually--
această normă de a adăuga

208
00:10:36,040 --> 00:10:40,390
cei doi am putea în cele din urmă together--
Trebuie să mod de mărimea capacității

209
00:10:40,390 --> 00:10:41,410
astfel încât să putem încadra în jurul valorii.

210
00:10:41,410 --> 00:10:43,620
>> Deci, dacă ajungem la elementul
numărul 10, dacă suntem

211
00:10:43,620 --> 00:10:48,790
înlocuindu-l în număr element de 10, ne-ar
de fapt, a pus în matrice locație 0.

212
00:10:48,790 --> 00:10:50,997
Și dacă am fost de gând să
matrice location-- mă scuzați,

213
00:10:50,997 --> 00:10:53,080
dacă le-am adaugat împreună,
și am ajuns la numărul

214
00:10:53,080 --> 00:10:56,330
11 ar fi în cazul în care ne-ar trebui să pună
ea, care nu există în acest array--

215
00:10:56,330 --> 00:10:58,200
ar fi merge în afara limitelor.

216
00:10:58,200 --> 00:11:03,367
Am putea Mod de 10 și a pus
l în matrice locație 1.

217
00:11:03,367 --> 00:11:04,450
Deci, asta e modul în care funcționează cozile.

218
00:11:04,450 --> 00:11:08,540
Ei întotdeauna merge de la stânga
la dreapta și, eventual, se infasoara in jurul.

219
00:11:08,540 --> 00:11:11,280
Și știi că sunt
dacă full size, că casetă roșie,

220
00:11:11,280 --> 00:11:13,710
devine egal cu capacitatea.

221
00:11:13,710 --> 00:11:16,720
Și așa după ce am adăugat 40 la
coadă, și ce trebuie să facem?

222
00:11:16,720 --> 00:11:19,890
Ei bine, cea mai veche elementul
în coada de așteptare este încă 19,

223
00:11:19,890 --> 00:11:21,990
așa că nu doriți să modificați
partea din față a cozii,

224
00:11:21,990 --> 00:11:23,820
dar acum avem două
elemente în coada de așteptare,

225
00:11:23,820 --> 00:11:28,710
și așa ne-o dorim pentru a mări
Dimensiunea nostru de la 1 pentru a doi.

226
00:11:28,710 --> 00:11:31,820
>> Asta e destul de mult cu
de lucru cu cozi pe bază de matrice,

227
00:11:31,820 --> 00:11:33,630
și similar cu stiva,
există, de asemenea un mod

228
00:11:33,630 --> 00:11:36,450
să pună în aplicare o coadă ca o listă legată.

229
00:11:36,450 --> 00:11:40,150
Acum, în cazul în care acest tip de structură de date
pare familiar pentru tine, este.

230
00:11:40,150 --> 00:11:43,780
Nu este o listă individual legate,
E o listă de două ori legată.

231
00:11:43,780 --> 00:11:46,790
Și acum, ca o parte, este
de fapt posibil să se implementeze

232
00:11:46,790 --> 00:11:50,160
o coadă ca o listă individual legate, dar
Cred că în termeni de vizualizare,

233
00:11:50,160 --> 00:11:53,350
este de fapt s-ar putea ajuta pentru a vizualiza
acest lucru ca pe o listă de două ori legată.

234
00:11:53,350 --> 00:11:56,850
Dar este cu siguranta posibil să
face acest lucru ca o listă individual legat.

235
00:11:56,850 --> 00:12:00,110
>> Deci, haideți să aruncăm o privire la
ce acest lucru ar putea arăta.

236
00:12:00,110 --> 00:12:02,750
Dacă vrem să enquue--
Deci, acum, din nou suntem

237
00:12:02,750 --> 00:12:05,360
trecerea la o listă legată
model bazat aici.

238
00:12:05,360 --> 00:12:08,420
Dacă vrem să Puneți în coadă, vrem
pentru a adăuga un element nou, bine

239
00:12:08,420 --> 00:12:09,730
ce trebuie să facem?

240
00:12:09,730 --> 00:12:12,770
Ei bine, în primul rând, pentru că
suntem adăugarea la sfârșitul

241
00:12:12,770 --> 00:12:15,520
și scoaterea din
începând, probabil

242
00:12:15,520 --> 00:12:20,050
doresc să mențină indicii atât
cap și coada listei legat?

243
00:12:20,050 --> 00:12:22,660
Coada fiind un alt termen pentru
sfârșitul listei de legătura,

244
00:12:22,660 --> 00:12:24,496
ultimul element din lista de legat.

245
00:12:24,496 --> 00:12:26,620
Iar acestea vor probabil,
din nou, să fie benefic pentru noi

246
00:12:26,620 --> 00:12:28,477
dacă acestea sunt variabile globale.

247
00:12:28,477 --> 00:12:31,060
Dar acum, dacă vrem să adăugați un nou
Element ce avem de făcut?

248
00:12:31,060 --> 00:12:35,262
Ce ne-am [? Malak?] sau dinamic
aloca noul nostru nod pentru noi înșine.

249
00:12:35,262 --> 00:12:38,220
Și apoi, la fel ca atunci când am adăuga orice
element de la o listă de două ori ne-am legat,

250
00:12:38,220 --> 00:12:40,410
Trebuie doar pentru a sorta de--
aceste ultime trei etape aici

251
00:12:40,410 --> 00:12:43,330
sunt doar toate despre miscarea
indicii în mod corect

252
00:12:43,330 --> 00:12:46,710
astfel încât elementul se adaugă la
lanțul fără a rupe lanțul

253
00:12:46,710 --> 00:12:49,580
sau de a face un fel de greșeală
sau având un fel de accident

254
00:12:49,580 --> 00:12:54,505
se întâmplă prin care accidental
orfane unele elemente de coada noastre.

255
00:12:54,505 --> 00:12:55,880
Iată ce acest lucru ar putea arăta.

256
00:12:55,880 --> 00:13:00,980
Vrem să adăugați elementul
10 la sfârșitul acestui coadă.

257
00:13:00,980 --> 00:13:03,380
Deci cea mai veche elementul aici
este reprezentat de cap.

258
00:13:03,380 --> 00:13:06,800
Asta e primul lucru pe care am pus
în această coadă ipotetic aici.

259
00:13:06,800 --> 00:13:10,430
Și coada, 13, este cel mai
adăugat recent de element.

260
00:13:10,430 --> 00:13:17,030
Și astfel, dacă vrem să Puneți în coadă 10 în
acest coada, vrem să-l puneți după 13.

261
00:13:17,030 --> 00:13:19,860
Și așa vom dinamic
aloca spațiu pentru un nou nod

262
00:13:19,860 --> 00:13:23,280
și verificați pentru a vă asigura nul
nu avem o eroare de memorie.

263
00:13:23,280 --> 00:13:27,040
Apoi vom
plasa 10 în acel nod,

264
00:13:27,040 --> 00:13:30,030
și acum trebuie să fim atenți
despre modul în care vom organiza indicii

265
00:13:30,030 --> 00:13:32,180
așa că nu rupe lantul.

266
00:13:32,180 --> 00:13:38,910
>> Putem stabili de 10 de câmp precedent
la punctul înapoi la coada vechi,

267
00:13:38,910 --> 00:13:41,620
iar din '10 va fi
nou coada la un moment dat

268
00:13:41,620 --> 00:13:44,459
până la momentul toate aceste
lanțuri sunt conectate,

269
00:13:44,459 --> 00:13:46,250
nimic nu va veni
După 10 acum.

270
00:13:46,250 --> 00:13:49,880
Și astfel 10 de pe lângă indicatorul
va indica nul,

271
00:13:49,880 --> 00:13:53,580
și apoi după ce am face acest lucru, după ce ne-am
conectat 10 înapoi la lanțul,

272
00:13:53,580 --> 00:13:57,780
putem lua capul vechi, sau, scuza
ma, coada vechi de coadă.

273
00:13:57,780 --> 00:14:02,980
Vechea sfârșitul cozii de așteptare,
13, și să-l arate la 10.

274
00:14:02,980 --> 00:14:08,220
Și acum, în acest moment, avem
enqueued numărul 10 în acest coada.

275
00:14:08,220 --> 00:14:14,740
Tot ce trebuie să facem acum este doar deplasați
coada pentru a indica 10 în loc de a 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing este de fapt
foarte asemănător cu popping

277
00:14:17,630 --> 00:14:21,710
dintr-o stivă, care este
implementat ca o listă legată

278
00:14:21,710 --> 00:14:24,040
dacă ați văzut videoclipul stive.

279
00:14:24,040 --> 00:14:27,280
Tot ce trebuie să faceți este să înceapă de la
începând, găsiți al doilea element,

280
00:14:27,280 --> 00:14:30,480
elibera primul element,
și apoi mutați capul

281
00:14:30,480 --> 00:14:32,930
pentru a indica al doilea element.

282
00:14:32,930 --> 00:14:37,920
Probabil, mai bine să-l vizualiza
doar pentru a fi în plus clar cu privire la aceasta.

283
00:14:37,920 --> 00:14:39,230
Deci, aici e din nou coada noastră.

284
00:14:39,230 --> 00:14:42,600
12 este cea mai veche elementul
în coadă nostru, cap.

285
00:14:42,600 --> 00:14:46,210
10 este cel mai nou elementul
în coadă noastră, coada noastră.

286
00:14:46,210 --> 00:14:49,310
>> Și astfel, atunci când ne-o dorim
să dequeue un element,

287
00:14:49,310 --> 00:14:52,202
dorim pentru a elimina cea mai veche elementul.

288
00:14:52,202 --> 00:14:52,910
Deci, ce facem?

289
00:14:52,910 --> 00:14:55,243
Ei bine, ne-am stabilit un pointer de traversare
care începe de la cap,

290
00:14:55,243 --> 00:14:57,840
si l-am muta, astfel încât să
indică al doilea element

291
00:14:57,840 --> 00:15:02,290
din acest queue-- ceva spunând trav
este egal cu trav săgeata de lângă, de exemplu,

292
00:15:02,290 --> 00:15:07,170
s-ar muta acolo trav pentru a indica
15, care, după ce dequeue 12,

293
00:15:07,170 --> 00:15:13,030
sau după ce vom elimina 12, va
devenit apoi cel mai vechi-element.

294
00:15:13,030 --> 00:15:16,360
>> Acum avem o așteptare pe primul
elementul prin cap pointer

295
00:15:16,360 --> 00:15:19,440
și al doilea element
prin trav pointer.

296
00:15:19,440 --> 00:15:25,170
Putem cap acum liber, iar apoi putem
nu spun nimic mai vine înainte de 15.

297
00:15:25,170 --> 00:15:29,990
Deci, putem schimba 15 Înapoi
pointer la punctul la nul,

298
00:15:29,990 --> 00:15:31,874
și ne-am muta doar capul peste.

299
00:15:31,874 --> 00:15:32,540
Și acolo mergem.

300
00:15:32,540 --> 00:15:35,840
Acum avem succes
dequeued 12, iar acum ne-am

301
00:15:35,840 --> 00:15:39,180
o altă coadă de 4 elemente.

302
00:15:39,180 --> 00:15:41,700
Asta e destul de mult tot
este de cozi,

303
00:15:41,700 --> 00:15:45,810
atât pe matrice și lista de legat pe bază de.

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

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

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