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

2
00:00:05,204 --> 00:00:07,370
Doug LLOYD: Entón, se ten
asistir o vídeo na pila,

3
00:00:07,370 --> 00:00:09,870
esta é probablemente vai sentir
como un pouco de déjà vu.

4
00:00:09,870 --> 00:00:13,850
Vai un concepto moi semellante,
só cunha lixeira torsión nel.

5
00:00:13,850 --> 00:00:15,530
Imos falar agora sobre filas.

6
00:00:15,530 --> 00:00:19,350
Así, nunha cola, semellante a unha pila,
é outro tipo de estrutura de datos

7
00:00:19,350 --> 00:00:22,412
que podemos utilizar para manter
datos en forma organizada.

8
00:00:22,412 --> 00:00:24,120
Semellante a unha pila,
pode ser aplicado

9
00:00:24,120 --> 00:00:27,000
como unha matriz ou unha lista vinculada.

10
00:00:27,000 --> 00:00:30,320
A diferenza dunha pila, as regras
que usan para determinar

11
00:00:30,320 --> 00:00:34,210
Cando as cousas están engadidos e eliminar
unha fila son un pouco diferentes.

12
00:00:34,210 --> 00:00:36,590
>> A diferenza dunha pila, que
é unha estrutura LIFO,

13
00:00:36,590 --> 00:00:45,610
último a entrar, primeiro en saír, unha fila é unha FIFO
estrutura, FIFO, first in, first out.

14
00:00:45,610 --> 00:00:49,320
Agora filas, probablemente
ten unha analoxía co filas.

15
00:00:49,320 --> 00:00:52,820
Se xa foi en liña no
un parque de atraccións ou nun banco,

16
00:00:52,820 --> 00:00:56,430
hai unha especie de xustiza
estrutura de execución.

17
00:00:56,430 --> 00:00:59,160
A primeira persoa na cola do
a base é a primeira persoa

18
00:00:59,160 --> 00:01:00,760
quen consegue falar co cadro.

19
00:01:00,760 --> 00:01:03,522
>> Sería unha especie de carreira
para a parte inferior se o único xeito

20
00:01:03,522 --> 00:01:06,730
ten que falar co cadro do
banco estaba a ser a última persoa en liña.

21
00:01:06,730 --> 00:01:09,146
Todos sempre quere
para ser a última persoa en liña,

22
00:01:09,146 --> 00:01:12,580
ea persoa que estaba alí primeiro
que foi esperando por un tempo,

23
00:01:12,580 --> 00:01:14,715
podería estar alí por horas,
e horas e horas

24
00:01:14,715 --> 00:01:17,590
antes de que eles teñan a oportunidade de realmente
retirar todo o diñeiro no banco.

25
00:01:17,590 --> 00:01:22,510
E así as filas son unha especie de
equidade implementación estrutura.

26
00:01:22,510 --> 00:01:25,780
Pero iso non significa, necesariamente,
que pilas son algo malo, só

27
00:01:25,780 --> 00:01:28,160
que as colas son outra forma de facelo.

28
00:01:28,160 --> 00:01:32,420
Entón, de novo unha fila é o primeiro en entrar, primeiro
fóra, contra unha pila que último a entrar,

29
00:01:32,420 --> 00:01:34,440
primeiro en saír.

30
00:01:34,440 --> 00:01:36,190
Semellante a unha pila,
temos dúas operacións

31
00:01:36,190 --> 00:01:38,470
que podemos realizar en filas.

32
00:01:38,470 --> 00:01:43,910
Os nomes son enfileiramento, que consiste en engadir
un novo elemento para o fin da cola,

33
00:01:43,910 --> 00:01:47,330
e desenfileirar, que é
para eliminar o máis antigo

34
00:01:47,330 --> 00:01:49,670
elemento desde a fronte da fila.

35
00:01:49,670 --> 00:01:53,600
Entón, nós estamos indo para engadir elementos
para o fin da cola,

36
00:01:53,600 --> 00:01:57,220
e nós estamos indo para eliminar elementos
desde a fronte da fila.

37
00:01:57,220 --> 00:02:00,790
Unha vez máis, coa pila, fomos engadindo
elementos para arriba da pila

