DOUG LLOYD: Así que si usted tiene visto el video en la pila,
esto es, probablemente, va a sentir como un poco de deja vu.
Se va a un concepto muy similar, sólo con un pequeño giro en él.
Vamos a hablar ahora acerca de las colas.
Así que una cola, similar a una pila, es otro tipo de estructura de datos
que podemos utilizar para mantener datos en una manera organizada.
Al igual que en una pila, puede ser implementado
como una matriz o una lista enlazada.
A diferencia de una pila, las reglas que utilizamos para determinar
cuando se añaden y eliminan de las cosas una cola son un poco diferentes.
>> A diferencia de una pila, que es una estructura LIFO,
último en entrar, primero en salir, una cola es un FIFO estructura, FIFO, primero en entrar, primero en salir.
Ahora colas, es probable que tienen una analogía con las colas.
Si alguna vez has estado en la cola un parque de atracciones o en un banco,
hay una especie de justicia la implementación de la estructura.
La primera persona en la fila el banco es la primera persona
quién va a hablar con el cajero.
>> Sería una especie de carrera a la parte inferior si la única manera
tienes que hablar con el cajero en el banco iba a ser la última persona en la fila.
Todo el mundo estaría siempre quieren ser la última persona de la fila,
y la persona que estaba allí primero quien ha estado esperando por un tiempo,
podría estar allí durante horas, y horas y horas
antes de que tengan la oportunidad de realidad retirar dinero en el banco.
Y así, las colas son una especie de equidad implementación de estructura.
Pero eso no significa necesariamente que las pilas son algo malo, simplemente
que las colas son otra manera de hacerlo.
Así que de nuevo una cola es primero en entrar, primero fuera, frente a una pila que dura en,
primero en salir.
Al igual que en una pila, tenemos dos operaciones
que podemos llevar a cabo en las colas.
Los nombres son enqueue, que consiste en añadir un nuevo elemento hasta el final de la cola,
y quitar de la cola, que es para eliminar los más antiguos
elemento desde la parte frontal de la cola.
Así que vamos a añadir elementos en el extremo de la cola,
y vamos a eliminar elementos desde la parte frontal de la cola.
Una vez más, con la pila, fuimos agregando elementos a la parte superior de la pila
y eliminación de elementos desde la parte superior de la pila.
Así que con enqueue, está añadiendo a Al final, la eliminación de la parte delantera.
Así que lo más antiguo de allí siempre es lo próximo
a salir si tratamos y quitar de la cola algo.
>> Así que de nuevo, con las colas, podemos implementaciones basadas en matrices
y lista enlazada implementaciones basadas.
Vamos a empezar de nuevo con implementaciones basadas en matrices.
La definición de la estructura se ve muy similar.
Tenemos otra matriz no del valor de tipo de datos,
por lo que puede contener tipos de datos arbitrarios.
Estamos de nuevo va a utilizar números enteros en este ejemplo.
>> Y al igual que con nuestro aplicación pila basada en matrices,
porque estamos usando un array, que necesariamente
tener esa limitación que C tipo de hace cumplir en nosotros, que somos nosotros
no tienen ningún dinamismo en nuestra capacidad para crecer y reducir el tamaño de la matriz.
Tenemos que decidir al comienzo ¿cuál es el número máximo de cosas
que podemos poner en este cola, y en este caso,
capacidad sería algún libras definida constante en nuestro código.
Y para los fines de esta de vídeo, la capacidad va a ser 10.
>> Necesitamos hacer un seguimiento de la parte delantera de la cola de
así que sabemos qué elemento queremos quitar de la cola,
y también necesitamos hacer un seguimiento de algo else-- el número de elementos
que tenemos en nuestra cola.
Nótese que no estamos hacer el seguimiento del final de la cola, justo
el tamaño de la cola.
Y la razón de que se espera convertido en un poco más clara en un momento.
Una vez que hemos completado esta definición de tipo,
tenemos un nuevo tipo de datos llamada cola, que ahora podemos
declarar variables de ese tipo de datos.
Y un tanto confusamente, he decidido llamar a esta cola q, la carta
q en lugar del tipo de datos q.
>> Así que aquí está nuestra cola.
Se trata de una estructura.
Contiene tres miembros o de tres campos, una matriz de tamaño CAPACIDAD.
En este caso, la capacidad es 10.
Y esta matriz es va a celebrar enteros.
En el verde es el frente de nuestra cola, el siguiente elemento a ser eliminado, y en rojo
será el tamaño de la cola, cuántos elementos Actualmente
existente en la cola.
Así que si decimos iguales q.front 0, y el tamaño es igual q.size 0--
estamos poniendo 0s en esos campos.
Y en este punto, estamos más o menos listo para comenzar a trabajar con nuestra cola.
>> Así que la primera operación que podamos realizar es poner en cola algo,
añadir un nuevo elemento a el final de la cola.
Bueno, ¿qué es lo que necesitamos hacer en el caso general?
Bueno esta función encolar necesidades para aceptar un puntero a nuestra cola.
Una vez más, si hubiéramos declarado nuestra cola a nivel mundial,
no necesitaríamos hacer esto necesariamente, pero en general,
que aceptar punteros a las estructuras de datos
de esta manera, porque de lo contrario, estamos pasando por value-- estamos
pasando copias de la cola, y así no vamos a cambiar realmente
la cola que tenemos la intención de cambiar.
>> La otra cosa que tiene que hacer es aceptar un elemento de datos del tipo apropiado.
Una vez más, en este caso, es va a ser enteros,
pero usted podría arbitrariamente declarar el tipo de datos como valor
y utilizar esto de manera más general.
Ese es el elemento que queremos poner en cola, queremos añadir al final de la cola.
Entonces realmente queremos colocar los datos en la cola.
En este caso, la colocación en el correcta ubicación de nuestra matriz,
y luego queremos cambiar el tamaño de la cola, cuántos elementos de nosotros
Actualmente tener.
>> Así que vamos a empezar.
Este es, de nuevo, que en general declaración de la función forma
para lo enqueue podría ser similar.
Y aquí vamos.
Vamos a poner en cola el número 28 en la cola.
¿Entonces, que vamos a hacer?
Bueno, la parte delantera de nuestra cola es a 0, y el tamaño de nuestra cola
está a 0, por lo que probablemente queremos poner el número 28 en la serie número de elemento
0, ¿verdad?
Así que ahora hemos puesto que en ese país.
Así que ahora, ¿qué tenemos que cambiar?
No queremos cambiar la parte delantera de la cola,
porque queremos saber qué elemento que podríamos necesitar para quitar de la cola más tarde.
Así que la razón por la que tenemos delante no es una especie de un indicador de lo que es
lo más antiguo de la matriz.
Bueno, la cosa más vieja del array-- en De hecho, la única cosa en la matriz de la derecha
ahora-- es 28, que es en la ubicación array 0.
Así que no queremos cambiar ese número verde,
porque ese es el elemento más antiguo.
Más bien, queremos cambiar el tamaño.
Así que en este caso, vamos a incremento de tamaño a 1.
>> Ahora una especie general de idea de donde el siguiente elemento se va a ir en una cola
es añadir esos dos números juntos, frente y tamaño,
y que te diré donde el próximo elemento en la cola se va a ir.
Así que ahora vamos a poner en cola otro número.
Vamos a poner en cola 33.
Así que 33 va a entrar en ubicación matriz 0 + 1.
Así que en este caso, se va para ir a la ubicación matriz 1,
y ahora el tamaño de nuestra cola es 2.
>> Una vez más, no estamos cambiando el frente de nuestra cola,
28 porque sigue siendo el elemento más antiguo, y
quiero a-- cuando finalmente lleguemos a desencola, eliminación de elementos
de esta cola, queremos saber donde el elemento más antiguo es.
Y por lo que siempre hay que mantener algún indicador de dónde está.
Así que eso es lo que el 0 es allí.
Eso es lo que está ahí para delante.
>> Vamos en enqueue un elemento más, 19.
Estoy seguro de que se puede adivinar donde 19 se va a ir.
Va a entrar en ubicación matriz número 2.
Eso es 0, más 2.
Y ahora el tamaño de nuestra cola es 3.
Tenemos 3 elementos en los mismos.
Así que si tuviéramos que, y no vamos que en este momento, poner en cola un elemento más,
que entraría en lugar array número 3, y el tamaño de nuestra cola
sería 4.
Así que hemos en cola varios elementos ahora.
Ahora vamos a empezar a eliminarlos.
Vamos a quitar de la cola de la cola.
>> Así similar al pop, que es una especie del análogo de esto para pilas,
dequeue necesita aceptar una puntero a la queue-- de nuevo,
a menos que sea declarado globalmente.
Ahora queremos cambiar la ubicación de la parte frontal de la cola.
Aquí es donde viene una especie de en juego, esa variable frente,
porque una vez que eliminamos un elemento, queremos
para moverse al siguiente elemento más antiguo.
>> Entonces queremos disminuir el tamaño de la cola,
y luego queremos volver el valor que fue eliminado de la cola.
Una vez más, no queremos simplemente descartarlo.
Hemos de suponer extrayendo desde el queue-- estamos
desencola porque nos preocupamos por él.
Así que queremos esta función para volver un elemento de datos de valor de tipo.
Una vez más, en este caso, el valor es entero.
>> Así que ahora vamos a quitar de la cola algo.
Vamos a quitar un elemento de la cola.
Si decimos int x es igual a y q, signo q-- una vez más que es un puntero a estos datos q
structure-- qué elemento va a ser quitado de la cola?
En este caso, ya que es una primera in, first out estructura de datos, FIFO,
la primera cosa que ponemos en este cola era de 28 años, por lo que en este caso,
vamos a tener 28 de la cola, no 19, que es lo
nos hubiera hecho si se trataba de una pila.
Vamos a tener 28 fuera de la cola.
>> De manera similar a lo que hicimos con una pila, no estamos realmente
va a eliminar 28 de la cola de sí mismo,
sólo vamos a clase de pretender que no está ahí.
Así que va a permanecer allí en la memoria, pero sólo somos
ir a clase de ignorarlo moviendo los otros dos campos de nuestros datos q
estructura.
Vamos a cambiar la parte delantera.
Q.front ahora va a ser 1, ya que es ahora
el elemento más antiguo que tenemos en nuestra cola, porque ya hemos eliminado 28,
que fue el primer elemento más antiguo.
>> Y ahora, queremos cambiar el tamaño de la cola
a dos elementos en lugar de tres.
Ahora recuerde antes dije cuando nos desee añadir elementos a la cola,
lo ponemos en un lugar array que es la suma de la parte delantera y tamaño.
Así que en este caso, todavía estamos poniendo él, el siguiente elemento en la cola,
en lugar de arreglo 3, y veremos que en un segundo.
>> Así que ahora que hemos desencolan nuestra primer elemento de la cola.
Hagámoslo de nuevo.
Vamos a quitar otra elemento de la cola.
En el caso, la corriente más antigua elemento es la ubicación matriz 1.
Eso es lo que q.front nos dice.
Esa caja verde nos dice que ese es el elemento más antiguo.
Y así, se convertirá en x 33.
Tendremos tipo de olvidar 33 que existe en la matriz,
y vamos a decir que ahora, la nuevo elemento más antiguo de la cola
es en la ubicación matriz 2, y el tamaño de la cola, el número de elementos
tenemos en la cola, es 1.
Ahora vamos a poner en cola algo, y yo tipo de dio esta distancia hace un segundo,
pero si queremos poner 40 en el cola, donde está 40 va a ir?
Bueno hemos estado poniendo que en q.front más cola de tamaño,
y así que tiene sentido realmente poner 40 aquí.
Ahora note que al algún momento, vamos
para llegar a la final de nuestra gama interior de q,
pero eso se desvaneció 28 y 33-- en realidad son, técnicamente
espacios abiertos, ¿verdad?
Y así, podemos eventually-- esa regla de adición
esos dos juntos-- podamos finalmente necesitará mod por el tamaño de la capacidad
para que podamos envolver alrededor.
>> Así que si llegamos al elemento número 10, si somos
reemplazándolo en el elemento número 10, estaríamos en realidad lo puso en lugar array 0.
Y si nos íbamos a variedad ubicación: me excusa,
si les agregamos juntos, y llegamos al número
11 sería donde tendríamos que poner ella, que no existe en este array--
sería ir fuera de límites.
Podríamos mod 10 y poner en lugar array 1.
Así es como funcionan las colas.
Ellos siempre van a ir de izquierda a derecha y posiblemente envolver alrededor.
Y usted sabe que son si a tamaño completo, esa caja roja,
llega a ser igual a la capacidad.
Y así, después hemos añadido 40 a la cola, bueno, ¿qué tenemos que hacer?
Bueno, el elemento más antiguo en la cola sigue siendo 19,
por lo que no queremos cambiar la parte delantera de la cola,
pero ahora tenemos dos elementos en la cola,
y así queremos aumentar nuestro tamaño desde 1 a 2.
>> Eso es más o menos con trabajando con las colas de la matriz,
y similar a apilar, también hay un modo
para aplicar una cola como una lista enlazada.
Ahora bien, si este tipo de estructura de datos parece familiar para usted, lo es.
No es una lista enlazada, es una lista doblemente enlazada.
Y ahora, como un aparte, es en realidad posible implementar
una cola como una lista enlazada, pero Creo que en términos de visualización,
que en realidad podría ayudar a ver esto como una lista doblemente enlazada.
Pero es definitivamente posible hacer esto como una lista enlazada.
>> Así que vamos a echar un vistazo a lo que esto podría ser similar.
Si queremos enquue-- por lo que ahora, una vez más estamos
el cambio a una lista enlazada modelo basado aquí.
Si queremos poner en cola, queremos añadir un nuevo elemento, así
¿qué es lo que tenemos que hacer?
Bueno, en primer lugar, porque estamos añadiendo al final
y la eliminación de la comenzando, probablemente
quieren mantener punteros tanto a la la cabeza y la cola de la lista enlazada?
Cola de ser otro término para al final de la lista enlazada,
el último elemento de la lista enlazada.
Y estos probablemente, una vez más, ser beneficioso para nosotros
si son variables globales.
Pero ahora si queremos añadir un nuevo elemento, ¿qué tenemos que hacer?
Lo que acabamos [? Malak?] o dinámicamente destinar nuestro nuevo nodo para nosotros mismos.
Y entonces, al igual que cuando añadimos ninguna elemento a una lista que doblemente enlazada,
sólo hay que ordenar de-- los últimos tres pasos aquí
son sólo trata de mover el punteros en la forma correcta
de manera que el elemento se agrega a la cadena sin romper la cadena
o hacer algún tipo de error o tener algún tipo de accidente
suceder en que podamos accidentalmente huérfanos algunos elementos de nuestra cola.
Aquí está lo que este podría ser similar.
Queremos añadir el elemento 10 hasta el final de esta cola.
Así que el elemento más antiguo aquí está representado por la cabeza.
Eso es lo primero que ponemos en esta cola hipotética aquí.
Y la cola, 13, es el más Recientemente añadido elemento.
Y por lo que si queremos poner en cola 10 en esta cola, queremos ponerlo después del 13.
Y así vamos a dinámicamente asignar espacio para un nuevo nodo
y verifique que no nula para asegurarse no tenemos un error de memoria.
Entonces vamos a colocar 10 en ese nodo,
y ahora tenemos que tener cuidado acerca de cómo organizamos punteros
así que no rompemos la cadena.
>> Podemos establecer campo anterior de 10 señalar de nuevo a la edad de la cola,
y desde '10 será el nueva cola en algún momento
por el momento todos estos cadenas están conectados,
nada va a venir después del 10 de ahora.
Y así que la próxima puntero de 10 apuntará a null,
y después hacemos esto, después de que hemos conectado 10 hacia atrás a la cadena,
podemos tomar el antiguo jefe, o, excusa yo, el viejo de la cola de la cola.
El final antiguo de la cola, 13, y hacer que apunte a 10.
Y ahora, en este momento, tenemos en cola el número 10 en esta cola.
Todo lo que necesitamos hacer ahora es simplemente mover el cola para que apunte a 10 en lugar de 13.
>> Desencola es en realidad muy similar a estallar
a partir de una pila que es implementado como una lista enlazada
si has visto el video pilas.
Todo lo que necesitamos hacer es empezar por el comenzando, encontrar el segundo elemento,
liberar el primer elemento, y luego mover la cabeza
para que apunte al segundo elemento.
Probablemente mejor para visualizarlo sólo para ser muy claro al respecto.
Así que aquí está nuestra cola de nuevo.
12 es el elemento más antiguo en nuestra cola, la cabeza.
10 es el elemento más nuevo en nuestra cola, nuestra cola.
>> Y así, cuando queremos quitar de la cola de un elemento,
queremos eliminar el elemento más antiguo.
¿Asi que que hacemos?
Bueno establecemos un puntero recorrido que comienza a la cabeza,
y nos movemos de forma que apunta al segundo elemento
de esta queue-- algo diciendo trav es igual a trav flecha al lado, por ejemplo,
movería trav allí para señalar 15, el cual, después de que quitar de la cola 12,
o después quitamos 12, voluntad convertido en el elemento más antiguo entonces.
>> Ahora tenemos una bodega en el primer elemento a través de la cabeza del puntero
y el segundo elemento a través de la Trav puntero.
Podemos cabeza ahora libre, y entonces podemos decir nada llega antes del 15 de más.
Así que podemos cambiar 15 del anterior puntero para apuntar a null,
y acabamos de mover la cabeza sobre.
Y ahí vamos.
Ahora tenemos éxito quitado de la cola 12, y ahora nosotros
tener otra cola de 4 elementos.
Eso es más o menos todo no a las colas,
ambos basados ​​en matrices y lista enlazada con base.
Soy Doug Lloyd.
Esto es CS 50.