1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Cola]

2
00:00:02,000 --> 00:00:05,000
[Chris Gerber, Harvard University]

3
00:00:05,000 --> 00:00:07,000
Esto es CS50, CS50.TV]

4
00:00:07,000 --> 00:00:11,000
Una estructura de datos útil para almacenar una colección ordenada de elementos es una cola.

5
00:00:11,000 --> 00:00:14,000
Se usa cuando los elementos necesitan ser removidos

6
00:00:14,000 --> 00:00:16,000
en el mismo orden en que se han añadido.

7
00:00:16,000 --> 00:00:20,000
Este concepto se conoce como FIFO, que es un acrónimo de primero en entrar, primero en salir.

8
00:00:20,000 --> 00:00:23,000
Para ayudar a visualizar este, puede ser útil para foto

9
00:00:23,000 --> 00:00:25,000
una fila para pagar en una tienda.

10
00:00:25,000 --> 00:00:28,000
Como la gente llega, esperan al final de la línea.

11
00:00:28,000 --> 00:00:31,000
El cajero entonces se turnan para servir a los clientes en el frente,

12
00:00:31,000 --> 00:00:34,000
que salga de la línea a la vez.

13
00:00:34,000 --> 00:00:37,000
En informática, nos referimos a la parte delantera de la cola a la cabeza

14
00:00:37,000 --> 00:00:39,000
y la parte trasera como la cola.

15
00:00:39,000 --> 00:00:41,000
Un ejemplo de cuando se puede utilizar en una aplicación de este

16
00:00:41,000 --> 00:00:44,000
es una lista de espera para inscripciones de clase.

17
00:00:44,000 --> 00:00:46,000
En cuanto se disponga de asientos en la clase,

18
00:00:46,000 --> 00:00:50,000
la persona a la cabeza de la lista de espera se ofrece la oportunidad de inscribirse en la clase.

19
00:00:50,000 --> 00:00:53,000
>> Una cola puede ser construida usando cualquier colección

20
00:00:53,000 --> 00:00:57,000
que almacena los datos en orden, tal como una matriz o una lista enlazada.

21
00:00:57,000 --> 00:01:00,000
Junto con la colección para almacenar los elementos de la cola,

22
00:01:00,000 --> 00:01:02,000
también se necesita un método para agregar elementos al final de la cola,

23
00:01:02,000 --> 00:01:04,000
que se llama enqueuing,

24
00:01:04,000 --> 00:01:07,000
y otra para eliminar un elemento de la cabeza de la cola,

25
00:01:07,000 --> 00:01:09,000
que se llama desencola.

26
00:01:09,000 --> 00:01:14,000
A menudo es útil incluir otro método para devolver la longitud actual de la cola

27
00:01:14,000 --> 00:01:17,000
así como un método para comprobar si la cola está vacía.

28
00:01:17,000 --> 00:01:20,000
Vamos a ver cómo podemos implementar una cola de enteros en C,

29
00:01:20,000 --> 00:01:23,000
utilizando una matriz para la colección de elementos.

30
00:01:23,000 --> 00:01:27,000
En primer lugar, creamos una estructura llamada cola para contener nuestras variables.

31
00:01:27,000 --> 00:01:30,000
Vamos a utilizar una matriz de tamaño fijo 0 índice de enteros

32
00:01:30,000 --> 00:01:33,000
para almacenar los elementos.

33
00:01:33,000 --> 00:01:35,000
También se incluyen una cabeza variable llamada

34
00:01:35,000 --> 00:01:39,000
que almacena el índice del elemento que se encuentra actualmente en la cabeza de la cola.

35
00:01:39,000 --> 00:01:42,000
Una tercera variable, llamada longitud, se utilizará

36
00:01:42,000 --> 00:01:45,000
para realizar un seguimiento del número de elementos en la matriz.

37
00:01:45,000 --> 00:01:48,000
Como alternativa, se puede considerar el uso de una variable llamada cola