38
00:02:00,790 --> 00:02:03,380
e retirada de elementos
dende o principio da pila.

39
00:02:03,380 --> 00:02:07,570
Así, con enqueue, está engadindo ao
final, a eliminación dende a frontal.

40
00:02:07,570 --> 00:02:10,639
Así, o máis antigo de alí
é sempre a seguinte cousa

41
00:02:10,639 --> 00:02:13,620
para saír, se intentamos
e retirar da cola algo.

42
00:02:13,620 --> 00:02:18,330
>> Entón, de novo, con filas, podemos
implementacións baseadas en array

43
00:02:18,330 --> 00:02:20,110
e-lista vinculada implementacións baseadas.

44
00:02:20,110 --> 00:02:24,620
Imos comezar de novo con
implementacións baseadas en array.

45
00:02:24,620 --> 00:02:27,070
A definición da estrutura
parece moi similar.

46
00:02:27,070 --> 00:02:30,720
Temos outro array
hai de valor tipo de datos,

47
00:02:30,720 --> 00:02:32,690
para que poida soster tipos de datos arbitrarios.

48
00:02:32,690 --> 00:02:35,570
Estamos indo de novo para usar
enteiros neste exemplo.

49
00:02:35,570 --> 00:02:39,830
>> E, así como coa nosa
implantación pila baseada array,

50
00:02:39,830 --> 00:02:42,340
porque estamos a usar un
matriz, que necesariamente

51
00:02:42,340 --> 00:02:46,850
ten esa limitación que tipo C
da impón sobre nós, que é o que nós

52
00:02:46,850 --> 00:02:51,670
non teñen ningunha dinamismo na nosa
capacidade de aumentar e diminuír a matriz.

53
00:02:51,670 --> 00:02:55,710
Temos que decidir a principios
o que é o número máximo de cousas

54
00:02:55,710 --> 00:02:59,300
que podemos poñer en este
cola, e, neste caso,

55
00:02:59,300 --> 00:03:02,070
capacidade sería algún libra
constante definida no noso código.

56
00:03:02,070 --> 00:03:05,430
E para os efectos da presente
vídeo, capacidade será 10.

57
00:03:05,430 --> 00:03:07,690
>> Necesitamos manter o control de
a fronte da fila

58
00:03:07,690 --> 00:03:11,160
polo que sabemos que elemento
queremos retirar da cola,

59
00:03:11,160 --> 00:03:15,070
e tamén necesitamos seguir
algo else-- o número de elementos

60
00:03:15,070 --> 00:03:16,690
que temos na nosa cola.

61
00:03:16,690 --> 00:03:19,360
Teña en conta que non estamos mantendo o control
do final da cola, só

62
00:03:19,360 --> 00:03:21,150
o tamaño da cola.

63
00:03:21,150 --> 00:03:24,310
E a razón para que veña a
chegar a ser un pouco máis claro en un momento.

64
00:03:24,310 --> 00:03:26,143
Unha vez que teñamos completado
esta definición de tipo,

65
00:03:26,143 --> 00:03:29,080
temos un novo tipo de datos
chamada de cola, que podemos agora

66
00:03:29,080 --> 00:03:30,630
declarar variables deste tipo de datos.

67
00:03:30,630 --> 00:03:35,350
E un tanto confusa, decidín
para chamar esa cola q, letra

68
00:03:35,350 --> 00:03:38,090
Q en vez do tipo de datos q.

69
00:03:38,090 --> 00:03:39,600
>> Entón aquí é a nosa cola.

70
00:03:39,600 --> 00:03:40,700
É unha estrutura.

71
00:03:40,700 --> 00:03:45,730
Contén tres membros ou tres
campos, unha matriz de tamaño capacidade.

72
00:03:45,730 --> 00:03:47,340
Neste caso, a capacidade é de 10.

73
00:03:47,340 --> 00:03:49,580
E esa matriz é
vai realizar enteiros.

74
00:03:49,580 --> 00:03:55,240
En verde é a cabeza da nosa cola, o
preto elemento a ser eliminado, e en vermello

75
00:03:55,240 --> 00:03:58,610
será o tamaño da cola,
cantos elementos están actualmente

76
00:03:58,610 --> 00:04:01,190
existente na cola.

