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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Así que si usted tiene
visto el video en la pila,

3
00:00:07,370 --> 00:00:09,870
esto es, probablemente, va a sentir
como un poco de deja vu.

4
00:00:09,870 --> 00:00:13,850
Se va a un concepto muy similar,
sólo con un pequeño giro en él.

5
00:00:13,850 --> 00:00:15,530
Vamos a hablar ahora acerca de las colas.

6
00:00:15,530 --> 00:00:19,350
Así que una cola, similar a una pila,
es otro tipo de estructura de datos

7
00:00:19,350 --> 00:00:22,412
que podemos utilizar para mantener
datos en una manera organizada.

8
00:00:22,412 --> 00:00:24,120
Al igual que en una pila,
puede ser implementado

9
00:00:24,120 --> 00:00:27,000
como una matriz o una lista enlazada.

10
00:00:27,000 --> 00:00:30,320
A diferencia de una pila, las reglas
que utilizamos para determinar

11
00:00:30,320 --> 00:00:34,210
cuando se añaden y eliminan de las cosas
una cola son un poco diferentes.

12
00:00:34,210 --> 00:00:36,590
>> A diferencia de una pila, que
es una estructura LIFO,

13
00:00:36,590 --> 00:00:45,610
último en entrar, primero en salir, una cola es un FIFO
estructura, FIFO, primero en entrar, primero en salir.

14
00:00:45,610 --> 00:00:49,320
Ahora colas, es probable que
tienen una analogía con las colas.

15
00:00:49,320 --> 00:00:52,820
Si alguna vez has estado en la cola
un parque de atracciones o en un banco,

16
00:00:52,820 --> 00:00:56,430
hay una especie de justicia
la implementación de la estructura.

17
00:00:56,430 --> 00:00:59,160
La primera persona en la fila
el banco es la primera persona

18
00:00:59,160 --> 00:01:00,760
quién va a hablar con el cajero.

19
00:01:00,760 --> 00:01:03,522
>> Sería una especie de carrera
a la parte inferior si la única manera

20
00:01:03,522 --> 00:01:06,730
tienes que hablar con el cajero en el
banco iba a ser la última persona en la fila.

21
00:01:06,730 --> 00:01:09,146
Todo el mundo estaría siempre quieren
ser la última persona de la fila,

22
00:01:09,146 --> 00:01:12,580
y la persona que estaba allí primero
quien ha estado esperando por un tiempo,

23
00:01:12,580 --> 00:01:14,715
podría estar allí durante horas,
y horas y horas

24
00:01:14,715 --> 00:01:17,590
antes de que tengan la oportunidad de realidad
retirar dinero en el banco.

25
00:01:17,590 --> 00:01:22,510
Y así, las colas son una especie de
equidad implementación de estructura.

26
00:01:22,510 --> 00:01:25,780
Pero eso no significa necesariamente
que las pilas son algo malo, simplemente

27
00:01:25,780 --> 00:01:28,160
que las colas son otra manera de hacerlo.

28
00:01:28,160 --> 00:01:32,420
Así que de nuevo una cola es primero en entrar, primero
fuera, frente a una pila que dura en,

29
00:01:32,420 --> 00:01:34,440
primero en salir.

30
00:01:34,440 --> 00:01:36,190
Al igual que en una pila,
tenemos dos operaciones

31
00:01:36,190 --> 00:01:38,470
que podemos llevar a cabo en las colas.

32
00:01:38,470 --> 00:01:43,910
Los nombres son enqueue, que consiste en añadir
un nuevo elemento hasta el final de la cola,

33
00:01:43,910 --> 00:01:47,330
y quitar de la cola, que es
para eliminar los más antiguos

34
00:01:47,330 --> 00:01:49,670
elemento desde la parte frontal de la cola.

35
00:01:49,670 --> 00:01:53,600
Así que vamos a añadir elementos
en el extremo de la cola,

36
00:01:53,600 --> 00:01:57,220
y vamos a eliminar elementos
desde la parte frontal de la cola.

37
00:01:57,220 --> 00:02:00,790
Una vez más, con la pila, fuimos agregando
elementos a la parte superior de la pila

38
00:02:00,790 --> 00:02:03,380
y eliminación de elementos
desde la parte superior de la pila.

