Doug LLOYD: Entón, se ten asistir o vídeo na pila, esta é probablemente vai sentir como un pouco de déjà vu. Vai un concepto moi semellante, só cunha lixeira torsión nel. Imos falar agora sobre filas. Así, nunha cola, semellante a unha pila, é outro tipo de estrutura de datos que podemos utilizar para manter datos en forma organizada. Semellante a unha pila, pode ser aplicado como unha matriz ou unha lista vinculada. A diferenza dunha pila, as regras que usan para determinar Cando as cousas están engadidos e eliminar unha fila son un pouco diferentes. A diferenza dunha pila, que é unha estrutura LIFO, último a entrar, primeiro en saír, unha fila é unha FIFO estrutura, FIFO, first in, first out. Agora filas, probablemente ten unha analoxía co filas. Se xa foi en liña no un parque de atraccións ou nun banco, hai unha especie de xustiza estrutura de execución. A primeira persoa na cola do a base é a primeira persoa quen consegue falar co cadro. 

Sería unha especie de carreira para a parte inferior se o único xeito ten que falar co cadro do banco estaba a ser a última persoa en liña. Todos sempre quere para ser a última persoa en liña, ea persoa que estaba alí primeiro que foi esperando por un tempo, podería estar alí por horas, e horas e horas antes de que eles teñan a oportunidade de realmente retirar todo o diñeiro no banco. E así as filas son unha especie de equidade implementación estrutura. Pero iso non significa, necesariamente, que pilas son algo malo, só que as colas son outra forma de facelo. Entón, de novo unha fila é o primeiro en entrar, primeiro fóra, contra unha pila que último a entrar, primeiro en saír. Semellante a unha pila, temos dúas operacións que podemos realizar en filas. Os nomes son enfileiramento, que consiste en engadir un novo elemento para o fin da cola, e desenfileirar, que é para eliminar o máis antigo elemento desde a fronte da fila. Entón, nós estamos indo para engadir elementos para o fin da cola, e nós estamos indo para eliminar elementos desde a fronte da fila. Unha vez máis, coa pila, fomos engadindo elementos para arriba da pila e retirada de elementos dende o principio da pila. Así, con enqueue, está engadindo ao final, a eliminación dende a frontal. Así, o máis antigo de alí é sempre a seguinte cousa para saír, se intentamos e retirar da cola algo. 

Entón, de novo, con filas, podemos implementacións baseadas en array e-lista vinculada implementacións baseadas. Imos comezar de novo con implementacións baseadas en array. A definición da estrutura parece moi similar. Temos outro array hai de valor tipo de datos, para que poida soster tipos de datos arbitrarios. Estamos indo de novo para usar enteiros neste exemplo. 

E, así como coa nosa implantación pila baseada array, porque estamos a usar un matriz, que necesariamente ten esa limitación que tipo C da impón sobre nós, que é o que nós non teñen ningunha dinamismo na nosa capacidade de aumentar e diminuír a matriz. Temos que decidir a principios o que é o número máximo de cousas que podemos poñer en este cola, e, neste caso, capacidade sería algún libra constante definida no noso código. E para os efectos da presente vídeo, capacidade será 10. 

Necesitamos manter o control de a fronte da fila polo que sabemos que elemento queremos retirar da cola, e tamén necesitamos seguir algo else-- o número de elementos que temos na nosa cola. Teña en conta que non estamos mantendo o control do final da cola, só o tamaño da cola. E a razón para que veña a chegar a ser un pouco máis claro en un momento. Unha vez que teñamos completado esta definición de tipo, temos un novo tipo de datos chamada de cola, que podemos agora declarar variables deste tipo de datos. E un tanto confusa, decidín para chamar esa cola q, letra Q en vez do tipo de datos q. 

Entón aquí é a nosa cola. É unha estrutura. Contén tres membros ou tres campos, unha matriz de tamaño capacidade. Neste caso, a capacidade é de 10. E esa matriz é vai realizar enteiros. En verde é a cabeza da nosa cola, o preto elemento a ser eliminado, e en vermello será o tamaño da cola, cantos elementos están actualmente existente na cola. Entón, se nós dicimos iguais q.front 0, eo tamaño é igual a q.size 0-- estamos poñendo 0s en estes campos. E, neste punto, estamos moi bonito listo para comezar a traballar coa nosa cola. 