77
00:04:01,190 --> 00:04:05,300
Entón, se nós dicimos iguais q.front
0, eo tamaño é igual a q.size 0--

78
00:04:05,300 --> 00:04:07,120
estamos poñendo 0s en estes campos.

79
00:04:07,120 --> 00:04:11,070
E, neste punto, estamos moi bonito
listo para comezar a traballar coa nosa cola.

80
00:04:11,070 --> 00:04:14,140
>> Así, a primeira operación que pudermos
executar é algo para enfileirar,

81
00:04:14,140 --> 00:04:16,860
para engadir un novo elemento
o fin da cola.

82
00:04:16,860 --> 00:04:19,089
Ben, o que necesitamos
facer no caso xeral?

83
00:04:19,089 --> 00:04:23,690
Ben esta función necesidades enfileirar
para aceptar un punteiro para a cola.

84
00:04:23,690 --> 00:04:26,370
Unha vez máis, se declarara
nosa cola globalmente,

85
00:04:26,370 --> 00:04:29,490
nós non necesitamos facelo
necesariamente, pero, en xeral, nos

86
00:04:29,490 --> 00:04:32,330
Debe aceptar punteiros
para estructuras de datos

87
00:04:32,330 --> 00:04:35,040
como este, porque, se non,
estamos pasando por value-- estamos

88
00:04:35,040 --> 00:04:38,140
pasando en copias da cola,
e por iso non estamos realmente cambiando

89
00:04:38,140 --> 00:04:41,050
a cola que temos a intención de cambiar.

90
00:04:41,050 --> 00:04:44,860
>> A outra cousa que cómpre facer é aceptar
un elemento de datos do tipo correspondente.

91
00:04:44,860 --> 00:04:46,818
Unha vez máis, neste caso, é
será enteiros,

92
00:04:46,818 --> 00:04:49,330
pero pode arbitrariamente
declarar o tipo de datos como valor

93
00:04:49,330 --> 00:04:51,160
e usar a forma máis xeral.

94
00:04:51,160 --> 00:04:56,030
Ese é o elemento que queremos para enfileirar,
queremos engadir ao final da cola.

95
00:04:56,030 --> 00:04:58,573
Entón realmente queren
poñer os datos na cola.

96
00:04:58,573 --> 00:05:01,490
Neste caso, colocándoo no
lugar correcto da nosa matriz,

97
00:05:01,490 --> 00:05:05,040
e entón nós queremos cambiar o tamaño
da cola, cantos elementos que

98
00:05:05,040 --> 00:05:07,050
ten actualmente.

99
00:05:07,050 --> 00:05:07,990
>> Entón, imos comezar.

100
00:05:07,990 --> 00:05:10,890
Aquí está, unha vez máis, que en xeral
declaración de función forma

101
00:05:10,890 --> 00:05:13,980
para o que enqueue pode parecer.

102
00:05:13,980 --> 00:05:14,910
E aquí imos nós.

103
00:05:14,910 --> 00:05:18,335
Imos enfileirar o número
28 para dentro da cola.

104
00:05:18,335 --> 00:05:19,460
Entón, o que imos facer?

105
00:05:19,460 --> 00:05:23,390
Ben, a cabeza da nosa cola é
a 0, eo tamaño da nosa cola

106
00:05:23,390 --> 00:05:29,680
é a 0, e por iso, probablemente quere poñer
o número 28 na matriz número elemento

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

108
00:05:31,124 --> 00:05:32,540
Entón, nós temos agora que puxo alí.

109
00:05:32,540 --> 00:05:34,820
Entón agora o que necesitamos cambiar?

110
00:05:34,820 --> 00:05:37,090
Non queren cambiar
a fronte da fila,

111
00:05:37,090 --> 00:05:40,850
porque queremos saber o elemento
que pode ser necesario para retirar da cola máis tarde.

112
00:05:40,850 --> 00:05:44,020
Así, a razón pola que temos diante hai
é unha especie de un indicador do que é

113
00:05:44,020 --> 00:05:46,439
o máis antiga do array.

114
00:05:46,439 --> 00:05:49,730
Ben, a cousa máis antiga do array-- en
realidade, o único na matriz dereita

