DOUG LLOYD: Então, se você tem assisti o vídeo na pilha, esta é provavelmente vai sentir como um pouco de deja vu. Vai um conceito muito semelhante, apenas com uma leve torção nele. Vamos falar agora sobre filas. Assim, uma fila, semelhante a uma pilha, é um outro tipo de estrutura de dados que podemos usar para manter dados em uma forma organizada. Semelhante a uma pilha, ele pode ser implementado como uma matriz ou uma lista vinculada. Ao contrário de uma pilha, as regras que usamos para determinar Quando as coisas ficam adicionados e removidos uma fila são um pouco diferentes. Ao contrário de uma pilha, que é uma estrutura LIFO, último a entrar, primeiro a sair, uma fila é uma FIFO estrutura, FIFO, first in, first out. Agora filas, você provavelmente tem uma analogia com filas. Se você já foi em linha no um parque de diversões ou em um banco, há uma espécie de justiça estrutura de execução. A primeira pessoa na fila do o banco é a primeira pessoa quem consegue falar com o caixa. 

Seria uma espécie de corrida para a parte inferior se a única maneira você tem que falar com o caixa do banco era para ser a última pessoa na linha. Todo mundo sempre quer para ser a última pessoa na linha, ea pessoa que estava lá primeiro que tem sido esperando por um tempo, poderia estar lá por horas, e horas e horas antes que eles tenham a chance de realmente retirar todo o dinheiro no banco. E assim as filas são uma espécie de equidade implementação estrutura. Mas isso não significa, necessariamente, que pilhas são uma coisa ruim, apenas que as filas são outra forma de fazê-lo. Então, novamente uma fila é o primeiro a entrar, primeiro fora, contra uma pilha que último a entrar, primeiro a sair. Semelhante a uma pilha, temos duas operações que podemos realizar em filas. Os nomes são enfileiramento, que consiste em adicionar um novo elemento para o fim da fila, e desenfileirar, que é para remover o mais antigo elemento a partir da frente da fila. Então, nós estamos indo para adicionar elementos para o fim da fila, e nós estamos indo para remover elementos a partir da frente da fila. Mais uma vez, com a pilha, fomos acrescentando elementos para o topo da pilha e remoção de elementos a partir do topo da pilha. Assim, com enqueue, está adicionando ao final, a remoção a partir da frente. Assim, a coisa mais antiga de lá é sempre a próxima coisa para sair, se tentarmos e retirar da fila algo. 

Então, novamente, com filas, nós podemos implementações baseadas em array e-lista vinculada implementações baseadas. Vamos começar de novo com implementações baseadas em array. A definição da estrutura parece muito similar. Temos outro array há de valor tipo de dados, para que ele possa segurar tipos de dados arbitrários. Nós estamos indo novamente para usar inteiros neste exemplo. 

E, assim como com a nossa implementação pilha baseada em array, porque nós estamos usando um matriz, que necessariamente tem essa limitação que tipo C da impõe sobre nós, o que é que nós não têm qualquer dinamismo na nossa capacidade de aumentar e diminuir a matriz. Temos que decidir no início o que é o número máximo de coisas que podemos colocar em este fila, e, neste caso, capacidade seria algum libra constante definida em nosso código. E para os efeitos da presente vídeo, capacidade vai ser 10. 

Precisamos manter o controle de a frente da fila por isso sabemos que elemento queremos retirar da fila, e também precisamos de acompanhar algo else-- o número de elementos que temos em nossa fila. Observe que não estamos mantendo o controle do final da fila, apenas o tamanho da fila. E a razão para que venha a tornar-se um pouco mais claro em um momento. Uma vez que tenhamos concluído esta definição de tipo, temos um novo tipo de dados chamada de fila, que nós podemos agora declarar variáveis ​​desse tipo de dados. E um tanto confusa, eu decidi para chamar essa fila q, a letra Q em vez do tipo de dados q. 

Então aqui é a nossa fila. É uma estrutura. Ele contém três membros ou três campos, uma matriz de tamanho capacidade. Neste caso, a capacidade é de 10. E essa matriz é vai realizar inteiros. Em verde é a frente da nossa fila, o próximo elemento a ser removido, e no vermelho será o tamanho da fila, quantos elementos estão atualmente existente na fila. Então, se nós dizemos iguais q.front 0, eo tamanho é igual a q.size 0-- estamos colocando 0s em esses campos. E, neste ponto, estamos muito bonito pronto para começar a trabalhar com a nossa fila. 