Así, a primeira operación que pudermos executar é algo para enfileirar, para engadir un novo elemento o fin da cola. Ben, o que necesitamos facer no caso xeral? Ben esta función necesidades enfileirar para aceptar un punteiro para a cola. Unha vez máis, se declarara nosa cola globalmente, nós non necesitamos facelo necesariamente, pero, en xeral, nos Debe aceptar punteiros para estructuras de datos como este, porque, se non, estamos pasando por value-- estamos pasando en copias da cola, e por iso non estamos realmente cambiando a cola que temos a intención de cambiar. 

A outra cousa que cómpre facer é aceptar un elemento de datos do tipo correspondente. Unha vez máis, neste caso, é será enteiros, pero pode arbitrariamente declarar o tipo de datos como valor e usar a forma máis xeral. Ese é o elemento que queremos para enfileirar, queremos engadir ao final da cola. Entón realmente queren poñer os datos na cola. Neste caso, colocándoo no lugar correcto da nosa matriz, e entón nós queremos cambiar o tamaño da cola, cantos elementos que ten actualmente. 

Entón, imos comezar. Aquí está, unha vez máis, que en xeral declaración de función forma para o que enqueue pode parecer. E aquí imos nós. Imos enfileirar o número 28 para dentro da cola. Entón, o que imos facer? Ben, a cabeza da nosa cola é a 0, eo tamaño da nosa cola é a 0, e por iso, probablemente quere poñer o número 28 na matriz número elemento 0, non? Entón, nós temos agora que puxo alí. Entón agora o que necesitamos cambiar? Non queren cambiar a fronte da fila, porque queremos saber o elemento que pode ser necesario para retirar da cola máis tarde. Así, a razón pola que temos diante hai é unha especie de un indicador do que é o máis antiga do array. Ben, a cousa máis antiga do array-- en realidade, o único na matriz dereita agora-- é 28, que é a matriz localización 0. Entón, nós non queremos cambiar este número verde, porque ese é o elemento máis antigo. Pola contra, queremos cambiar o tamaño. Polo tanto, neste caso, imos incrementar tamaño 1. 

Agora, un tipo xeral da idea de onde a preto elemento está indo a ir nunha cola é para engadir estes dous números xuntos, adiante e tamaño, e que lle vai dicir onde o seguinte elemento na cola está a ir. Entón agora imos enfileirar outro número. Imos enfileirar 33. Entón 33 entrará en matriz localización 0 + 1. Polo tanto, neste caso, que vai para entrar nun local da matriz, e agora o tamaño da nosa cola é 2. 

Unha vez máis, non estamos cambiando a cabeza da nosa cola, porque 28 é aínda o máis antigo elemento, e nós quere a-- cando finalmente chegar para dequeuing, eliminación de elementos dende esta fila, queremos saber onde o elemento máis antigo é. E así temos sempre que manter algún indicador de onde é. Entón é iso que a 0 está aí para. Iso é o que está aí para adiante. 

Imos en enqueue un elemento de máis, 19. Estou seguro que pode adiviñar onde 19 está a ir. Vai entrar en matriz número de posición 2. Isto é 0 + 2. E agora o tamaño da nosa cola é 3. Temos 3 elementos nel. Entón, se fósemos, e nós non imos a dereita agora, enfileirar outro elemento, ía entrar en lugar da matriz número 3, eo tamaño da nosa cola sería 4. Entón, nós temos enfileirado varios elementos agora. Agora imos comezar a eliminar-los. Imos desenfileirar-los a partir da fila. 

Así, semellante ao pop, que é unha especie do análogo deste para pilas, dequeue que aceptar unha punteiro para o queue-- novo, a non ser que sexa declarado globalmente. Agora queremos cambiar o lugar de diante da cola. Este é o lugar onde tipo de vén en xogo, esa variable fronte, porque unha vez que eliminar un elemento, queremos para movelo ao seguinte elemento máis antigo. 