115
00:05:49,730 --> 00:05:53,540
agora-- é 28, que é
a matriz localización 0.

116
00:05:53,540 --> 00:05:56,160
Entón, nós non queremos
cambiar este número verde,

117
00:05:56,160 --> 00:05:57,910
porque ese é o elemento máis antigo.

118
00:05:57,910 --> 00:06:00,510
Pola contra, queremos cambiar o tamaño.

119
00:06:00,510 --> 00:06:04,110
Polo tanto, neste caso, imos
incrementar tamaño 1.

120
00:06:04,110 --> 00:06:08,430
>> Agora, un tipo xeral da idea de onde a
preto elemento está indo a ir nunha cola

121
00:06:08,430 --> 00:06:12,310
é para engadir estes dous números
xuntos, adiante e tamaño,

122
00:06:12,310 --> 00:06:16,390
e que lle vai dicir onde o seguinte
elemento na cola está a ir.

123
00:06:16,390 --> 00:06:18,130
Entón agora imos enfileirar outro número.

124
00:06:18,130 --> 00:06:20,250
Imos enfileirar 33.

125
00:06:20,250 --> 00:06:24,480
Entón 33 entrará en
matriz localización 0 + 1.

126
00:06:24,480 --> 00:06:26,840
Polo tanto, neste caso, que vai
para entrar nun local da matriz,

127
00:06:26,840 --> 00:06:29,500
e agora o tamaño da nosa cola é 2.

128
00:06:29,500 --> 00:06:31,840
>> Unha vez máis, non estamos cambiando
a cabeza da nosa cola,

129
00:06:31,840 --> 00:06:34,730
porque 28 é aínda o
máis antigo elemento, e nós

130
00:06:34,730 --> 00:06:38,220
quere a-- cando finalmente chegar
para dequeuing, eliminación de elementos

131
00:06:38,220 --> 00:06:43,300
dende esta fila, queremos saber
onde o elemento máis antigo é.

132
00:06:43,300 --> 00:06:48,620
E así temos sempre que manter
algún indicador de onde é.

133
00:06:48,620 --> 00:06:50,410
Entón é iso que a 0 está aí para.

134
00:06:50,410 --> 00:06:52,910
Iso é o que está aí para adiante.

135
00:06:52,910 --> 00:06:55,022
>> Imos en enqueue un elemento de máis, 19.

136
00:06:55,022 --> 00:06:56,980
Estou seguro que pode adiviñar
onde 19 está a ir.

137
00:06:56,980 --> 00:06:59,860
Vai entrar en
matriz número de posición 2.

138
00:06:59,860 --> 00:07:01,570
Isto é 0 + 2.

139
00:07:01,570 --> 00:07:03,199
E agora o tamaño da nosa cola é 3.

140
00:07:03,199 --> 00:07:04,240
Temos 3 elementos nel.

141
00:07:04,240 --> 00:07:08,490
Entón, se fósemos, e nós non imos
a dereita agora, enfileirar outro elemento,

142
00:07:08,490 --> 00:07:11,370
ía entrar en lugar da matriz
número 3, eo tamaño da nosa cola

143
00:07:11,370 --> 00:07:13,160
sería 4.

144
00:07:13,160 --> 00:07:15,279
Entón, nós temos enfileirado varios elementos agora.

145
00:07:15,279 --> 00:07:16,570
Agora imos comezar a eliminar-los.

146
00:07:16,570 --> 00:07:19,450
Imos desenfileirar-los a partir da fila.

147
00:07:19,450 --> 00:07:23,340
>> Así, semellante ao pop, que é unha especie
do análogo deste para pilas,

148
00:07:23,340 --> 00:07:26,180
dequeue que aceptar unha
punteiro para o queue-- novo,

149
00:07:26,180 --> 00:07:28,140
a non ser que sexa declarado globalmente.

150
00:07:28,140 --> 00:07:31,610
Agora queremos cambiar o lugar
de diante da cola.

151
00:07:31,610 --> 00:07:35,050
Este é o lugar onde tipo de vén
en xogo, esa variable fronte,

152
00:07:35,050 --> 00:07:37,310
porque unha vez que eliminar
un elemento, queremos

153
00:07:37,310 --> 00:07:40,720
para movelo ao seguinte elemento máis antigo.