39
00:02:03,380 --> 00:02:07,570
Así que con enqueue, está añadiendo a
Al final, la eliminación de la parte delantera.

40
00:02:07,570 --> 00:02:10,639
Así que lo más antiguo de allí
siempre es lo próximo

41
00:02:10,639 --> 00:02:13,620
a salir si tratamos
y quitar de la cola algo.

42
00:02:13,620 --> 00:02:18,330
>> Así que de nuevo, con las colas, podemos
implementaciones basadas en matrices

43
00:02:18,330 --> 00:02:20,110
y lista enlazada implementaciones basadas.

44
00:02:20,110 --> 00:02:24,620
Vamos a empezar de nuevo con
implementaciones basadas en matrices.

45
00:02:24,620 --> 00:02:27,070
La definición de la estructura
se ve muy similar.

46
00:02:27,070 --> 00:02:30,720
Tenemos otra matriz
no del valor de tipo de datos,

47
00:02:30,720 --> 00:02:32,690
por lo que puede contener tipos de datos arbitrarios.

48
00:02:32,690 --> 00:02:35,570
Estamos de nuevo va a utilizar
números enteros en este ejemplo.

49
00:02:35,570 --> 00:02:39,830
>> Y al igual que con nuestro
aplicación pila basada en matrices,

50
00:02:39,830 --> 00:02:42,340
porque estamos usando un
array, que necesariamente

51
00:02:42,340 --> 00:02:46,850
tener esa limitación que C tipo
de hace cumplir en nosotros, que somos nosotros

52
00:02:46,850 --> 00:02:51,670
no tienen ningún dinamismo en nuestra
capacidad para crecer y reducir el tamaño de la matriz.

53
00:02:51,670 --> 00:02:55,710
Tenemos que decidir al comienzo
¿cuál es el número máximo de cosas

54
00:02:55,710 --> 00:02:59,300
que podemos poner en este
cola, y en este caso,

55
00:02:59,300 --> 00:03:02,070
capacidad sería algún libras
definida constante en nuestro código.

56
00:03:02,070 --> 00:03:05,430
Y para los fines de esta
de vídeo, la capacidad va a ser 10.

57
00:03:05,430 --> 00:03:07,690
>> Necesitamos hacer un seguimiento de
la parte delantera de la cola de

58
00:03:07,690 --> 00:03:11,160
así que sabemos qué elemento
queremos quitar de la cola,

59
00:03:11,160 --> 00:03:15,070
y también necesitamos hacer un seguimiento de
algo else-- el número de elementos

60
00:03:15,070 --> 00:03:16,690
que tenemos en nuestra cola.

61
00:03:16,690 --> 00:03:19,360
Nótese que no estamos hacer el seguimiento
del final de la cola, justo

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

63
00:03:21,150 --> 00:03:24,310
Y la razón de que se espera
convertido en un poco más clara en un momento.

64
00:03:24,310 --> 00:03:26,143
Una vez que hemos completado
esta definición de tipo,

65
00:03:26,143 --> 00:03:29,080
tenemos un nuevo tipo de datos
llamada cola, que ahora podemos

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

67
00:03:30,630 --> 00:03:35,350
Y un tanto confusamente, he decidido
llamar a esta cola q, la carta

68
00:03:35,350 --> 00:03:38,090
q en lugar del tipo de datos q.

69
00:03:38,090 --> 00:03:39,600
>> Así que aquí está nuestra cola.

70
00:03:39,600 --> 00:03:40,700
Se trata de una estructura.

71
00:03:40,700 --> 00:03:45,730
Contiene tres miembros o de tres
campos, una matriz de tamaño CAPACIDAD.

72
00:03:45,730 --> 00:03:47,340
En este caso, la capacidad es 10.

73
00:03:47,340 --> 00:03:49,580
Y esta matriz es
va a celebrar enteros.

74
00:03:49,580 --> 00:03:55,240
En el verde es el frente de nuestra cola, el
siguiente elemento a ser eliminado, y en rojo

75
00:03:55,240 --> 00:03:58,610
será el tamaño de la cola,
cuántos elementos Actualmente

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