Entón queremos diminuír o tamaño da cola, e entón nós queremos devolver o valor que foi eliminado da fila. Unha vez máis, nós non queremos só descartalo lo. Nós probablemente está extraendo lo dende o queue-- estamos dequeuing-lo porque nos preocupa con iso. Entón, nós queremos esta función para voltar un elemento de datos do valor tipo. Unha vez máis, neste caso, é o valor enteiro. 

Entón agora imos retirar da cola algo. Imos eliminar un elemento da fila. Se dicimos int x é igual a & q, comercial q-- unha vez que é un punteiro para este datos q structure-- o elemento será será? Neste caso, xa que é un primeiro in, first out estrutura de datos, FIFO, o primeiro que dedicou a este cola foi de 28, e por tanto, neste caso, imos tomar 28 a cola, non 19, que é o que teriamos feito se iso era unha pila. Nós imos ter 28 para fóra da cola. 

Á semellanza do que fixemos con unha pila, non estamos, en realidade, vai eliminar 28 desde a propia cola, nós só estamos indo a tipo de finxir que non está alí. Entón vai estar alí na memoria, pero nós somos só vai tipo de ignore-lo, movendo os outros dous campos de datos Q noso estrutura. Nós imos cambiar a parte dianteira. Q.front vai agora ser 1, porque esa é agora o elemento máis antigo que temos no noso cola, porque xa eliminou 28, que foi o ex elemento máis antigo. 

E agora, queremos cambiar o tamaño da cola de dous elementos en vez de tres. Agora lembre, eu dixen antes, cando quere engadir elementos á cola, imos poñer-la nun lugar matriz que é a suma da fronte e tamaño. Polo tanto, neste caso, aínda estamos poñendo el, o elemento seguinte na cola, no lugar da matriz 3, e imos ver iso nun segundo. 

Entón, nós temos agora a nosa dequeued primeiro elemento da fila. Imos facelo de novo. Imos eliminar outra elemento da fila. No caso, a cadea máis antigo elemento é un lugar da matriz. Iso é o que nos di q.front. Esa caixa verde nos di que que é o elemento máis antigo. E así, a ser x 33. Nós só unha especie de esquecer 33 que hai na matriz, e imos dicir que agora, o novo elemento máis antigo na cola está no lugar da matriz 2, e do tamaño da cola, o número de elementos temos na cola, é 1. Agora imos enfileirar algo, e eu tipo de deu este fóra un segundo atrás, pero se queremos poñer 40 no cola, onde está 40 indo a ir? Ben, nós estivemos colocando- en q.front máis cola de tamaño, e por iso ten sentido para realmente poñer 40 aquí. Agora conta que polo nalgún momento, nós imos para chegar ao final de nosa matriz dentro q, pero que desapareceu 28 e 33-- son realmente, tecnicamente espazos abertos, non? E así, podemos eventually-- esa regra de engadir aqueles dous together-- podemos finalmente Debe modificación polo tamaño da capacidade por iso, pode involucrar ao redor. 

Entón, se chegamos ao elemento número 10, se estamos substituíndo o no elemento número 10, estariamos realmente poñelas en orde de localización 0. E se nós iamos matriz localização-- me desculpar, se engadimos a eles xuntos, e chegamos ao número 11 estaría onde teriamos que poñer el, que non existe neste array-- estaría indo a fóra dos límites. Poderiamos mod en 10 e colocá- en que lugar da matriz 1. Entón é así que as colas de traballo. Eles están sempre indo a ir desde a esquerda cara á dereita e, posiblemente, participa en torno. E vostede sabe que son en tamaño grande, que a caixa vermella, pasa a ser igual á capacidade. E así, despois engadimos 40 ao cola, así que temos que facer? Ben, o elemento máis antigo na cola é aínda 19, polo que non quere cambiar a fronte da fila, pero agora temos dous elementos na cola, e por iso queremos aumentar noso tamaño 1-2. 

Iso é moi fermoso isto con traballar con colas baseadas en matrices, e semellante para apilar, Hai tamén un xeito para aplicar unha cola como unha lista ligada. Agora, se este tipo de estrutura de datos parece familiar para ti, é. Non é unha lista vinculada illadamente, é unha lista dobremente ligada. E agora, como un aparte, é realmente posible aplicar unha fila como unha lista vinculada illadamente, senón Eu creo que en termos de visualización, realmente pode axudar a ver isto como unha lista dobremente ligada. Pero é sempre posible facelo como unha lista vinculada illadamente. 

