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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Així que si vostè té
vist el vídeo a la pila,

3
00:00:07,370 --> 00:00:09,870
això és, probablement, va sentir
com una mica de deixa vu.

4
00:00:09,870 --> 00:00:13,850
Es va a un concepte molt similar,
només amb un petit gir en ell.

5
00:00:13,850 --> 00:00:15,530
Anem a parlar ara sobre les cues.

6
00:00:15,530 --> 00:00:19,350
Així que una cua, similar a una pila,
és un altre tipus d'estructura de dades

7
00:00:19,350 --> 00:00:22,412
que podem utilitzar per mantenir
dades en una manera organitzada.

8
00:00:22,412 --> 00:00:24,120
Igual que en una pila,
pot ser implementat

9
00:00:24,120 --> 00:00:27,000
com una matriu o una llista enllaçada.

10
00:00:27,000 --> 00:00:30,320
A diferència d'una pila, les regles
que utilitzem per determinar

11
00:00:30,320 --> 00:00:34,210
quan s'afegeixen i s'eliminen de les coses
una cua són una mica diferents.

12
00:00:34,210 --> 00:00:36,590
>> A diferència d'una pila, que
és una estructura LIFO,

13
00:00:36,590 --> 00:00:45,610
últim en entrar, primer en sortir, una cua és un FIFO
estructura, FIFO, primer a entrar, primer en sortir.

14
00:00:45,610 --> 00:00:49,320
Ara cues, és probable que
tenen una analogia amb les cues.

15
00:00:49,320 --> 00:00:52,820
Si alguna vegada has estat a la cua
un parc d'atraccions o en un banc,

16
00:00:52,820 --> 00:00:56,430
hi ha una mena de justícia
la implementació de l'estructura.

17
00:00:56,430 --> 00:00:59,160
La primera persona a la fila
el banc és la primera persona

18
00:00:59,160 --> 00:01:00,760
qui va a parlar amb el caixer.

19
00:01:00,760 --> 00:01:03,522
>> Seria una mena de carrera
a la part inferior si l'única manera

20
00:01:03,522 --> 00:01:06,730
has de parlar amb el caixer en el
banc anava a ser l'última persona a la fila.

21
00:01:06,730 --> 00:01:09,146
Tothom estaria sempre volen
ser l'última persona de la fila,

22
00:01:09,146 --> 00:01:12,580
i la persona que hi era primer
qui ha estat esperant per un temps,

23
00:01:12,580 --> 00:01:14,715
podria ser-hi durant hores,
i hores i hores

24
00:01:14,715 --> 00:01:17,590
abans que tinguin l'oportunitat de realitat
retirar diners al banc.

25
00:01:17,590 --> 00:01:22,510
I així, les cues són una mena de
equitat implementació d'estructura.

26
00:01:22,510 --> 00:01:25,780
Però això no vol dir necessàriament
que les piles són una cosa dolenta, simplement

27
00:01:25,780 --> 00:01:28,160
que les cues són una altra manera de fer-ho.

28
00:01:28,160 --> 00:01:32,420
Així que de nou una cua és primer a entrar, primer
fora, davant d'una pila que dura a,

29
00:01:32,420 --> 00:01:34,440
primer a sortir.

30
00:01:34,440 --> 00:01:36,190
Igual que en una pila,
tenim dues operacions

31
00:01:36,190 --> 00:01:38,470
que podem dur a terme a les cues.

32
00:01:38,470 --> 00:01:43,910
Els noms són enqueue, que consisteix a afegir
un nou element fins al final de la cua,

33
00:01:43,910 --> 00:01:47,330
i treure de la cua, que és
per eliminar els més antics

34
00:01:47,330 --> 00:01:49,670
element des de la part frontal de la cua.

35
00:01:49,670 --> 00:01:53,600
Així que anem a afegir elements
a l'extrem de la cua,

36
00:01:53,600 --> 00:01:57,220
i anem a eliminar elements
des de la part frontal de la cua.

37
00:01:57,220 --> 00:02:00,790
Una vegada més, amb la pila, vam anar agregant
elements a la part superior de la pila

38
00:02:00,790 --> 00:02:03,380
i eliminació d'elements
des de la part superior de la pila.