154
00:07:40,720 --> 00:07:44,180
>> Entón queremos diminuír
o tamaño da cola,

155
00:07:44,180 --> 00:07:47,130
e entón nós queremos devolver o valor
que foi eliminado da fila.

156
00:07:47,130 --> 00:07:48,921
Unha vez máis, nós non queremos só descartalo lo.

157
00:07:48,921 --> 00:07:51,170
Nós probablemente está extraendo
lo dende o queue-- estamos

158
00:07:51,170 --> 00:07:54,170
dequeuing-lo porque nos preocupa con iso.

159
00:07:54,170 --> 00:08:01,080
Entón, nós queremos esta función para voltar
un elemento de datos do valor tipo.

160
00:08:01,080 --> 00:08:04,360
Unha vez máis, neste caso, é o valor enteiro.

161
00:08:04,360 --> 00:08:05,670
>> Entón agora imos retirar da cola algo.

162
00:08:05,670 --> 00:08:09,310
Imos eliminar un elemento da fila.

163
00:08:09,310 --> 00:08:15,970
Se dicimos int x é igual a & q, comercial q--
unha vez que é un punteiro para este datos q

164
00:08:15,970 --> 00:08:20,177
structure-- o elemento
será será?

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

166
00:08:23,840 --> 00:08:29,480
Neste caso, xa que é un primeiro
in, first out estrutura de datos, FIFO,

167
00:08:29,480 --> 00:08:33,690
o primeiro que dedicou a este
cola foi de 28, e por tanto, neste caso,

168
00:08:33,690 --> 00:08:37,245
imos tomar 28
a cola, non 19, que é o que

169
00:08:37,245 --> 00:08:38,870
teriamos feito se iso era unha pila.

170
00:08:38,870 --> 00:08:42,220
Nós imos ter 28 para fóra da cola.

171
00:08:42,220 --> 00:08:44,960
>> Á semellanza do que fixemos con
unha pila, non estamos, en realidade,

172
00:08:44,960 --> 00:08:47,345
vai eliminar 28
desde a propia cola,

173
00:08:47,345 --> 00:08:49,470
nós só estamos indo a tipo
de finxir que non está alí.

174
00:08:49,470 --> 00:08:51,678
Entón vai estar alí
na memoria, pero nós somos só

175
00:08:51,678 --> 00:08:57,820
vai tipo de ignore-lo, movendo
os outros dous campos de datos Q noso

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

177
00:08:58,830 --> 00:09:00,230
Nós imos cambiar a parte dianteira.

178
00:09:00,230 --> 00:09:04,290
Q.front vai agora
ser 1, porque esa é agora

179
00:09:04,290 --> 00:09:07,740
o elemento máis antigo que temos no noso
cola, porque xa eliminou 28,

180
00:09:07,740 --> 00:09:10,460
que foi o ex elemento máis antigo.

181
00:09:10,460 --> 00:09:13,540
>> E agora, queremos cambiar
o tamaño da cola

182
00:09:13,540 --> 00:09:15,780
de dous elementos en vez de tres.

183
00:09:15,780 --> 00:09:20,450
Agora lembre, eu dixen antes, cando
quere engadir elementos á cola,

184
00:09:20,450 --> 00:09:26,000
imos poñer-la nun lugar matriz
que é a suma da fronte e tamaño.

185
00:09:26,000 --> 00:09:29,050
Polo tanto, neste caso, aínda estamos poñendo
el, o elemento seguinte na cola,

186
00:09:29,050 --> 00:09:33,360
no lugar da matriz 3, e
imos ver iso nun segundo.

187
00:09:33,360 --> 00:09:35,730
>> Entón, nós temos agora a nosa dequeued
primeiro elemento da fila.

188
00:09:35,730 --> 00:09:36,480
Imos facelo de novo.

189
00:09:36,480 --> 00:09:38,696
Imos eliminar outra
elemento da fila.

190
00:09:38,696 --> 00:09:42,400
No caso, a cadea máis antigo
elemento é un lugar da matriz.

191
00:09:42,400 --> 00:09:44,220
Iso é o que nos di q.front.

192
00:09:44,220 --> 00:09:46,980
Esa caixa verde nos di que
que é o elemento máis antigo.