77
00:04:01,190 --> 00:04:05,300
Así que si decimos iguales q.front
0, y el tamaño es igual q.size 0--

78
00:04:05,300 --> 00:04:07,120
estamos poniendo 0s en esos campos.

79
00:04:07,120 --> 00:04:11,070
Y en este punto, estamos más o menos
listo para comenzar a trabajar con nuestra cola.

80
00:04:11,070 --> 00:04:14,140
>> Así que la primera operación que podamos
realizar es poner en cola algo,

81
00:04:14,140 --> 00:04:16,860
añadir un nuevo elemento a
el final de la cola.

82
00:04:16,860 --> 00:04:19,089
Bueno, ¿qué es lo que necesitamos
hacer en el caso general?

83
00:04:19,089 --> 00:04:23,690
Bueno esta función encolar necesidades
para aceptar un puntero a nuestra cola.

84
00:04:23,690 --> 00:04:26,370
Una vez más, si hubiéramos declarado
nuestra cola a nivel mundial,

85
00:04:26,370 --> 00:04:29,490
no necesitaríamos hacer esto
necesariamente, pero en general,

86
00:04:29,490 --> 00:04:32,330
que aceptar punteros
a las estructuras de datos

87
00:04:32,330 --> 00:04:35,040
de esta manera, porque de lo contrario,
estamos pasando por value-- estamos

88
00:04:35,040 --> 00:04:38,140
pasando copias de la cola,
y así no vamos a cambiar realmente

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

90
00:04:41,050 --> 00:04:44,860
>> La otra cosa que tiene que hacer es aceptar
un elemento de datos del tipo apropiado.

91
00:04:44,860 --> 00:04:46,818
Una vez más, en este caso, es
va a ser enteros,

92
00:04:46,818 --> 00:04:49,330
pero usted podría arbitrariamente
declarar el tipo de datos como valor

93
00:04:49,330 --> 00:04:51,160
y utilizar esto de manera más general.

94
00:04:51,160 --> 00:04:56,030
Ese es el elemento que queremos poner en cola,
queremos añadir al final de la cola.

95
00:04:56,030 --> 00:04:58,573
Entonces realmente queremos
colocar los datos en la cola.

96
00:04:58,573 --> 00:05:01,490
En este caso, la colocación en el
correcta ubicación de nuestra matriz,

97
00:05:01,490 --> 00:05:05,040
y luego queremos cambiar el tamaño
de la cola, cuántos elementos de nosotros

98
00:05:05,040 --> 00:05:07,050
Actualmente tener.

99
00:05:07,050 --> 00:05:07,990
>> Así que vamos a empezar.

100
00:05:07,990 --> 00:05:10,890
Este es, de nuevo, que en general
declaración de la función forma

101
00:05:10,890 --> 00:05:13,980
para lo enqueue podría ser similar.

102
00:05:13,980 --> 00:05:14,910
Y aquí vamos.

103
00:05:14,910 --> 00:05:18,335
Vamos a poner en cola el número
28 en la cola.

104
00:05:18,335 --> 00:05:19,460
¿Entonces, que vamos a hacer?

105
00:05:19,460 --> 00:05:23,390
Bueno, la parte delantera de nuestra cola es
a 0, y el tamaño de nuestra cola

106
00:05:23,390 --> 00:05:29,680
está a 0, por lo que probablemente queremos poner
el número 28 en la serie número de elemento

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

108
00:05:31,124 --> 00:05:32,540
Así que ahora hemos puesto que en ese país.

109
00:05:32,540 --> 00:05:34,820
Así que ahora, ¿qué tenemos que cambiar?

110
00:05:34,820 --> 00:05:37,090
No queremos cambiar
la parte delantera de la cola,

111
00:05:37,090 --> 00:05:40,850
porque queremos saber qué elemento
que podríamos necesitar para quitar de la cola más tarde.

112
00:05:40,850 --> 00:05:44,020
Así que la razón por la que tenemos delante no
es una especie de un indicador de lo que es

113
00:05:44,020 --> 00:05:46,439
lo más antiguo de la matriz.

114
00:05:46,439 --> 00:05:49,730
Bueno, la cosa más vieja del array-- en
De hecho, la única cosa en la matriz de la derecha