39
00:02:03,380 --> 00:02:07,570
Així que amb enqueue, està afegint a
Al final, l'eliminació de la part davantera.

40
00:02:07,570 --> 00:02:10,639
Així que el més antic d'allà
sempre és el proper

41
00:02:10,639 --> 00:02:13,620
a sortir si tractem
i treure de la cua alguna cosa.

42
00:02:13,620 --> 00:02:18,330
>> Així que de nou, amb les cues, podem
implementacions basades en matrius

43
00:02:18,330 --> 00:02:20,110
i llista enllaçada implementacions basades.

44
00:02:20,110 --> 00:02:24,620
Anem a començar de nou amb
implementacions basades en matrius.

45
00:02:24,620 --> 00:02:27,070
La definició de l'estructura
es veu molt similar.

46
00:02:27,070 --> 00:02:30,720
Tenim una altra matriu
no del valor de tipus de dades,

47
00:02:30,720 --> 00:02:32,690
pel que pot contenir tipus de dades arbitraris.

48
00:02:32,690 --> 00:02:35,570
Estem novament utilitzarà
nombres enters en aquest exemple.

49
00:02:35,570 --> 00:02:39,830
>> I igual que amb el nostre
aplicació pila basada en matrius,

50
00:02:39,830 --> 00:02:42,340
perquè estem usant un
array, que necessàriament

51
00:02:42,340 --> 00:02:46,850
tenir aquesta limitació que C tipus
de fa complir en nosaltres, que som nosaltres

52
00:02:46,850 --> 00:02:51,670
no tenen cap dinamisme en la nostra
capacitat per créixer i reduir la mida de la matriu.

53
00:02:51,670 --> 00:02:55,710
Hem de decidir al començament
Quin és el nombre màxim de coses

54
00:02:55,710 --> 00:02:59,300
que podem posar en aquest
cua, i en aquest cas,

55
00:02:59,300 --> 00:03:02,070
capacitat seria algun lliures
definida constant en el nostre codi.

56
00:03:02,070 --> 00:03:05,430
I per als fins d'aquesta
de vídeo, la capacitat serà 10.

57
00:03:05,430 --> 00:03:07,690
>> Necessitem fer un seguiment de
la part davantera de la cua de

58
00:03:07,690 --> 00:03:11,160
així que sabem quin element
volem treure de la cua,

59
00:03:11,160 --> 00:03:15,070
i també necessitem fer un seguiment de
alguna cosa else-- el nombre d'elements

60
00:03:15,070 --> 00:03:16,690
que tenim a la nostra cua.

61
00:03:16,690 --> 00:03:19,360
Cal notar que no estem fer el seguiment
del final de la cua, just

62
00:03:19,360 --> 00:03:21,150
la mida de la cua.

63
00:03:21,150 --> 00:03:24,310
I la raó que s'espera
convertit en una mica més clara en un moment.

64
00:03:24,310 --> 00:03:26,143
Un cop hem completat
aquesta definició de tipus,

65
00:03:26,143 --> 00:03:29,080
tenim un nou tipus de dades
anomenada cua, que ara podem

66
00:03:29,080 --> 00:03:30,630
declarar variables d'aquest tipus de dades.

67
00:03:30,630 --> 00:03:35,350
I una mica confusament, he decidit
anomenar aquesta cua q, la carta

68
00:03:35,350 --> 00:03:38,090
q en lloc del tipus de dades q.

69
00:03:38,090 --> 00:03:39,600
>> Així que aquí està la nostra cua.

70
00:03:39,600 --> 00:03:40,700
Es tracta d'una estructura.

71
00:03:40,700 --> 00:03:45,730
Conté tres membres o de tres
camps, una matriu de mida CAPACITAT.

72
00:03:45,730 --> 00:03:47,340
En aquest cas, la capacitat és de 10.

73
00:03:47,340 --> 00:03:49,580
I aquesta matriu és
va a celebrar sencers.

74
00:03:49,580 --> 00:03:55,240
En el verd és el front de la nostra cua, el
següent element a ser eliminat, i en vermell