Assim, a primeira operação que pudermos executar é algo para enfileirar, para adicionar um novo elemento o fim da fila. Bem, o que nós precisamos fazer no caso geral? Bem esta função necessidades enfileirar para aceitar um ponteiro para a fila. Mais uma vez, se tinha declarado nossa fila globalmente, nós não precisamos fazer isso necessariamente, mas, em geral, nós precisa aceitar ponteiros para estruturas de dados como este, porque, caso contrário, nós estamos passando por value-- estamos passando em cópias da fila, e por isso não estamos realmente mudando a fila que temos a intenção de mudar. 

A outra coisa que precisa fazer é aceitar um elemento de dados do tipo apropriado. Mais uma vez, neste caso, é vai ser inteiros, mas você pode arbitrariamente declarar o tipo de dados como valor e utilizar esta forma mais geral. Esse é o elemento que queremos para enfileirar, queremos adicionar ao final da fila. Então nós realmente querem colocar os dados na fila. Neste caso, colocando-o no local correto da nossa matriz, e então nós queremos mudar o tamanho da fila, quantos elementos que tem atualmente. 

Então, vamos começar. Aqui está, mais uma vez, que em geral declaração de função forma para o que enqueue pode parecer. E aqui vamos nós. Vamos enfileirar o número 28 para dentro da fila. Então, o que vamos fazer? Bem, a frente da nossa fila é a 0, eo tamanho da nossa fila é a 0, e por isso, provavelmente quer colocar o número 28 na matriz número elemento 0, certo? Então, nós temos agora que colocou lá. Então agora o que precisamos mudar? Nós não querem mudar a frente da fila, porque queremos saber o elemento que poderá ser necessário para retirar da fila mais tarde. Assim, a razão pela qual temos frente há é uma espécie de um indicador do que é a coisa mais antiga do array. Bem, a coisa mais antiga do array-- em verdade, a única coisa na matriz direita agora-- é 28, que é a matriz localização 0. Então, nós não queremos alterar esse número verde, porque esse é o elemento mais antigo. Em vez disso, queremos mudar o tamanho. Portanto, neste caso, vamos incrementar tamanho 1. 

Agora, um tipo geral da ideia de onde o próximo elemento está indo para ir em uma fila é para adicionar esses dois números juntos, frente e tamanho, e que vai lhe dizer onde o próximo elemento na fila está a ir. Então agora vamos enfileirar outro número. Vamos enfileirar 33. Então 33 vai entrar em matriz localização 0 + 1. Portanto, neste caso, ele vai para entrar em um local da matriz, e agora o tamanho da nossa fila é 2. 

Mais uma vez, nós não estamos mudando a frente da nossa fila, porque 28 é ainda o mais antigo elemento, e nós quer a-- quando finalmente chegar para dequeuing, remoção de elementos a partir desta fila, queremos saber onde o elemento mais antigo é. E assim temos sempre que manter algum indicador de onde é. Então é isso que a 0 está lá para. Isso é o que está lá para frente. 

Vamos em enqueue um elemento a mais, 19. Tenho certeza que você pode adivinhar onde 19 está a ir. Vai entrar em matriz número de posição 2. Isso é 0 + 2. E agora o tamanho da nossa fila é 3. Temos 3 elementos nele. Então, se fôssemos, e nós não vamos para a direita agora, enfileirar outro elemento, ele iria entrar em local da matriz número 3, eo tamanho da nossa fila seria 4. Então, nós temos enfileirado vários elementos agora. Agora vamos começar a removê-los. Vamos desenfileirar-los a partir da fila. 

Assim, semelhante ao pop, que é uma espécie do análogo deste para pilhas, dequeue precisa aceitar uma ponteiro para o queue-- novamente, a menos que seja declarado globalmente. Agora queremos alterar o local de a frente da fila. Este é o lugar onde tipo de vem em jogo, essa variável frente, porque uma vez que remover um elemento, queremos para movê-lo para o próximo elemento mais antigo. 

Então nós queremos diminuir o tamanho da fila, e então nós queremos devolver o valor que foi removido da fila. Mais uma vez, nós não queremos apenas descartá-lo. Nós provavelmente está extraindo lo a partir do queue-- estamos dequeuing-lo porque nos preocupamos com isso. Então, nós queremos esta função para retornar um elemento de dados de valor tipo. Mais uma vez, neste caso, é o valor inteiro. 