115
00:05:49,730 --> 00:05:53,540
ahora-- es 28, que es
en la ubicación array 0.

116
00:05:53,540 --> 00:05:56,160
Así que no queremos
cambiar ese número verde,

117
00:05:56,160 --> 00:05:57,910
porque ese es el elemento más antiguo.

118
00:05:57,910 --> 00:06:00,510
Más bien, queremos cambiar el tamaño.

119
00:06:00,510 --> 00:06:04,110
Así que en este caso, vamos a
incremento de tamaño a 1.

120
00:06:04,110 --> 00:06:08,430
>> Ahora una especie general de idea de donde el
siguiente elemento se va a ir en una cola

121
00:06:08,430 --> 00:06:12,310
es añadir esos dos números
juntos, frente y tamaño,

122
00:06:12,310 --> 00:06:16,390
y que te diré donde el próximo
elemento en la cola se va a ir.

123
00:06:16,390 --> 00:06:18,130
Así que ahora vamos a poner en cola otro número.

124
00:06:18,130 --> 00:06:20,250
Vamos a poner en cola 33.

125
00:06:20,250 --> 00:06:24,480
Así que 33 va a entrar en
ubicación matriz 0 + 1.

126
00:06:24,480 --> 00:06:26,840
Así que en este caso, se va
para ir a la ubicación matriz 1,

127
00:06:26,840 --> 00:06:29,500
y ahora el tamaño de nuestra cola es 2.

128
00:06:29,500 --> 00:06:31,840
>> Una vez más, no estamos cambiando
el frente de nuestra cola,

129
00:06:31,840 --> 00:06:34,730
28 porque sigue siendo el
elemento más antiguo, y

130
00:06:34,730 --> 00:06:38,220
quiero a-- cuando finalmente lleguemos
a desencola, eliminación de elementos

131
00:06:38,220 --> 00:06:43,300
de esta cola, queremos saber
donde el elemento más antiguo es.

132
00:06:43,300 --> 00:06:48,620
Y por lo que siempre hay que mantener
algún indicador de dónde está.

133
00:06:48,620 --> 00:06:50,410
Así que eso es lo que el 0 es allí.

134
00:06:50,410 --> 00:06:52,910
Eso es lo que está ahí para delante.

135
00:06:52,910 --> 00:06:55,022
>> Vamos en enqueue un elemento más, 19.

136
00:06:55,022 --> 00:06:56,980
Estoy seguro de que se puede adivinar
donde 19 se va a ir.

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

138
00:06:59,860 --> 00:07:01,570
Eso es 0, más 2.

139
00:07:01,570 --> 00:07:03,199
Y ahora el tamaño de nuestra cola es 3.

140
00:07:03,199 --> 00:07:04,240
Tenemos 3 elementos en los mismos.

141
00:07:04,240 --> 00:07:08,490
Así que si tuviéramos que, y no vamos
que en este momento, poner en cola un elemento más,

142
00:07:08,490 --> 00:07:11,370
que entraría en lugar array
número 3, y el tamaño de nuestra cola

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

144
00:07:13,160 --> 00:07:15,279
Así que hemos en cola varios elementos ahora.

145
00:07:15,279 --> 00:07:16,570
Ahora vamos a empezar a eliminarlos.

146
00:07:16,570 --> 00:07:19,450
Vamos a quitar de la cola de la cola.

147
00:07:19,450 --> 00:07:23,340
>> Así similar al pop, que es una especie
del análogo de esto para pilas,

148
00:07:23,340 --> 00:07:26,180
dequeue necesita aceptar una
puntero a la queue-- de nuevo,

149
00:07:26,180 --> 00:07:28,140
a menos que sea declarado globalmente.

150
00:07:28,140 --> 00:07:31,610
Ahora queremos cambiar la ubicación
de la parte frontal de la cola.

151
00:07:31,610 --> 00:07:35,050
Aquí es donde viene una especie de
en juego, esa variable frente,

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

153
00:07:37,310 --> 00:07:40,720
para moverse al siguiente elemento más antiguo.

154
00:07:40,720 --> 00:07:44,180
>> Entonces queremos disminuir
el tamaño de la cola,

155
00:07:44,180 --> 00:07:47,130
y luego queremos volver el valor
que fue eliminado de la cola.

