[Powered by Google Translate] [Cola]
[Chris Gerber, Harvard University]
Esto es CS50, CS50.TV]
Una estructura de datos útil para almacenar una colección ordenada de elementos es una cola.
Se usa cuando los elementos necesitan ser removidos
en el mismo orden en que se han añadido.
Este concepto se conoce como FIFO, que es un acrónimo de primero en entrar, primero en salir.
Para ayudar a visualizar este, puede ser útil para foto
una fila para pagar en una tienda.
Como la gente llega, esperan al final de la línea.
El cajero entonces se turnan para servir a los clientes en el frente,
que salga de la línea a la vez.
En informática, nos referimos a la parte delantera de la cola a la cabeza
y la parte trasera como la cola.
Un ejemplo de cuando se puede utilizar en una aplicación de este
es una lista de espera para inscripciones de clase.
En cuanto se disponga de asientos en la clase,
la persona a la cabeza de la lista de espera se ofrece la oportunidad de inscribirse en la clase.
>> Una cola puede ser construida usando cualquier colección
que almacena los datos en orden, tal como una matriz o una lista enlazada.
Junto con la colección para almacenar los elementos de la cola,
también se necesita un método para agregar elementos al final de la cola,
que se llama enqueuing,
y otra para eliminar un elemento de la cabeza de la cola,
que se llama desencola.
A menudo es útil incluir otro método para devolver la longitud actual de la cola
así como un método para comprobar si la cola está vacía.
Vamos a ver cómo podemos implementar una cola de enteros en C,
utilizando una matriz para la colección de elementos.
En primer lugar, creamos una estructura llamada cola para contener nuestras variables.
Vamos a utilizar una matriz de tamaño fijo 0 índice de enteros
para almacenar los elementos.
También se incluyen una cabeza variable llamada
que almacena el índice del elemento que se encuentra actualmente en la cabeza de la cola.
Una tercera variable, llamada longitud, se utilizará
para realizar un seguimiento del número de elementos en la matriz.
Como alternativa, se puede considerar el uso de una variable llamada cola
para que apunte al elemento último campo en la matriz.
Antes de escribir código más,
vamos a probar nuestro diseño.
Vamos a empezar con una matriz vacía de longitud 0,
con la cabeza a 0.
Ahora vamos a enqueue 4 valores - 6, 2, 3, y 1.
La longitud será ahora 4,
y el jefe se quedará en 0.
>> ¿Qué pasa si quitar de la cola un valor?
Vamos a reducir la longitud a 3,
establecer la cabeza a 1,
y devolver el valor 6.
Ese código se vería así.
Aquí tenemos la función de quitar de la cola,
que toma un puntero a la cola - q - y un puntero al elemento,
que es un tipo int.
En primer lugar, comprobar la longitud de la cola para asegurarse de que es mayor que 0,
para asegurar que hay un elemento a ser quitadas de la cola.
Luego nos fijamos en la matriz de elementos, en la posición de la cabeza,
y establezca el valor de elemento a ser el valor en esa posición.
Luego cambiamos la cabeza para ser el siguiente índice
% De la capacidad.
A continuación, reducir la longitud de la cola por 1.
Por último, volvemos true para indicar que el quitar de la cola se ha realizado correctamente.
Si quitar de la cola de nuevo, la longitud será 2,
la cabeza también se convertirá en dos,
y el valor de retorno será 2.
>> ¿Qué pasa si encolar otro valor, como un 7?
Como ya se encontraban en el final de la cola,
tendremos que envolver y almacenar el valor en 0 elemento de la matriz.
Matemáticamente, esto se puede representar mediante la adición de la longitud
para el índice de la cabeza
y la realización de un módulo utilizando la capacidad de la cola.
Aquí es decir 2 +2, que es 4% 4,
que es 0.
Traduciendo esta idea de codificar tenemos esta función.
Aquí vemos la función de puesta en cola,
que toma un puntero a la cola - q -
y toma el elemento a encolar, que es un número entero.
A continuación comprobar para asegurarse de que la capacidad de la cola
es todavía mayor que la longitud actual de la cola.
A continuación, se guarda el elemento en la matriz de elementos
en el índice que se determina por la cabeza% + longitud de la capacidad de la cola.
A continuación, aumentar la longitud de la cola por 1,
y luego volver true para indicar que la función de puesta en cola se ha realizado correctamente.
>> Además de las dos funciones que hemos mencionado,
hay dos funciones adicionales.
La primera es la función IsEmpty,
que toma un puntero a la cola
y verifica que la longitud es 0.
La segunda es la función de longitud,
que también tiene un puntero a la cola
y devuelve la longitud actual de la estructura.
Esta breve reseña ha demostrado una posible implementación de una cola.
Una de las limitaciones a esta implementación
es que la cola tiene un tamaño máximo fijo.
Si tratamos de añadir más elementos que la cola puede contener,
es posible que debamos ignorar la solicitud y soltar el elemento,
o puede que prefiera volver algún tipo de error.
Uso de una lista vinculada en lugar de una matriz
haría más fácil a tamaño dinámicamente la cola.
Sin embargo, ya que no tienen acceso directo a los elementos de una lista enlazada,
si no mantenemos un registro de la cola,
tendríamos que escanear toda la lista vinculada a llegar hasta el final cada vez.
También podría considerar el uso de una gran variedad de otro tipo de datos,
tales como estructuras, para crear colas de elementos más complejos.
Pensando de nuevo a nuestro ejemplo de una lista de espera de clase,
estas estructuras podrían representar a los estudiantes individuales.
>> Mi nombre es Chris Gerber, y esto es CS50.
[CS50.TV]
Y vuelta - >> Una vez más.
Y devolver true para indicar que - la cola se ha realizado correctamente.
-% De la capacidad de la cola -
Va a ser divertido en edición. [Risas]