38
00:01:48,000 --> 00:01:51,000
para que apunte al elemento último campo en la matriz.

39
00:01:51,000 --> 00:01:53,000
Antes de escribir código más,

40
00:01:53,000 --> 00:01:55,000
vamos a probar nuestro diseño.

41
00:01:55,000 --> 00:01:58,000
Vamos a empezar con una matriz vacía de longitud 0,

42
00:01:58,000 --> 00:02:02,000
con la cabeza a 0.

43
00:02:02,000 --> 00:02:11,000
Ahora vamos a enqueue 4 valores - 6, 2, 3, y 1.

44
00:02:11,000 --> 00:02:14,000
La longitud será ahora 4,

45
00:02:14,000 --> 00:02:17,000
y el jefe se quedará en 0.

46
00:02:17,000 --> 00:02:20,000
>> ¿Qué pasa si quitar de la cola un valor?

47
00:02:20,000 --> 00:02:24,000
Vamos a reducir la longitud a 3,

48
00:02:24,000 --> 00:02:28,000
establecer la cabeza a 1,

49
00:02:28,000 --> 00:02:33,000
y devolver el valor 6.

50
00:02:33,000 --> 00:02:36,000
Ese código se vería así.

51
00:02:36,000 --> 00:02:38,000
Aquí tenemos la función de quitar de la cola,

52
00:02:38,000 --> 00:02:41,000
que toma un puntero a la cola - q - y un puntero al elemento,

53
00:02:41,000 --> 00:02:44,000
que es un tipo int.

54
00:02:44,000 --> 00:02:47,000
En primer lugar, comprobar la longitud de la cola para asegurarse de que es mayor que 0,

55
00:02:47,000 --> 00:02:50,000
para asegurar que hay un elemento a ser quitadas de la cola.

56
00:02:50,000 --> 00:02:54,000
Luego nos fijamos en la matriz de elementos, en la posición de la cabeza,

57
00:02:54,000 --> 00:02:58,000
y establezca el valor de elemento a ser el valor en esa posición.

58
00:02:58,000 --> 00:03:01,000
Luego cambiamos la cabeza para ser el siguiente índice

59
00:03:01,000 --> 00:03:04,000
% De la capacidad.

60
00:03:04,000 --> 00:03:07,000
A continuación, reducir la longitud de la cola por 1.

61
00:03:07,000 --> 00:03:12,000
Por último, volvemos true para indicar que el quitar de la cola se ha realizado correctamente.

62
00:03:12,000 --> 00:03:19,000
Si quitar de la cola de nuevo, la longitud será 2,

63
00:03:19,000 --> 00:03:24,000
la cabeza también se convertirá en dos,

64
00:03:24,000 --> 00:03:32,000
y el valor de retorno será 2.

65
00:03:32,000 --> 00:03:35,000
>> ¿Qué pasa si encolar otro valor, como un 7?

66
00:03:35,000 --> 00:03:37,000
Como ya se encontraban en el final de la cola,

67
00:03:37,000 --> 00:03:47,000
tendremos que envolver y almacenar el valor en 0 elemento de la matriz.

68
00:03:47,000 --> 00:03:50,000
Matemáticamente, esto se puede representar mediante la adición de la longitud

69
00:03:50,000 --> 00:03:52,000
para el índice de la cabeza

70
00:03:52,000 --> 00:03:55,000
y la realización de un módulo utilizando la capacidad de la cola.

71
00:03:55,000 --> 00:04:00,000
Aquí es decir 2 +2, que es 4% 4,

72
00:04:00,000 --> 00:04:02,000
que es 0.

73
00:04:02,000 --> 00:04:05,000
Traduciendo esta idea de codificar tenemos esta función.

74
00:04:05,000 --> 00:04:08,000
Aquí vemos la función de puesta en cola,