156
00:07:47,130 --> 00:07:48,921
Una vez más, no queremos simplemente descartarlo.

157
00:07:48,921 --> 00:07:51,170
Hemos de suponer extrayendo
desde el queue-- estamos

158
00:07:51,170 --> 00:07:54,170
desencola porque nos preocupamos por él.

159
00:07:54,170 --> 00:08:01,080
Así que queremos esta función para volver
un elemento de datos de valor de tipo.

160
00:08:01,080 --> 00:08:04,360
Una vez más, en este caso, el valor es entero.

161
00:08:04,360 --> 00:08:05,670
>> Así que ahora vamos a quitar de la cola algo.

162
00:08:05,670 --> 00:08:09,310
Vamos a quitar un elemento de la cola.

163
00:08:09,310 --> 00:08:15,970
Si decimos int x es igual a y q, signo q--
una vez más que es un puntero a estos datos q

164
00:08:15,970 --> 00:08:20,177
structure-- qué elemento
va a ser quitado de la cola?

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

166
00:08:23,840 --> 00:08:29,480
En este caso, ya que es una primera
in, first out estructura de datos, FIFO,

167
00:08:29,480 --> 00:08:33,690
la primera cosa que ponemos en este
cola era de 28 años, por lo que en este caso,

168
00:08:33,690 --> 00:08:37,245
vamos a tener 28 de
la cola, no 19, que es lo

169
00:08:37,245 --> 00:08:38,870
nos hubiera hecho si se trataba de una pila.

170
00:08:38,870 --> 00:08:42,220
Vamos a tener 28 fuera de la cola.

171
00:08:42,220 --> 00:08:44,960
>> De manera similar a lo que hicimos con
una pila, no estamos realmente

172
00:08:44,960 --> 00:08:47,345
va a eliminar 28
de la cola de sí mismo,

173
00:08:47,345 --> 00:08:49,470
sólo vamos a clase
de pretender que no está ahí.

174
00:08:49,470 --> 00:08:51,678
Así que va a permanecer allí
en la memoria, pero sólo somos

175
00:08:51,678 --> 00:08:57,820
ir a clase de ignorarlo moviendo
los otros dos campos de nuestros datos q

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

177
00:08:58,830 --> 00:09:00,230
Vamos a cambiar la parte delantera.

178
00:09:00,230 --> 00:09:04,290
Q.front ahora va a
ser 1, ya que es ahora

179
00:09:04,290 --> 00:09:07,740
el elemento más antiguo que tenemos en nuestra
cola, porque ya hemos eliminado 28,

180
00:09:07,740 --> 00:09:10,460
que fue el primer elemento más antiguo.

181
00:09:10,460 --> 00:09:13,540
>> Y ahora, queremos cambiar
el tamaño de la cola

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

183
00:09:15,780 --> 00:09:20,450
Ahora recuerde antes dije cuando nos
desee añadir elementos a la cola,

184
00:09:20,450 --> 00:09:26,000
lo ponemos en un lugar array
que es la suma de la parte delantera y tamaño.

185
00:09:26,000 --> 00:09:29,050
Así que en este caso, todavía estamos poniendo
él, el siguiente elemento en la cola,

186
00:09:29,050 --> 00:09:33,360
en lugar de arreglo 3, y
veremos que en un segundo.

187
00:09:33,360 --> 00:09:35,730
>> Así que ahora que hemos desencolan nuestra
primer elemento de la cola.

188
00:09:35,730 --> 00:09:36,480
Hagámoslo de nuevo.

189
00:09:36,480 --> 00:09:38,696
Vamos a quitar otra
elemento de la cola.

190
00:09:38,696 --> 00:09:42,400
En el caso, la corriente más antigua
elemento es la ubicación matriz 1.

191
00:09:42,400 --> 00:09:44,220
Eso es lo que q.front nos dice.

192
00:09:44,220 --> 00:09:46,980
Esa caja verde nos dice que
ese es el elemento más antiguo.

193
00:09:46,980 --> 00:09:49,310
Y así, se convertirá en x 33.

194
00:09:49,310 --> 00:09:52,130
Tendremos tipo de olvidar
33 que existe en la matriz,