Então agora vamos retirar da fila algo. Vamos remover um elemento da fila. Se dissermos int x é igual a & q, comercial q-- mais uma vez que é um ponteiro para este dados q structure-- o elemento vai ser será? Neste caso, uma vez que é um primeiro in, first out estrutura de dados, FIFO, a primeira coisa que dedicou a este fila foi de 28, e portanto, neste caso, nós estamos indo tomar 28 de a fila, não 19, que é o que teríamos feito se isso era uma pilha. Nós vamos levar 28 para fora da fila. 

À semelhança do que fizemos com uma pilha, não estamos, na verdade, vai eliminar 28 a partir da própria fila, nós apenas estamos indo para tipo de fingir que não está lá. Então ele vai ficar lá na memória, mas nós somos apenas vai tipo de ignorá-lo, movendo os outros dois campos de dados Q nosso estrutura. Nós vamos mudar a parte dianteira. Q.front vai agora ser 1, porque essa é agora o elemento mais antigo que temos em nosso fila, porque já removeu 28, que foi o ex-elemento mais antigo. 

E agora, nós queremos mudar o tamanho da fila de dois elementos em vez de três. Agora lembre-se, eu disse mais cedo, quando nós deseja adicionar elementos para a fila, vamos colocá-la em um local matriz que é a soma da frente e tamanho. Portanto, neste caso, ainda estamos colocando ele, o elemento seguinte na fila, no local da matriz 3, e vamos ver isso em um segundo. 

Então, nós temos agora a nossa dequeued primeiro elemento da fila. Vamos fazer de novo. Vamos remover outra elemento da fila. No caso, a corrente mais antigo elemento é um local da matriz. Isso é o que nos diz q.front. Essa caixa verde nos diz que que é o elemento mais antigo. E assim, se tornará x 33. Vamos apenas uma espécie de esquecer 33 que existe na matriz, e vamos dizer que agora, o novo elemento mais antigo na fila está no local da matriz 2, e do tamanho da fila, o número de elementos temos na fila, é 1. Agora vamos enfileirar alguma coisa, e eu tipo de deu este fora um segundo atrás, mas se queremos colocar 40 no fila, onde está 40 indo para ir? Bem, nós estivemos colocando- em q.front mais fila de tamanho, e por isso faz sentido para realmente colocar 40 aqui. Agora note que pelo algum momento, nós vamos para chegar ao fim de nossa matriz dentro de q, mas que desapareceu 28 e 33-- eles são realmente, tecnicamente espaços abertos, certo? E assim, podemos eventually-- essa regra de adicionar aqueles dois together-- podemos, eventualmente, precisa modificação pelo tamanho da capacidade por isso, pode envolver em torno. 

Então, se chegarmos ao elemento número 10, se estamos substituindo-o no elemento número 10, estaríamos realmente colocá-lo em ordem de localização 0. E se nós íamos matriz localização-- me desculpar, se nós adicionamos-los juntos, e chegamos ao número 11 estaria onde teríamos que colocar ele, que não existe no presente array-- ele estaria indo para fora dos limites. Poderíamos mod em 10 e colocá- em que local da matriz 1. Então é assim que as filas de trabalho. Eles estão sempre indo para ir a partir da esquerda para a direita e, possivelmente, envolver em torno. E você sabe que eles são se em tamanho grande, que a caixa vermelha, torna-se igual à capacidade. E assim, depois nós adicionamos 40 para o fila, bem o que precisamos fazer? Bem, o elemento mais antigo na fila é ainda 19, por isso não quer mudar a frente da fila, mas agora temos dois elementos na fila, e por isso queremos aumentar nosso tamanho 1-2. 

Isso é muito bonito isso com trabalhar com filas baseadas em matrizes, e semelhante para empilhar, Há também uma maneira para implementar uma fila como uma lista ligada. Agora, se este tipo de estrutura de dados parece familiar para você, é. Não é uma lista vinculada isoladamente, é uma lista duplamente ligada. E agora, como um aparte, é realmente possível implementar uma fila como uma lista vinculada isoladamente, mas Eu acho que em termos de visualização, ele realmente pode ajudar a visualizar isto como uma lista duplamente ligada. Mas é definitivamente possível fazer isso como uma lista vinculada isoladamente. 