Entón imos dar un ollo o que iso pode parecer. Se queremos enquue-- agora, estamos de novo o cambio a unha lista ligada modelo baseado aquí. Se queremos enfileirar, queremos para engadir un novo elemento, así o que necesitamos facer? Ben, en primeiro lugar, porque estamos engadindo ao fin ea retirada desde a comezando, nós probablemente queren manter punteiros para ambos cabeza ea cola da lista ligada? Cola sendo outro termo para o fin da lista ligada, o último elemento da lista ligada. E estes probablemente unha vez máis, ser beneficioso para nós se son variables globais. Pero agora, se queremos engadir un novo elemento que é o que temos que facer? O que nós só [? Malak?] Ou dinamicamente reservar o noso novo nó para nós mesmos. E entón, así como cando nós engadimos calquera elemento dunha lista dobremente ligada nós, só ten que clasificar de-- estes tres últimos pasos aquí son só todo sobre como mover o punteiros na forma correcta de xeito que o elemento se engade ao a cadea sen romper a cadea ou facer algún tipo de erro ou ter algún tipo de accidente pasar polo cal accidentalmente orfos algúns elementos da nosa cola. Aquí está o que iso pode parecer. Queremos engadir o elemento 10 para o extremo desta fila. Así, o elemento máis antigo aquí é representado pola cabeza. Esa é a primeira cousa que poñemos para esta fila hipotético aquí. E cola, 13, é o máis recentemente engadíu elemento. E por iso, se queremos enfileirar 10 en esta fila, queremos poñelo tras 13. E así imos dinamicamente asignar espazo para un novo nodo e comprobar a nula para asegurarse non temos un fallo na memoria. Entón nós imos 10 poñer en que no, e agora necesitamos ter coidado sobre como podemos organizar punteiros así que non romper a cadea. 

Podemos definir 10 do campo anterior para ligar de novo no vello cola, e xa que será a '10 nova cola nalgún momento no momento en que todos estes cadeas están conectados, nada vai vir tras 10 agora. E así 10 do próximo punteiro ha apuntar null, e, a continuación, despois de se facer iso, despois de termos conectado 10 atrás para a cadea, podemos tomar a vella cabeza, ou, escusa me, o vello cola da cola. O vello final da cola, 13, e facelo apuntar a 10. E agora, neste momento, temos enfileirado o número 10 desta fila. Todo o que necesitamos facer agora é só mover o cola para apuntar, no canto de 10 a 13. 

Dequeuing é, en realidade, moi semellantes para avanzar a partir dunha pila que está aplicada como unha lista ligada se xa viu o vídeo Stacks. Todo o que necesitamos facer é comezar a comezando, atopar o segundo elemento, liberar o primeiro elemento, e despois mover a cabeza para apuntar ao segundo elemento. Probablemente mellor para velo só para ser máis claro diso. Entón aquí está a nosa cola de novo. 12 é o elemento máis antigo na nosa cola, a cabeza. 10 é o elemento máis novo na nosa cola, o noso rabo. 

E así, cando queremos para retirar da cola dun elemento, queremos eliminar o elemento máis antigo. Entón, o que facemos? Ben, nós definir un punteiro de paso que comeza na cabeza, e movelo para que apunta para o segundo elemento desta queue-- algo por dicir trav é igual a trav frecha próxima, por exemplo, movería trav para apuntar para alí 15, que, despois de nos retirar da cola 12, ou despois de eliminar 12, vontade chegar a ser o elemento máis vello entón. 

Agora temos un poder sobre o primeiro elemento a través da cabeza do punteiro eo segundo elemento a través do trav punteiro. Podemos cabeza agora está libre, e entón podemos dicir nada vén antes do 15 de anymore. Así, podemos cambiar 15 do anterior punteiro para apuntar para null, e nós só mover a cabeza sobre. E alí imos nós. Agora temos correctamente dequeued 12, e agora nós ten outra fila de 4 elementos. Iso é moi fermoso todo existe a filas, tanto baseada array correo lista ligada baseado. Eu son Doug Lloyd. Este é CS 50.