195
00:09:52,130 --> 00:09:55,100
y vamos a decir que ahora, la
nuevo elemento más antiguo de la cola

196
00:09:55,100 --> 00:09:58,900
es en la ubicación matriz 2, y el tamaño
de la cola, el número de elementos

197
00:09:58,900 --> 00:10:02,152
tenemos en la cola, es 1.

198
00:10:02,152 --> 00:10:05,110
Ahora vamos a poner en cola algo, y yo
tipo de dio esta distancia hace un segundo,

199
00:10:05,110 --> 00:10:10,340
pero si queremos poner 40 en el
cola, donde está 40 va a ir?

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

201
00:10:12,880 --> 00:10:17,730
Bueno hemos estado poniendo que
en q.front más cola de tamaño,

202
00:10:17,730 --> 00:10:20,850
y así que tiene sentido
realmente poner 40 aquí.

203
00:10:20,850 --> 00:10:22,840
Ahora note que al
algún momento, vamos

204
00:10:22,840 --> 00:10:27,980
para llegar a la final de
nuestra gama interior de q,

205
00:10:27,980 --> 00:10:32,010
pero eso se desvaneció 28 y 33--
en realidad son, técnicamente

206
00:10:32,010 --> 00:10:33,300
espacios abiertos, ¿verdad?

207
00:10:33,300 --> 00:10:36,040
Y así, podemos eventually--
esa regla de adición

208
00:10:36,040 --> 00:10:40,390
esos dos juntos-- podamos finalmente
necesitará mod por el tamaño de la capacidad

209
00:10:40,390 --> 00:10:41,410
para que podamos envolver alrededor.

210
00:10:41,410 --> 00:10:43,620
>> Así que si llegamos al elemento
número 10, si somos

211
00:10:43,620 --> 00:10:48,790
reemplazándolo en el elemento número 10, estaríamos
en realidad lo puso en lugar array 0.

212
00:10:48,790 --> 00:10:50,997
Y si nos íbamos a
variedad ubicación: me excusa,

213
00:10:50,997 --> 00:10:53,080
si les agregamos juntos,
y llegamos al número

214
00:10:53,080 --> 00:10:56,330
11 sería donde tendríamos que poner
ella, que no existe en este array--

215
00:10:56,330 --> 00:10:58,200
sería ir fuera de límites.

216
00:10:58,200 --> 00:11:03,367
Podríamos mod 10 y poner
en lugar array 1.

217
00:11:03,367 --> 00:11:04,450
Así es como funcionan las colas.

218
00:11:04,450 --> 00:11:08,540
Ellos siempre van a ir de izquierda
a derecha y posiblemente envolver alrededor.

219
00:11:08,540 --> 00:11:11,280
Y usted sabe que son
si a tamaño completo, esa caja roja,

220
00:11:11,280 --> 00:11:13,710
llega a ser igual a la capacidad.

221
00:11:13,710 --> 00:11:16,720
Y así, después hemos añadido 40 a la
cola, bueno, ¿qué tenemos que hacer?

222
00:11:16,720 --> 00:11:19,890
Bueno, el elemento más antiguo
en la cola sigue siendo 19,

223
00:11:19,890 --> 00:11:21,990
por lo que no queremos cambiar
la parte delantera de la cola,

224
00:11:21,990 --> 00:11:23,820
pero ahora tenemos dos
elementos en la cola,

225
00:11:23,820 --> 00:11:28,710
y así queremos aumentar
nuestro tamaño desde 1 a 2.

226
00:11:28,710 --> 00:11:31,820
>> Eso es más o menos con
trabajando con las colas de la matriz,

227
00:11:31,820 --> 00:11:33,630
y similar a apilar,
también hay un modo

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

229
00:11:36,450 --> 00:11:40,150
Ahora bien, si este tipo de estructura de datos
parece familiar para usted, lo es.

230
00:11:40,150 --> 00:11:43,780
No es una lista enlazada,
es una lista doblemente enlazada.

231
00:11:43,780 --> 00:11:46,790
Y ahora, como un aparte, es
en realidad posible implementar

232
00:11:46,790 --> 00:11:50,160
una cola como una lista enlazada, pero
Creo que en términos de visualización,