75
00:03:55,240 --> 00:03:58,610
serà la mida de la cua,
quants elements Actualment

76
00:03:58,610 --> 00:04:01,190
existent a la cua.

77
00:04:01,190 --> 00:04:05,300
Així que si diem iguals q.front
0, i la mida és igual q.size 0--

78
00:04:05,300 --> 00:04:07,120
estem posant 0s en aquests camps.

79
00:04:07,120 --> 00:04:11,070
I en aquest punt, estem més o menys
a punt per començar a treballar amb la nostra cua.

80
00:04:11,070 --> 00:04:14,140
>> Així que la primera operació que puguem
realitzar és posar en cua alguna cosa,

81
00:04:14,140 --> 00:04:16,860
afegir un nou element a
al final de la cua.

82
00:04:16,860 --> 00:04:19,089
Bé, què és el que necessitem
fer en el cas general?

83
00:04:19,089 --> 00:04:23,690
Bé aquesta funció encolar necessitats
per acceptar un punter a la nostra cua.

84
00:04:23,690 --> 00:04:26,370
Un cop més, si haguéssim declarat
la nostra cua a nivell mundial,

85
00:04:26,370 --> 00:04:29,490
no necessitaríem fer això
necessàriament, però en general,

86
00:04:29,490 --> 00:04:32,330
d'acceptar punters
a les estructures de dades

87
00:04:32,330 --> 00:04:35,040
d'aquesta manera, perquè en cas contrari,
estem passant per value-- estem

88
00:04:35,040 --> 00:04:38,140
passant còpies de la cua,
i així no canviarem realment

89
00:04:38,140 --> 00:04:41,050
la cua que tenim la intenció de canviar.

90
00:04:41,050 --> 00:04:44,860
>> L'altra cosa que ha de fer és acceptar
un element de dades del tipus apropiat.

91
00:04:44,860 --> 00:04:46,818
Un cop més, en aquest cas, és
serà sencers,

92
00:04:46,818 --> 00:04:49,330
però vostè podria arbitràriament
declarar el tipus de dades com a valor

93
00:04:49,330 --> 00:04:51,160
i utilitzar això de manera més general.

94
00:04:51,160 --> 00:04:56,030
Aquest és l'element que volem posar en cua,
volem afegir al final de la cua.

95
00:04:56,030 --> 00:04:58,573
Llavors realment volem
col·locar les dades a la cua.

96
00:04:58,573 --> 00:05:01,490
En aquest cas, la col·locació en el
correcta ubicació de la nostra matriu,

97
00:05:01,490 --> 00:05:05,040
i després volem canviar la mida
de la cua, quants elements de nosaltres

98
00:05:05,040 --> 00:05:07,050
Actualment tenir.

99
00:05:07,050 --> 00:05:07,990
>> Així que anem a començar.

100
00:05:07,990 --> 00:05:10,890
Aquest és, de nou, que en general
declaració de la funció forma

101
00:05:10,890 --> 00:05:13,980
per a la qual enqueue podria ser similar.

102
00:05:13,980 --> 00:05:14,910
I aquí anem.

103
00:05:14,910 --> 00:05:18,335
Anem a posar en cua el nombre
28 a la cua.

104
00:05:18,335 --> 00:05:19,460
Llavors, què farem?

105
00:05:19,460 --> 00:05:23,390
Bé, la part davantera de la nostra cua és
a 0, i la mida de la nostra cua

106
00:05:23,390 --> 00:05:29,680
està a 0, de manera que probablement volem posar
el número 28 en la sèrie nombre d'element

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

108
00:05:31,124 --> 00:05:32,540
Així que ara hem ja que en aquest país.

109
00:05:32,540 --> 00:05:34,820
Així que ara, què hem de canviar?

110
00:05:34,820 --> 00:05:37,090
No volem canviar
la part davantera de la cua,

111
00:05:37,090 --> 00:05:40,850
perquè volem saber quin element
que podríem necessitar per treure de la cua més tard.

112
00:05:40,850 --> 00:05:44,020
Així que la raó per la qual tenim davant no
és una espècie d'un indicador del que és

113
00:05:44,020 --> 00:05:46,439
el més antic de la matriu.