193
00:09:46,980 --> 00:09:49,310
E así, a ser x 33.

194
00:09:49,310 --> 00:09:52,130
Nós só unha especie de esquecer
33 que hai na matriz,

195
00:09:52,130 --> 00:09:55,100
e imos dicir que agora, o
novo elemento máis antigo na cola

196
00:09:55,100 --> 00:09:58,900
está no lugar da matriz 2, e do tamaño
da cola, o número de elementos

197
00:09:58,900 --> 00:10:02,152
temos na cola, é 1.

198
00:10:02,152 --> 00:10:05,110
Agora imos enfileirar algo, e eu
tipo de deu este fóra un segundo atrás,

199
00:10:05,110 --> 00:10:10,340
pero se queremos poñer 40 no
cola, onde está 40 indo a ir?

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

201
00:10:12,880 --> 00:10:17,730
Ben, nós estivemos colocando-
en q.front máis cola de tamaño,

202
00:10:17,730 --> 00:10:20,850
e por iso ten sentido para
realmente poñer 40 aquí.

203
00:10:20,850 --> 00:10:22,840
Agora conta que polo
nalgún momento, nós imos

204
00:10:22,840 --> 00:10:27,980
para chegar ao final de
nosa matriz dentro q,

205
00:10:27,980 --> 00:10:32,010
pero que desapareceu 28 e 33--
son realmente, tecnicamente

206
00:10:32,010 --> 00:10:33,300
espazos abertos, non?

207
00:10:33,300 --> 00:10:36,040
E así, podemos eventually--
esa regra de engadir

208
00:10:36,040 --> 00:10:40,390
aqueles dous together-- podemos finalmente
Debe modificación polo tamaño da capacidade

209
00:10:40,390 --> 00:10:41,410
por iso, pode involucrar ao redor.

210
00:10:41,410 --> 00:10:43,620
>> Entón, se chegamos ao elemento
número 10, se estamos

211
00:10:43,620 --> 00:10:48,790
substituíndo o no elemento número 10, estariamos
realmente poñelas en orde de localización 0.

212
00:10:48,790 --> 00:10:50,997
E se nós iamos
matriz localização-- me desculpar,

213
00:10:50,997 --> 00:10:53,080
se engadimos a eles xuntos,
e chegamos ao número

214
00:10:53,080 --> 00:10:56,330
11 estaría onde teriamos que poñer
el, que non existe neste array--

215
00:10:56,330 --> 00:10:58,200
estaría indo a fóra dos límites.

216
00:10:58,200 --> 00:11:03,367
Poderiamos mod en 10 e colocá-
en que lugar da matriz 1.

217
00:11:03,367 --> 00:11:04,450
Entón é así que as colas de traballo.

218
00:11:04,450 --> 00:11:08,540
Eles están sempre indo a ir desde a esquerda
cara á dereita e, posiblemente, participa en torno.

219
00:11:08,540 --> 00:11:11,280
E vostede sabe que son
en tamaño grande, que a caixa vermella,

220
00:11:11,280 --> 00:11:13,710
pasa a ser igual á capacidade.

221
00:11:13,710 --> 00:11:16,720
E así, despois engadimos 40 ao
cola, así que temos que facer?

222
00:11:16,720 --> 00:11:19,890
Ben, o elemento máis antigo
na cola é aínda 19,

223
00:11:19,890 --> 00:11:21,990
polo que non quere cambiar
a fronte da fila,

224
00:11:21,990 --> 00:11:23,820
pero agora temos dous
elementos na cola,

225
00:11:23,820 --> 00:11:28,710
e por iso queremos aumentar
noso tamaño 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Iso é moi fermoso isto con
traballar con colas baseadas en matrices,

227
00:11:31,820 --> 00:11:33,630
e semellante para apilar,
Hai tamén un xeito

228
00:11:33,630 --> 00:11:36,450
para aplicar unha cola como unha lista ligada.

229
00:11:36,450 --> 00:11:40,150
Agora, se este tipo de estrutura de datos
parece familiar para ti, é.

230
00:11:40,150 --> 00:11:43,780
Non é unha lista vinculada illadamente,
é unha lista dobremente ligada.