Então vamos dar uma olhada o que isso pode parecer. Se queremos enquue-- agora, estamos novamente a mudança para uma lista ligada modelo baseado aqui. Se queremos enfileirar, queremos para adicionar um novo elemento, bem o que precisamos fazer? Bem, em primeiro lugar, porque estamos adicionando ao fim e a remoção a partir da começando, nós provavelmente querem manter ponteiros para ambos os cabeça ea cauda da lista ligada? Cauda sendo outro termo para o fim da lista ligada, o último elemento da lista ligada. E estes, provavelmente, mais uma vez, ser benéfico para nós se eles são variáveis ​​globais. Mas agora, se queremos adicionar um novo elemento que é que temos de fazer? O que nós apenas [? Malak?] ou dinamicamente alocar o nosso novo nó para nós mesmos. E então, assim como quando nós adicionamos qualquer elemento de uma lista duplamente ligada nós, só tem que classificar de-- esses três últimos passos aqui são apenas tudo sobre como mover o ponteiros na maneira correta de modo que o elemento é adicionado ao a cadeia sem quebrar a cadeia ou fazer algum tipo de erro ou ter algum tipo de acidente acontecer pelo qual acidentalmente órfãos alguns elementos da nossa fila. Aqui está o que isso pode parecer. Queremos adicionar o elemento 10 para a extremidade desta fila. Assim, o elemento mais antigo aqui é representado pela cabeça. Essa é a primeira coisa que colocamos para esta fila hipotético aqui. E cauda, ​​13, é o mais recentemente adicionou elemento. E por isso, se queremos enfileirar 10 em esta fila, queremos colocá-lo depois de 13. E assim vamos dinamicamente atribuir espaço para um novo nó e verificar se há nula para se certificar não temos uma falha na memória. Então nós vamos 10 colocar em que nó, e agora nós precisamos ter cuidado sobre como podemos organizar ponteiros assim que nós não quebrar a cadeia. 

Podemos definir 10 do campo anterior para apontar de volta ao velho cauda, e uma vez que será a '10 nova cauda em algum momento no momento em que todos esses cadeias estão conectados, nada vai vir após 10 agora. E assim 10 do próximo ponteiro irá apontar para null, e, em seguida, depois de se fazer isso, depois de termos ligado 10 para trás para a corrente, podemos tomar a velha cabeça, ou, desculpa me, o velho cauda da fila. O velho final da fila, 13, e fazê-lo apontar a 10. E agora, neste momento, temos enfileirado o número 10 para essa fila. Tudo o que precisamos fazer agora é apenas mover o cauda para apontar para, em vez de 10 a 13. 

Dequeuing é, na verdade, muito semelhantes para avançar a partir de uma pilha que está implementada como uma lista ligada se você já viu o vídeo stacks. Tudo o que precisamos fazer é começar no começando, encontrar o segundo elemento, libertar o primeiro elemento, e depois mover a cabeça para apontar para o segundo elemento. Provavelmente melhor para visualizá-lo apenas para ser mais claro sobre isso. Então aqui está a nossa fila novamente. 12 é o elemento mais antigo em nossa fila, a cabeça. 10 é o elemento mais novo em nossa fila, o nosso rabo. 

E assim, quando nós queremos para retirar da fila um elemento, queremos remover o elemento mais antigo. Então, o que fazemos? Bem, nós definir um ponteiro de passagem que começa na cabeça, e movê-lo para que ele aponta para o segundo elemento desta queue-- algo por dizer trav é igual a trav seta próxima, por exemplo, moveria trav para apontar para lá 15, que, depois de nos retirar da fila 12, ou depois de remover 12, vontade tornar-se o elemento mais velho então. 

Agora temos um poder sobre o primeiro elemento através da cabeça do ponteiro e o segundo elemento através do trav ponteiro. Podemos cabeça agora está livre, e então nós podemos dizer nada vem antes de 15 de anymore. Assim, podemos mudar 15 do anterior ponteiro para apontar para null, e nós apenas mover a cabeça sobre. E lá vamos nós. Agora nós temos com sucesso dequeued 12, e agora nós tem outra fila de 4 elementos. Isso é muito bonito tudo existe a filas, tanto baseada em array e-lista ligada baseado. Eu sou Doug Lloyd. Este é CS 50.