114
00:05:46,439 --> 00:05:49,730
Bé, la cosa més vella del array-- en
De fet, l'única cosa en la matriu de la dreta

115
00:05:49,730 --> 00:05:53,540
ara-- és 28, que és
en la ubicació array 0.

116
00:05:53,540 --> 00:05:56,160
Així que no volem
canviar aquest número verd,

117
00:05:56,160 --> 00:05:57,910
perquè aquest és l'element més antic.

118
00:05:57,910 --> 00:06:00,510
Més aviat, volem canviar la mida.

119
00:06:00,510 --> 00:06:04,110
Així que en aquest cas, anem a
increment de mida a 1.

120
00:06:04,110 --> 00:06:08,430
>> Ara una espècie general d'idea d'on el
següent element es va a anar en una cua

121
00:06:08,430 --> 00:06:12,310
és afegir aquests dos nombres
junts, front i grandària,

122
00:06:12,310 --> 00:06:16,390
i que et diré on ve
element a la cua se n'anirà.

123
00:06:16,390 --> 00:06:18,130
Així que ara anem a posar en cua un altre número.

124
00:06:18,130 --> 00:06:20,250
Anem a posar en cua 33.

125
00:06:20,250 --> 00:06:24,480
Així que 33 va entrar en
ubicació matriu 0 + 1.

126
00:06:24,480 --> 00:06:26,840
Així que en aquest cas, es va
per anar a la ubicació matriu 1,

127
00:06:26,840 --> 00:06:29,500
i ara la mida de la nostra cua és 2.

128
00:06:29,500 --> 00:06:31,840
>> Un cop més, no estem canviant
el front de la nostra cua,

129
00:06:31,840 --> 00:06:34,730
28 perquè segueix sent el
element més antic, i

130
00:06:34,730 --> 00:06:38,220
vull A-- quan finalment arribem
a desencua, eliminació d'elements

131
00:06:38,220 --> 00:06:43,300
d'aquesta cua, volem saber
on l'element més antic és.

132
00:06:43,300 --> 00:06:48,620
I pel que sempre cal mantenir
algun indicador d'on està.

133
00:06:48,620 --> 00:06:50,410
Així que això és el que el 0 és allà.

134
00:06:50,410 --> 00:06:52,910
Això és el que hi és per davant.

135
00:06:52,910 --> 00:06:55,022
>> Anem a enqueue un element més, 19.

136
00:06:55,022 --> 00:06:56,980
Estic segur que es pot endevinar
on 19 es va a anar.

137
00:06:56,980 --> 00:06:59,860
Va a entrar en
ubicació matriu número 2.

138
00:06:59,860 --> 00:07:01,570
Això és 0, més 2.

139
00:07:01,570 --> 00:07:03,199
I ara la mida de la nostra cua es 3.

140
00:07:03,199 --> 00:07:04,240
Tenim 3 elements en els mateixos.

141
00:07:04,240 --> 00:07:08,490
Així que si haguéssim de, i no anem
que en aquest moment, posar en cua un element més,

142
00:07:08,490 --> 00:07:11,370
que entraria en lloc array
número 3, i la mida de la nostra cua

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

144
00:07:13,160 --> 00:07:15,279
Així que hem en col diversos elements ara.

145
00:07:15,279 --> 00:07:16,570
Ara anem a començar a eliminar-los.

146
00:07:16,570 --> 00:07:19,450
Anem a treure de la cua de la cua.

147
00:07:19,450 --> 00:07:23,340
>> Així similar al pop, que és una espècie
l'anàleg d'això per a piles,

148
00:07:23,340 --> 00:07:26,180
dequeue necessita acceptar una
punter a la queue-- de nou,

149
00:07:26,180 --> 00:07:28,140
llevat que sigui declarat globalment.

150
00:07:28,140 --> 00:07:31,610
Ara volem canviar la ubicació
de la part frontal de la cua.

151
00:07:31,610 --> 00:07:35,050
Aquí és on ve una mena de
en joc, aquesta variable front,

152
00:07:35,050 --> 00:07:37,310
perquè una vegada que eliminem
un element, volem

153
00:07:37,310 --> 00:07:40,720
per moure al següent element més antic.