231
00:11:43,780 --> 00:11:46,790
E agora, como un aparte, é
realmente posible aplicar

232
00:11:46,790 --> 00:11:50,160
unha fila como unha lista vinculada illadamente, senón
Eu creo que en termos de visualización,

233
00:11:50,160 --> 00:11:53,350
realmente pode axudar a ver
isto como unha lista dobremente ligada.

234
00:11:53,350 --> 00:11:56,850
Pero é sempre posible
facelo como unha lista vinculada illadamente.

235
00:11:56,850 --> 00:12:00,110
>> Entón imos dar un ollo
o que iso pode parecer.

236
00:12:00,110 --> 00:12:02,750
Se queremos enquue--
agora, estamos de novo

237
00:12:02,750 --> 00:12:05,360
o cambio a unha lista ligada
modelo baseado aquí.

238
00:12:05,360 --> 00:12:08,420
Se queremos enfileirar, queremos
para engadir un novo elemento, así

239
00:12:08,420 --> 00:12:09,730
o que necesitamos facer?

240
00:12:09,730 --> 00:12:12,770
Ben, en primeiro lugar, porque
estamos engadindo ao fin

241
00:12:12,770 --> 00:12:15,520
ea retirada desde a
comezando, nós probablemente

242
00:12:15,520 --> 00:12:20,050
queren manter punteiros para ambos
cabeza ea cola da lista ligada?

243
00:12:20,050 --> 00:12:22,660
Cola sendo outro termo para
o fin da lista ligada,

244
00:12:22,660 --> 00:12:24,496
o último elemento da lista ligada.

245
00:12:24,496 --> 00:12:26,620
E estes probablemente
unha vez máis, ser beneficioso para nós

246
00:12:26,620 --> 00:12:28,477
se son variables globais.

247
00:12:28,477 --> 00:12:31,060
Pero agora, se queremos engadir un novo
elemento que é o que temos que facer?

248
00:12:31,060 --> 00:12:35,262
O que nós só [? Malak?] Ou dinamicamente
reservar o noso novo nó para nós mesmos.

249
00:12:35,262 --> 00:12:38,220
E entón, así como cando nós engadimos calquera
elemento dunha lista dobremente ligada nós,

250
00:12:38,220 --> 00:12:40,410
só ten que clasificar de--
estes tres últimos pasos aquí

251
00:12:40,410 --> 00:12:43,330
son só todo sobre como mover o
punteiros na forma correcta

252
00:12:43,330 --> 00:12:46,710
de xeito que o elemento se engade ao
a cadea sen romper a cadea

253
00:12:46,710 --> 00:12:49,580
ou facer algún tipo de erro
ou ter algún tipo de accidente

254
00:12:49,580 --> 00:12:54,505
pasar polo cal accidentalmente
orfos algúns elementos da nosa cola.

255
00:12:54,505 --> 00:12:55,880
Aquí está o que iso pode parecer.

256
00:12:55,880 --> 00:13:00,980
Queremos engadir o elemento
10 para o extremo desta fila.

257
00:13:00,980 --> 00:13:03,380
Así, o elemento máis antigo aquí
é representado pola cabeza.

258
00:13:03,380 --> 00:13:06,800
Esa é a primeira cousa que poñemos
para esta fila hipotético aquí.

259
00:13:06,800 --> 00:13:10,430
E cola, 13, é o máis
recentemente engadíu elemento.

260
00:13:10,430 --> 00:13:17,030
E por iso, se queremos enfileirar 10 en
esta fila, queremos poñelo tras 13.

261
00:13:17,030 --> 00:13:19,860
E así imos dinamicamente
asignar espazo para un novo nodo

262
00:13:19,860 --> 00:13:23,280
e comprobar a nula para asegurarse
non temos un fallo na memoria.

263
00:13:23,280 --> 00:13:27,040
Entón nós imos
10 poñer en que no,

264
00:13:27,040 --> 00:13:30,030
e agora necesitamos ter coidado
sobre como podemos organizar punteiros

265
00:13:30,030 --> 00:13:32,180
así que non romper a cadea.

266
00:13:32,180 --> 00:13:38,910
>> Podemos definir 10 do campo anterior
para ligar de novo no vello cola,