75
00:04:08,000 --> 00:04:10,000
que toma un puntero a la cola - q -

76
00:04:10,000 --> 00:04:14,000
y toma el elemento a encolar, que es un número entero.

77
00:04:14,000 --> 00:04:18,000
A continuación comprobar para asegurarse de que la capacidad de la cola

78
00:04:18,000 --> 00:04:21,000
es todavía mayor que la longitud actual de la cola.

79
00:04:21,000 --> 00:04:24,000
A continuación, se guarda el elemento en la matriz de elementos

80
00:04:24,000 --> 00:04:30,000
en el índice que se determina por la cabeza% + longitud de la capacidad de la cola.

81
00:04:30,000 --> 00:04:33,000
A continuación, aumentar la longitud de la cola por 1,

82
00:04:33,000 --> 00:04:39,000
y luego volver true para indicar que la función de puesta en cola se ha realizado correctamente.

83
00:04:39,000 --> 00:04:42,000
>> Además de las dos funciones que hemos mencionado,

84
00:04:42,000 --> 00:04:44,000
hay dos funciones adicionales.

85
00:04:44,000 --> 00:04:46,000
La primera es la función IsEmpty,

86
00:04:46,000 --> 00:04:48,000
que toma un puntero a la cola

87
00:04:48,000 --> 00:04:51,000
y verifica que la longitud es 0.

88
00:04:51,000 --> 00:04:53,000
La segunda es la función de longitud,

89
00:04:53,000 --> 00:04:55,000
que también tiene un puntero a la cola

90
00:04:55,000 --> 00:04:58,000
y devuelve la longitud actual de la estructura.

91
00:04:58,000 --> 00:05:03,000
Esta breve reseña ha demostrado una posible implementación de una cola.

92
00:05:03,000 --> 00:05:06,000
Una de las limitaciones a esta implementación

93
00:05:06,000 --> 00:05:08,000
es que la cola tiene un tamaño máximo fijo.

94
00:05:08,000 --> 00:05:11,000
Si tratamos de añadir más elementos que la cola puede contener,

95
00:05:11,000 --> 00:05:14,000
es posible que debamos ignorar la solicitud y soltar el elemento,

96
00:05:14,000 --> 00:05:17,000
o puede que prefiera volver algún tipo de error.

97
00:05:17,000 --> 00:05:20,000
Uso de una lista vinculada en lugar de una matriz

98
00:05:20,000 --> 00:05:22,000
haría más fácil a tamaño dinámicamente la cola.

99
00:05:22,000 --> 00:05:26,000
Sin embargo, ya que no tienen acceso directo a los elementos de una lista enlazada,

100
00:05:26,000 --> 00:05:28,000
si no mantenemos un registro de la cola,

101
00:05:28,000 --> 00:05:32,000
tendríamos que escanear toda la lista vinculada a llegar hasta el final cada vez.

102
00:05:32,000 --> 00:05:35,000
También podría considerar el uso de una gran variedad de otro tipo de datos,

103
00:05:35,000 --> 00:05:39,000
tales como estructuras, para crear colas de elementos más complejos.

104
00:05:39,000 --> 00:05:42,000
Pensando de nuevo a nuestro ejemplo de una lista de espera de clase,

105
00:05:42,000 --> 00:05:45,000
estas estructuras podrían representar a los estudiantes individuales.

106
00:05:45,000 --> 00:05:48,000
>> Mi nombre es Chris Gerber, y esto es CS50.

107
00:05:48,000 --> 00:05:51,000
[CS50.TV]

108
00:05:51,000 --> 00:05:55,000
Y vuelta - >> Una vez más.

109
00:05:55,000 --> 00:06:00,000
Y devolver true para indicar que - la cola se ha realizado correctamente.

110
00:06:00,000 --> 00:06:03,000
-% De la capacidad de la cola -

111
00:06:03,000 --> 00:06:06,000
Va a ser divertido en edición. [Risas]