154
00:07:40,720 --> 00:07:44,180
>> Llavors volem disminuir
la mida de la cua,

155
00:07:44,180 --> 00:07:47,130
i després volem tornar el valor
que va ser eliminat de la cua.

156
00:07:47,130 --> 00:07:48,921
Un cop més, no volem simplement descartar-ho.

157
00:07:48,921 --> 00:07:51,170
Hem de suposar extraient
des del queue-- estem

158
00:07:51,170 --> 00:07:54,170
desencua perquè ens preocupem per ell.

159
00:07:54,170 --> 00:08:01,080
Així que volem aquesta funció per tornar
un element de dades de valor de tipus.

160
00:08:01,080 --> 00:08:04,360
Un cop més, en aquest cas, el valor és sencer.

161
00:08:04,360 --> 00:08:05,670
>> Així que ara anem a treure de la cua alguna cosa.

162
00:08:05,670 --> 00:08:09,310
Anem a treure un element de la cua.

163
00:08:09,310 --> 00:08:15,970
Si diem int x és igual a i q, signe q--
una vegada més que és un punter a aquestes dades q

164
00:08:15,970 --> 00:08:20,177
structure-- quin element
serà tret de la cua?

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

166
00:08:23,840 --> 00:08:29,480
En aquest cas, ja que és una primera
in, first out estructura de dades, FIFO,

167
00:08:29,480 --> 00:08:33,690
la primera cosa que posem en aquest
cua era de 28 anys, de manera que en aquest cas,

168
00:08:33,690 --> 00:08:37,245
tindrem 28 de
la cua, no 19, que és el

169
00:08:37,245 --> 00:08:38,870
ens hagués fet si es tractava d'una pila.

170
00:08:38,870 --> 00:08:42,220
Tindrem 28 fora de la cua.

171
00:08:42,220 --> 00:08:44,960
>> De manera similar al que vam fer amb
una pica, no estem realment

172
00:08:44,960 --> 00:08:47,345
va a eliminar 28
de la cua de si mateix,

173
00:08:47,345 --> 00:08:49,470
només anem a classe
de pretendre que no hi és.

174
00:08:49,470 --> 00:08:51,678
Així que va a quedar-s'hi
en la memòria, però només som

175
00:08:51,678 --> 00:08:57,820
anar a classe d'ignorar-movent
els altres dos camps de les nostres dades q

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

177
00:08:58,830 --> 00:09:00,230
Canviarem la part davantera.

178
00:09:00,230 --> 00:09:04,290
Q.front ara va a
ser 1, ja que és ara

179
00:09:04,290 --> 00:09:07,740
l'element més antic que tenim a la nostra
cua, perquè ja hem eliminat 28,

180
00:09:07,740 --> 00:09:10,460
que va ser el primer element més antic.

181
00:09:10,460 --> 00:09:13,540
>> I ara, volem canviar
la mida de la cua

182
00:09:13,540 --> 00:09:15,780
a dos elements en lloc de tres.

183
00:09:15,780 --> 00:09:20,450
Ara recordeu abans vaig dir quan ens
voleu afegir elements a la cua,

184
00:09:20,450 --> 00:09:26,000
el posem en un lloc array
que és la suma de la part davantera i grandària.

185
00:09:26,000 --> 00:09:29,050
Així que en aquest cas, encara estem posant
ell, el següent element a la cua,

186
00:09:29,050 --> 00:09:33,360
en lloc d'arranjament 3, i
veurem que en un segon.

187
00:09:33,360 --> 00:09:35,730
>> Així que ara que hem desencolen nostra
primer element de la cua.

188
00:09:35,730 --> 00:09:36,480
Anem a fer-ho de nou.

189
00:09:36,480 --> 00:09:38,696
Anem a treure una altra
element de la cua.

190
00:09:38,696 --> 00:09:42,400
En el cas, el corrent més antiga
element és la ubicació matriu 1.

191
00:09:42,400 --> 00:09:44,220
Això és el que q.front ens diu.

192
00:09:44,220 --> 00:09:46,980
Aquesta caixa verda ens diu que
aquest és l'element més antic.