233
00:11:50,160 --> 00:11:53,350
que en realidad podría ayudar a ver
esto como una lista doblemente enlazada.

234
00:11:53,350 --> 00:11:56,850
Pero es definitivamente posible
hacer esto como una lista enlazada.

235
00:11:56,850 --> 00:12:00,110
>> Así que vamos a echar un vistazo a
lo que esto podría ser similar.

236
00:12:00,110 --> 00:12:02,750
Si queremos enquue--
por lo que ahora, una vez más estamos

237
00:12:02,750 --> 00:12:05,360
el cambio a una lista enlazada
modelo basado aquí.

238
00:12:05,360 --> 00:12:08,420
Si queremos poner en cola, queremos
añadir un nuevo elemento, así

239
00:12:08,420 --> 00:12:09,730
¿qué es lo que tenemos que hacer?

240
00:12:09,730 --> 00:12:12,770
Bueno, en primer lugar, porque
estamos añadiendo al final

241
00:12:12,770 --> 00:12:15,520
y la eliminación de la
comenzando, probablemente

242
00:12:15,520 --> 00:12:20,050
quieren mantener punteros tanto a la
la cabeza y la cola de la lista enlazada?

243
00:12:20,050 --> 00:12:22,660
Cola de ser otro término para
al final de la lista enlazada,

244
00:12:22,660 --> 00:12:24,496
el último elemento de la lista enlazada.

245
00:12:24,496 --> 00:12:26,620
Y estos probablemente,
una vez más, ser beneficioso para nosotros

246
00:12:26,620 --> 00:12:28,477
si son variables globales.

247
00:12:28,477 --> 00:12:31,060
Pero ahora si queremos añadir un nuevo
elemento, ¿qué tenemos que hacer?

248
00:12:31,060 --> 00:12:35,262
Lo que acabamos [? Malak?] o dinámicamente
destinar nuestro nuevo nodo para nosotros mismos.

249
00:12:35,262 --> 00:12:38,220
Y entonces, al igual que cuando añadimos ninguna
elemento a una lista que doblemente enlazada,

250
00:12:38,220 --> 00:12:40,410
sólo hay que ordenar de--
los últimos tres pasos aquí

251
00:12:40,410 --> 00:12:43,330
son sólo trata de mover el
punteros en la forma correcta

252
00:12:43,330 --> 00:12:46,710
de manera que el elemento se agrega a
la cadena sin romper la cadena

253
00:12:46,710 --> 00:12:49,580
o hacer algún tipo de error
o tener algún tipo de accidente

254
00:12:49,580 --> 00:12:54,505
suceder en que podamos accidentalmente
huérfanos algunos elementos de nuestra cola.

255
00:12:54,505 --> 00:12:55,880
Aquí está lo que este podría ser similar.

256
00:12:55,880 --> 00:13:00,980
Queremos añadir el elemento
10 hasta el final de esta cola.

257
00:13:00,980 --> 00:13:03,380
Así que el elemento más antiguo aquí
está representado por la cabeza.

258
00:13:03,380 --> 00:13:06,800
Eso es lo primero que ponemos
en esta cola hipotética aquí.

259
00:13:06,800 --> 00:13:10,430
Y la cola, 13, es el más
Recientemente añadido elemento.

260
00:13:10,430 --> 00:13:17,030
Y por lo que si queremos poner en cola 10 en
esta cola, queremos ponerlo después del 13.

261
00:13:17,030 --> 00:13:19,860
Y así vamos a dinámicamente
asignar espacio para un nuevo nodo

262
00:13:19,860 --> 00:13:23,280
y verifique que no nula para asegurarse
no tenemos un error de memoria.

263
00:13:23,280 --> 00:13:27,040
Entonces vamos a
colocar 10 en ese nodo,

264
00:13:27,040 --> 00:13:30,030
y ahora tenemos que tener cuidado
acerca de cómo organizamos punteros

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

266
00:13:32,180 --> 00:13:38,910
>> Podemos establecer campo anterior de 10
señalar de nuevo a la edad de la cola,

267
00:13:38,910 --> 00:13:41,620
y desde '10 será el
nueva cola en algún momento

268
00:13:41,620 --> 00:13:44,459
por el momento todos estos
cadenas están conectados,