267
00:13:38,910 --> 00:13:41,620
e xa que será a '10
nova cola nalgún momento

268
00:13:41,620 --> 00:13:44,459
no momento en que todos estes
cadeas están conectados,

269
00:13:44,459 --> 00:13:46,250
nada vai vir
tras 10 agora.

270
00:13:46,250 --> 00:13:49,880
E así 10 do próximo punteiro
ha apuntar null,

271
00:13:49,880 --> 00:13:53,580
e, a continuación, despois de se facer iso, despois de termos
conectado 10 atrás para a cadea,

272
00:13:53,580 --> 00:13:57,780
podemos tomar a vella cabeza, ou, escusa
me, o vello cola da cola.

273
00:13:57,780 --> 00:14:02,980
O vello final da cola,
13, e facelo apuntar a 10.

274
00:14:02,980 --> 00:14:08,220
E agora, neste momento, temos
enfileirado o número 10 desta fila.

275
00:14:08,220 --> 00:14:14,740
Todo o que necesitamos facer agora é só mover o
cola para apuntar, no canto de 10 a 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing é, en realidade,
moi semellantes para avanzar

277
00:14:17,630 --> 00:14:21,710
a partir dunha pila que está
aplicada como unha lista ligada

278
00:14:21,710 --> 00:14:24,040
se xa viu o vídeo Stacks.

279
00:14:24,040 --> 00:14:27,280
Todo o que necesitamos facer é comezar a
comezando, atopar o segundo elemento,

280
00:14:27,280 --> 00:14:30,480
liberar o primeiro elemento,
e despois mover a cabeza

281
00:14:30,480 --> 00:14:32,930
para apuntar ao segundo elemento.

282
00:14:32,930 --> 00:14:37,920
Probablemente mellor para velo
só para ser máis claro diso.

283
00:14:37,920 --> 00:14:39,230
Entón aquí está a nosa cola de novo.

284
00:14:39,230 --> 00:14:42,600
12 é o elemento máis antigo
na nosa cola, a cabeza.

285
00:14:42,600 --> 00:14:46,210
10 é o elemento máis novo
na nosa cola, o noso rabo.

286
00:14:46,210 --> 00:14:49,310
>> E así, cando queremos
para retirar da cola dun elemento,

287
00:14:49,310 --> 00:14:52,202
queremos eliminar o elemento máis antigo.

288
00:14:52,202 --> 00:14:52,910
Entón, o que facemos?

289
00:14:52,910 --> 00:14:55,243
Ben, nós definir un punteiro de paso
que comeza na cabeza,

290
00:14:55,243 --> 00:14:57,840
e movelo para que
apunta para o segundo elemento

291
00:14:57,840 --> 00:15:02,290
desta queue-- algo por dicir trav
é igual a trav frecha próxima, por exemplo,

292
00:15:02,290 --> 00:15:07,170
movería trav para apuntar para alí
15, que, despois de nos retirar da cola 12,

293
00:15:07,170 --> 00:15:13,030
ou despois de eliminar 12, vontade
chegar a ser o elemento máis vello entón.

294
00:15:13,030 --> 00:15:16,360
>> Agora temos un poder sobre o primeiro
elemento a través da cabeza do punteiro

295
00:15:16,360 --> 00:15:19,440
eo segundo elemento
a través do trav punteiro.

296
00:15:19,440 --> 00:15:25,170
Podemos cabeza agora está libre, e entón podemos
dicir nada vén antes do 15 de anymore.

297
00:15:25,170 --> 00:15:29,990
Así, podemos cambiar 15 do anterior
punteiro para apuntar para null,

298
00:15:29,990 --> 00:15:31,874
e nós só mover a cabeza sobre.

299
00:15:31,874 --> 00:15:32,540
E alí imos nós.

300
00:15:32,540 --> 00:15:35,840
Agora temos correctamente
dequeued 12, e agora nós

301
00:15:35,840 --> 00:15:39,180
ten outra fila de 4 elementos.

302
00:15:39,180 --> 00:15:41,700
Iso é moi fermoso todo
existe a filas,

303
00:15:41,700 --> 00:15:45,810
tanto baseada array correo lista ligada baseado.

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

305
00:15:46,860 --> 00:15:49,100
Este é CS 50.

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