193
00:09:46,980 --> 00:09:49,310
I així, es convertirà en x 33.

194
00:09:49,310 --> 00:09:52,130
Tindrem tipus d'oblidar
33 que hi ha a la matriu,

195
00:09:52,130 --> 00:09:55,100
i direm que ara, la
nou element més antic de la cua

196
00:09:55,100 --> 00:09:58,900
és en la ubicació matriu 2, i la mida
de la cua, el nombre d'elements

197
00:09:58,900 --> 00:10:02,152
tenim a la cua, és 1.

198
00:10:02,152 --> 00:10:05,110
Ara anem a posar en cua alguna cosa, i jo
tipus de donar aquesta distància fa un segon,

199
00:10:05,110 --> 00:10:10,340
però si volem posar 40 al
cua, on està 40 va anar?

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

201
00:10:12,880 --> 00:10:17,730
Bé hem estat posant que
en q.front més cua de grandària,

202
00:10:17,730 --> 00:10:20,850
i així que té sentit
realment posar 40 aquí.

203
00:10:20,850 --> 00:10:22,840
Ara noti que al
algun moment, anem

204
00:10:22,840 --> 00:10:27,980
per arribar a la final de
la nostra gamma interior de q,

205
00:10:27,980 --> 00:10:32,010
però això es va esvair 28 i 33--
en realitat són, tècnicament

206
00:10:32,010 --> 00:10:33,300
espais oberts, oi?

207
00:10:33,300 --> 00:10:36,040
I així, podem eventually--
aquesta regla d'addició

208
00:10:36,040 --> 00:10:40,390
aquests dos junts-- puguem finalment
necessitarà mod per la grandària de la capacitat

209
00:10:40,390 --> 00:10:41,410
perquè puguem embolicar al voltant.

210
00:10:41,410 --> 00:10:43,620
>> Així que si arribem a l'element
número 10, si som

211
00:10:43,620 --> 00:10:48,790
reemplaçant-ho en l'element número 10, estaríem
en realitat el va posar en lloc array 0.

212
00:10:48,790 --> 00:10:50,997
I si ens anàvem a
varietat ubicació: em excusa,

213
00:10:50,997 --> 00:10:53,080
si els afegim junts,
i vam arribar al nombre

214
00:10:53,080 --> 00:10:56,330
11 seria on hauríem de posar
ella, que no existeix en aquest array--

215
00:10:56,330 --> 00:10:58,200
seria anar fora de límits.

216
00:10:58,200 --> 00:11:03,367
Podríem mod 10 i posar
en lloc array 1.

217
00:11:03,367 --> 00:11:04,450
Així és com funcionen les cues.

218
00:11:04,450 --> 00:11:08,540
Ells sempre van a anar d'esquerra
a dreta i possiblement embolicar al voltant.

219
00:11:08,540 --> 00:11:11,280
I vostè sap que són
si a la mida, aquesta caixa vermella,

220
00:11:11,280 --> 00:11:13,710
arriba a ser igual a la capacitat.

221
00:11:13,710 --> 00:11:16,720
I així, després hem afegit 40 a la
cua, bé, ¿què hem de fer?

222
00:11:16,720 --> 00:11:19,890
Bé, l'element més antic
a la cua segueix sent 19,

223
00:11:19,890 --> 00:11:21,990
pel que no volem canviar
la part davantera de la cua,

224
00:11:21,990 --> 00:11:23,820
però ara tenim dos
elements a la cua,

225
00:11:23,820 --> 00:11:28,710
i així volem augmentar
nostre grandària des 1 a 2.

226
00:11:28,710 --> 00:11:31,820
>> Això és més o menys amb
treballant amb les cues de la matriu,

227
00:11:31,820 --> 00:11:33,630
i similar a apilar,
també hi ha una manera

228
00:11:33,630 --> 00:11:36,450
per aplicar una cua com una llista enllaçada.

229
00:11:36,450 --> 00:11:40,150
Ara bé, si aquest tipus d'estructura de dades
sembla familiar per a vostè, ho és.

230
00:11:40,150 --> 00:11:43,780
No és una llista enllaçada,
és una llista doblement enllaçada.