269
00:13:44,459 --> 00:13:46,250
nada va a venir
después del 10 de ahora.

270
00:13:46,250 --> 00:13:49,880
Y así que la próxima puntero de 10
apuntará a null,

271
00:13:49,880 --> 00:13:53,580
y después hacemos esto, después de que hemos
conectado 10 hacia atrás a la cadena,

272
00:13:53,580 --> 00:13:57,780
podemos tomar el antiguo jefe, o, excusa
yo, el viejo de la cola de la cola.

273
00:13:57,780 --> 00:14:02,980
El final antiguo de la cola,
13, y hacer que apunte a 10.

274
00:14:02,980 --> 00:14:08,220
Y ahora, en este momento, tenemos
en cola el número 10 en esta cola.

275
00:14:08,220 --> 00:14:14,740
Todo lo que necesitamos hacer ahora es simplemente mover el
cola para que apunte a 10 en lugar de 13.

276
00:14:14,740 --> 00:14:17,630
>> Desencola es en realidad
muy similar a estallar

277
00:14:17,630 --> 00:14:21,710
a partir de una pila que es
implementado como una lista enlazada

278
00:14:21,710 --> 00:14:24,040
si has visto el video pilas.

279
00:14:24,040 --> 00:14:27,280
Todo lo que necesitamos hacer es empezar por el
comenzando, encontrar el segundo elemento,

280
00:14:27,280 --> 00:14:30,480
liberar el primer elemento,
y luego mover la cabeza

281
00:14:30,480 --> 00:14:32,930
para que apunte al segundo elemento.

282
00:14:32,930 --> 00:14:37,920
Probablemente mejor para visualizarlo
sólo para ser muy claro al respecto.

283
00:14:37,920 --> 00:14:39,230
Así que aquí está nuestra cola de nuevo.

284
00:14:39,230 --> 00:14:42,600
12 es el elemento más antiguo
en nuestra cola, la cabeza.

285
00:14:42,600 --> 00:14:46,210
10 es el elemento más nuevo
en nuestra cola, nuestra cola.

286
00:14:46,210 --> 00:14:49,310
>> Y así, cuando queremos
quitar de la cola de un elemento,

287
00:14:49,310 --> 00:14:52,202
queremos eliminar el elemento más antiguo.

288
00:14:52,202 --> 00:14:52,910
¿Asi que que hacemos?

289
00:14:52,910 --> 00:14:55,243
Bueno establecemos un puntero recorrido
que comienza a la cabeza,

290
00:14:55,243 --> 00:14:57,840
y nos movemos de forma que
apunta al segundo elemento

291
00:14:57,840 --> 00:15:02,290
de esta queue-- algo diciendo trav
es igual a trav flecha al lado, por ejemplo,

292
00:15:02,290 --> 00:15:07,170
movería trav allí para señalar
15, el cual, después de que quitar de la cola 12,

293
00:15:07,170 --> 00:15:13,030
o después quitamos 12, voluntad
convertido en el elemento más antiguo entonces.

294
00:15:13,030 --> 00:15:16,360
>> Ahora tenemos una bodega en el primer
elemento a través de la cabeza del puntero

295
00:15:16,360 --> 00:15:19,440
y el segundo elemento
a través de la Trav puntero.

296
00:15:19,440 --> 00:15:25,170
Podemos cabeza ahora libre, y entonces podemos
decir nada llega antes del 15 de más.

297
00:15:25,170 --> 00:15:29,990
Así que podemos cambiar 15 del anterior
puntero para apuntar a null,

298
00:15:29,990 --> 00:15:31,874
y acabamos de mover la cabeza sobre.

299
00:15:31,874 --> 00:15:32,540
Y ahí vamos.

300
00:15:32,540 --> 00:15:35,840
Ahora tenemos éxito
quitado de la cola 12, y ahora nosotros

301
00:15:35,840 --> 00:15:39,180
tener otra cola de 4 elementos.

302
00:15:39,180 --> 00:15:41,700
Eso es más o menos todo
no a las colas,

303
00:15:41,700 --> 00:15:45,810
ambos basados ​​en matrices y lista enlazada con base.

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

305
00:15:46,860 --> 00:15:49,100
Esto es CS 50.

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