231
00:11:43,780 --> 00:11:46,790
I ara, com un a part, és
en realitat possible implementar

232
00:11:46,790 --> 00:11:50,160
una cua com una llista enllaçada, però
Crec que en termes de visualització,

233
00:11:50,160 --> 00:11:53,350
que en realitat podria ajudar a veure
això com una llista doblement enllaçada.

234
00:11:53,350 --> 00:11:56,850
Però és definitivament possible
fer això com una llista enllaçada.

235
00:11:56,850 --> 00:12:00,110
>> Així que anem a fer una ullada a
el que això podria ser similar.

236
00:12:00,110 --> 00:12:02,750
Si volem enquue--
de manera que ara, un cop més estem

237
00:12:02,750 --> 00:12:05,360
el canvi a una llista enllaçada
model basat aquí.

238
00:12:05,360 --> 00:12:08,420
Si volem posar en cua, volem
afegir un nou element, així

239
00:12:08,420 --> 00:12:09,730
¿Què és el que hem de fer?

240
00:12:09,730 --> 00:12:12,770
Bé, en primer lloc, perquè
estem afegint al final

241
00:12:12,770 --> 00:12:15,520
i l'eliminació de la
començant, probablement

242
00:12:15,520 --> 00:12:20,050
volen mantenir punters tant a la
el cap i la cua de la llista enllaçada?

243
00:12:20,050 --> 00:12:22,660
Cua de ser un altre terme per
al final de la llista enllaçada,

244
00:12:22,660 --> 00:12:24,496
l'últim element de la llista enllaçada.

245
00:12:24,496 --> 00:12:26,620
I aquests probablement,
un cop més, ser beneficiós per a nosaltres

246
00:12:26,620 --> 00:12:28,477
si són variables globals.

247
00:12:28,477 --> 00:12:31,060
Però ara si volem afegir un nou
element, ¿què hem de fer?

248
00:12:31,060 --> 00:12:35,262
El que acabem [? Malak?] O dinàmicament
destinar el nostre nou node per a nosaltres mateixos.

249
00:12:35,262 --> 00:12:38,220
I llavors, igual que quan afegim cap
element a una llista que doblement enllaçada,

250
00:12:38,220 --> 00:12:40,410
només cal ordenar de--
els últims tres passos aquí

251
00:12:40,410 --> 00:12:43,330
són només tracta de moure el
punters en la forma correcta

252
00:12:43,330 --> 00:12:46,710
de manera que l'element s'agrega a
la cadena sense trencar la cadena

253
00:12:46,710 --> 00:12:49,580
o fer algun tipus d'error
o tenir algun tipus d'accident

254
00:12:49,580 --> 00:12:54,505
succeir en què puguem accidentalment
orfes alguns elements de la nostra cua.

255
00:12:54,505 --> 00:12:55,880
Aquí està el que aquest podria ser similar.

256
00:12:55,880 --> 00:13:00,980
Volem afegir l'element
10 fins al final d'aquesta cua.

257
00:13:00,980 --> 00:13:03,380
Així que l'element més antic aquí
està representat pel cap.

258
00:13:03,380 --> 00:13:06,800
Això és el primer que posem
en aquesta cua hipotètica aquí.

259
00:13:06,800 --> 00:13:10,430
I la cua, 13, és el més
Recentment afegit element.

260
00:13:10,430 --> 00:13:17,030
I pel que si volem posar en cua 10 a
aquesta cua, volem posar-ho després del 13.

261
00:13:17,030 --> 00:13:19,860
I així anem a dinàmicament
assignar espai per a un nou node

262
00:13:19,860 --> 00:13:23,280
i verifiqui que no nul·la per assegurar
no tenim un error de memòria.

263
00:13:23,280 --> 00:13:27,040
Llavors anem a
col·locar 10 en aquest node,

264
00:13:27,040 --> 00:13:30,030
i ara hem de tenir cura
sobre com organitzem punters

265
00:13:30,030 --> 00:13:32,180
així que no trenquem la cadena.

266
00:13:32,180 --> 00:13:38,910
>> Podem establir camp anterior de 10
assenyalar de nou a l'edat de la cua,

267
00:13:38,910 --> 00:13:41,620
i des '10 serà el
nova cua en algun moment

268
00:13:41,620 --> 00:13:44,459
de moment tots aquests
cadenes estan connectats,

269
00:13:44,459 --> 00:13:46,250
res vindrà
després del 10 d'ara.

270
00:13:46,250 --> 00:13:49,880
I així que la propera punter de 10
apuntarà a null,

271
00:13:49,880 --> 00:13:53,580
i després fem això, després que hem
connectat 10 cap enrere a la cadena,

272
00:13:53,580 --> 00:13:57,780
podem prendre l'antic cap, o, excusa
jo, el vell de la cua de la cua.

273
00:13:57,780 --> 00:14:02,980
El final antic de la cua,
13, i fer que apunti a 10.

274
00:14:02,980 --> 00:14:08,220
I ara, en aquest moment, tenim
en cua el número 10 en aquesta cua.

275
00:14:08,220 --> 00:14:14,740
Tot el que necessitem fer ara és simplement moure el
cua perquè apunti a 10 en lloc de 13.

276
00:14:14,740 --> 00:14:17,630
>> Desencua és en realitat
molt similar a esclatar

277
00:14:17,630 --> 00:14:21,710
a partir d'una pila que és
implementat com una llista enllaçada

278
00:14:21,710 --> 00:14:24,040
si has vist el vídeo piles.

279
00:14:24,040 --> 00:14:27,280
Tot el que necessitem fer és començar pel
començant, trobar el segon element,

280
00:14:27,280 --> 00:14:30,480
alliberar el primer element,
i després moure el cap

281
00:14:30,480 --> 00:14:32,930
perquè apunti al segon element.

282
00:14:32,930 --> 00:14:37,920
Probablement millor per visualitzar-
només per ser molt clar al respecte.

283
00:14:37,920 --> 00:14:39,230
Així que aquí està la nostra cua de nou.

284
00:14:39,230 --> 00:14:42,600
12 és l'element més antic
en la nostra cua, el cap.

285
00:14:42,600 --> 00:14:46,210
10 és l'element més nou
en la nostra cua, la nostra cua.

286
00:14:46,210 --> 00:14:49,310
>> I així, quan volem
treure de la cua d'un element,

287
00:14:49,310 --> 00:14:52,202
volem eliminar l'element més antic.

288
00:14:52,202 --> 00:14:52,910
Llavors, què fem?

289
00:14:52,910 --> 00:14:55,243
Bé establim un punter recorregut
que comença al capdavant,

290
00:14:55,243 --> 00:14:57,840
i ens movem de manera que
apunta al segon element

291
00:14:57,840 --> 00:15:02,290
d'aquesta queue-- alguna cosa dient trav
és igual a trav fletxa al costat, per exemple,

292
00:15:02,290 --> 00:15:07,170
mouria trav allà per assenyalar
15, el qual, després que treure de la cua 12,

293
00:15:07,170 --> 00:15:13,030
o després traiem 12, voluntat
convertit en l'element més antic llavors.

294
00:15:13,030 --> 00:15:16,360
>> Ara tenim un celler en el primer
element a través del cap del punter

295
00:15:16,360 --> 00:15:19,440
i el segon element
a través de la Trav punter.

296
00:15:19,440 --> 00:15:25,170
Podem cap ara lliure, i llavors podem
dir res arriba abans del 15 de més.

297
00:15:25,170 --> 00:15:29,990
Així que podem canviar 15 de l'anterior
punter per apuntar a null,

298
00:15:29,990 --> 00:15:31,874
i acabem de moure el cap sobre.

299
00:15:31,874 --> 00:15:32,540
I aquí anem.

300
00:15:32,540 --> 00:15:35,840
Ara tenim èxit
tret de la cua 12, i ara nosaltres

301
00:15:35,840 --> 00:15:39,180
tenir una altra cua de 4 elements.

302
00:15:39,180 --> 00:15:41,700
Això és més o menys tot
no a les cues,

303
00:15:41,700 --> 00:15:45,810
tots dos basats en matrius i llista enllaçada amb base.

304
00:15:45,810 --> 00:15:46,860
Sóc Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Això és CS 50.

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