Estruturas de Dados - Fila (Lista Encadeada)

Olá meus caros Alunos hoje nós vamos falar sobre a estrutura de dados fila novamente só que dessa vez nós vamos falar num contexto de implementação utilizando lista encadeada o Outeiro da aula de hoje vai ser primeiramente nós falaríamos sobre a estrutura do nó seguido da definição do tipo abstrato de dados depois nós falaríamos sobre o detalhes de implementação e depois de aplicações dessa nossa estrutura e vamos falar primeiramente sobre a estrutura do nó a estrutura do nova essa é a mesma da aula passada em que nós falamos sobre pilhas nós teremos um objeto do uma

uma stripper node Type para gerar o nosso nó que contém o que ele contém a informação sendo que essa informação vai ser um item Type e um ponteiro para o próximo nó que por sua vez também vai ter um inventário e um ponteiro para o nosso seguimos Então é isso que nós temos aqui Um item Type com a informação e um ponteiro para o próximo não é urgente que a gente tem feito até agora esse itemtype na verdade está sendo um apelido para um caractere e como é a mesma coisa da aula passada nós já

Podemos seguir adiante vamos falar sobre a estrutura de dados aqui a gente tem uma classe e uma classe kill e essa classe aqui só pra vocês saberem a pronúncia correta dessa palavra aqui é kill em aulas anteriores eu tenho falado é o kiwi assim como em kiewit justamente pra ficar mais fácil de entender o que eu estou falando tem vezes que alguns alunos acabam não entendendo algum conceito e sem aulas presenciais Se eu tentar pronunciar essa palavra da maneira correta então eu prefiro pronunciar o ecrã não à venda em um erro aí simplesmente por eu

ter falado algo em você não tenha entendido Mas é interessante saber qual é a pronúncia correta das palavras também além do que elas implementam e vamos continuar aqui aqui a gente tem Construtor e destrutor do jeito que a gente tinha na aula na implementação anterior de fila e aqui a gente tem uns métodos que têm os mesmos nomes os mesmos tipos de retorno e os mesmos tipos de parâmetros na implementação anterior então aqui não tem que mencionar nada não preciso mencionar nada já é o mesmo da da implementação anterior como a mesma semântica aqui embaixo

note tem algumas modificações temos dois contêineres um ponteiro chamado fontes e um ponteiro chamado Year from our se a gente pode traduzir na frente parte da frente EA parte de trás bom então isso quer dizer o quê que a gente ter a um ponteiro para frente da fila tá e a fila vai ser tudo aqui no meio um ponteiro para parte de trás da fila só para a gente saber onde inserir e onde removido bom então vamos mudar apenas a implementação interna porque porque a implementação da interface pública é a mesma da anterior e agora

alguns detalhes de implementação implementar emos como eu já disse uma fila como desista entediada teremos dois ponteiros um front and rear que apontaram para o início e o final da fila respectivamente E é claro que nós queremos inserções e remoções ocorrendo em tempo constantes para ficar semelhante com aquilo que a gente fez com a implementação e ver tudo em outras palavras nós queremos que as nossas Sensações e Emoções independam do número de elementos na estrutura o que em outras palavras também quer dizer que a gente não vai fazer nem Tipo de política dentro da estrutura

para saber onde nós vamos inserir e qual elemento nós vamos remover Mas a temos que obter esses elementos em tempo com estamos Hoje vamos falar sobre Construtor e destrutor aqui como Construtor e destrutor eu vou apenas seguir a ideia de inicializar os ponteiros como nulo por quê Porque eventualmente eu posso utilizar a ideia de nulo como critério de parar em algum laço se eu não tivesse feito essa inicialização Eles teriam and find O que poderia causar aí uma com algum certo problema ao finalizar algum tipo de laço que varre um a lista do início para

o fim e vamos falar agora sobre o destino torno da mesma forma como ocorreu com a pilha na aula passada o destrutor ele não é um simples espelho do Construtor em que no Construtor eu coloco uniu e no destrutor eu coloco deles não aqui eu tenho que me preocupar com as alocações que foram feitas pelo método insert pelo método de inserção e seria o método inclui bom então o que que eu vou fazer eu tenho aqui uma lista encadeada e agora é uma fila e Eu Tenho que varrer essa desista encadeada do início até o

fim então aqui a minha lista aqui é o frontes tá apontando para o primeiro elemento e aqui no final eu vou ter o rir eu apontando para o último elemento como o primeiro elemento a conta para o segundo segundo aponta para o terceiro e assim por diante então eu vou começar do Frozen então no front eu sei que eu tenho que apagar esse elemento entretanto eu sei que eu tenho que ao apagar garantir que eu sei quem é o próximo não posso apagar antes de salvar esse ponteiro aqui então o que é que eu faço

eu criei um ponteiro temporário que seria o tempo e PTR Monteiro temporário para apontar para este elemento daí eu atualizo prontos para plantar próximo elemento E aí sim utilizando esse ponteiro temporário eu eu desloca esse nome é exatamente isso que eu faço aqui um ponteiro temporária apontando para Fontes depois eu atualizo offrons para apontar para o próximo elemento e depois eu apago o não apaga o ponteiro temporário depois eu desalocar a memória apontada pelo ponteiro temporário e ao final de tudo isso é o final desse lá na sua aqui o frontes ele vai estar nulo

por quê Porque ele seguiu até o fim no final contava para nulo só que entretanto rir ele tá apontando para uma região de memória que já foi deslocada só para não ter nenhum erro caso o usuário ver o que se diz essa estrutura o Twitter and on and on a verificação de cheio ou de vasinho Vamos começar com a verificação de vazio vamos lá de aparecimento tudo aqui embaixo eu poderia checar seu Frozen é igual a Lulu se eu vim era igual a nulo se o front eu ir sem igual a lua na verdade se

o front por diferentes por igual a nulo e o river full se o front com diferente de nulo mas o ponteiro para trás for igual a Lulu aí já teria um certo problema que aconteceu e se não pode acontecer não deveria acontecer então pô decisão mesmo eu coloquei se front for igual anulo eu vou assumir Por conseguinte que eu ir também é igual aluno e que a pilha que a fila estava sendo e agora para verificar se a fila está cheia de novo o mesmo argumento que eu fiz na aula passada você pode inserir Quantos

elementos você quiser você não está definido por exemplo como a gente fez com vetor um espaço apenas de cem elementos se não definiu isso a priori entra tanto pode ocorrer de você ficar inserindo inserindo inserido em algum erro de memória ocorrer por exemplo não consigo inserir mais um cima próximo a haldis ou qualquer outro tipo de erro se algum erro ocorrer que que eu vou interpretar aqui que a filha está cheia não conseguia local uma nova memória Então é isso que essa linha de código aqui está fazendo eu declaro primeiro antes do método traz antes

do Tri quer dizer da palavra reservada traz um novo novo site tento alocar e logo em seguida deleto Se eu conseguir alocar e deletar significa me dá consigo colocar mais um então retorno falso por quê Porque eu tô dizendo ainda não está cheia aqui dentro desse Troy E aí ela fica mais ou então aí fora você consegue se eu não conseguir alocar mais uma aqui o que que eu faço eu retorno outro dizendo Olha eu não consegui alocar mais um Então vou interpretar aqui a fila Está cheio vai ser melhor para todo mundo assim basicamente

é isso que essa linha de código está dizendo e vamos ver agora a inserção de elementos para inserir um novo elemento que a gente tem que imaginar a gente tem que imaginar que a gente insere no final o interese a gente não mexe no ponteiro que está apontando para frente é certo em uma situação que eu vou falar agora mas vamos pensar no caso basta a gente tem um ponteiro aqui apontando para o fim Lilian e a gente tem um ponteiro aqui apontando para frente para inserir um novo não O que que a gente passa

a gente cria um novo não em qualquer lugar da memória por exemplo eu vou criar um novo Jockey essa ideia está sendo feita bem aqui eu tenho um novo nó E eu coloquei a informação o que veio por parâmetro que a oitentalha dentro desse novo vem aqui eu fiz esse nó apontar para quem apontava Para nulo por quê Porque ele vai ser o último da fila então o último dado pela sempre aponta para tu sabe vamos assumir que existe realmente uma fila aqui ou seja vamos assumir primeiramente que eu não vou entrar nesse e que

eu vou entrar nesse elsie aqui então existe realmente uma fila se existe realmente uma fila o que que eu faria eu faria o ponteiro O Henrique está contando Ou seja eu faria nesse elemento aqui que eu ia tá contando apontar para esse novo Nokia eu acabei de gerar Então vou pegar esse Winner next Back e apontar ele para cá E é isso que eu estou fazendo nessa Dinha de código bem aqui e daí o quê que eu preciso fazer eu preciso fazer ou ir está bem aqui apontando para esse elemento que agora não é mais

o último eu preciso fazer ele apontar para cá então coloca aqui eu ir é igual Are You Hold On é só que você deve se perguntar tá mas esse esse aqui que eu decidi ignorar bem esse esse aqui é quando a fila está vazia ou estão frontes e ouvir eles estão apontando para nulo eu sei eu já Criei um novo elemento tá o front o vídeo eu estou contando para nulo tanto frontcontroller vão ter que apontar para cá se o igual a Lulu ou seja essa situação está todo mundo apontando para Lulú eu já pego

o front e já faço era contar para cá porque porque eu sei que o front também tá nula que ele está vazia porque eu não coloquei o igual a new world aqui dentro você vai se perguntar você coloquei um Frozen porque fora desse F eu já tinha um código que dizia our é igual a Nilde então não vou colocar de novo então seu irmão anula colorfront é igual a new 2 japonês para o nosso eu acabei de zerar por quê Porque o único elemento da fila é igual em 12 também é vai ser perguntar para

cá tem um único elemento da fila Então se está vazio eu posso os dois ponteiros apontaram porque eu acabei de gerar se não está vazio então eu sigo a ideia geral eu faço quem quem era o último eu posso apontar para o novo e agora o ponteiro quero ouvir vai apontar para o outro é essa é a ideia dessa linha de código Aqui está bem De acordo com o que a gente já aprendeu de fila e agora para remover um elemento bem para remover o elemento a gente utiliza o ponteiro que estava apontando para Fontes

o primeiro elemento a gente ignora todo o resto aqui então vamos lá tem um ponteiro front aqui esse front depois ele vai ter que apontar para o próximo nó eu vou ter que deslocar esse nó bem aqui então o que que eu vou fazer vou criar um tempo e PTR para apontar para esse noc depois o teu salvo essa região de memória que um ponteiro para ela para não ter vazamento de memória então eu coloco node Type* tempo e PTR um ponteiro para essa região aqui 30 e PT é igual a Fronte tá o item

Type vai ser um front. Inferior ou seja antes de apagar o salvo essa informação o piru ela para alguma outra região de memória e essa outra região de memória eu vou conseguir acessar utilizando a variável Y Então já salvei o item que eu vou dar no return ao final do próprio e daí o que é que eu faço primeiramente eu faço front que está apontando para cá apontar para o próximo elemento então coloco front é igual a Fronte setinha next setinha lembrando é porque o fronto Na verdade é um ponteiro para um ponteiro para uma

estrutura bom então para acessar o campo dessa estrutura usa certinho não uso ponto o ponto eu só usaria se eu tivesse uma variável daquela classe ou daquela Street outra crítico E se eu fazer isso fazer o front agora fonte next eu perceber que o front acabou apontando para nulo significa que eu já estava no último elemento então eu removi o último elemento então front passou apontar para nulo e eu só tenho que fazer o que eu só tenho que fazer o Ranger rir apontar para nulo também porque porque eu ia então Estava contando para esse

elemento aqui que eu acabei de remover como eu acabei de amor eu não quero que eu ia ficar apontando para ele porque ele vai apontar para nulo Então coloca o ir igual a novo aqui ótimo já fiz tudo era isso que eu precisava fazer o quê que eu tenho que fazer agora simplesmente desalocar essa memória e depois retornar o item para o usuário questionou essa função que a Justamente que eu fiz aqui de Elite tempo e PTR e eu return Python eu espero que tenha ficado Claro todas as linhas desse código aqui e imprimindo a

desista na saída padrão que que eu vou fazer simplesmente um Lion que vai do início da minha lista até o final da minha lista de um por um e até percebeu alguém aqui apontou para mim então vou colocar um tempo e PTR para apontar para o início e esse tempo e PTR vai ficar se atualizando uma ideia muito parecida como da pilha Então tá aqui o tempo é PTR eu imprimi a informação na tela e daí atualiza para o tempo e PTR seu próximo é mesmo E aí oi e daí com essa nova estrutura eu

posso utilizar o mesmo código teus de de teste da estrutura anterior ou seja posso pedir para o usuário colocar alguns caracteres daí quando o usuário coloca os caracteres eu coloco na fila quando o usuário de um barra a m ou na fila estiver cheia eu vou dizer eu vou desenfileirar todo mundo e colocar o resultado na saída padrão então esse código que funcionava com a nossa outra versão de fila vai funcionar sem nenhuma modificação com essa nossa nova versão depilo Hoje vamos falar sobre aplicações da estrutura a fila tem várias aplicações eu já dei o

exemplo do documento enviado para impressão só o documento de Pedro para enviar do antes do Di Paulo Então vai ter que ser impresso antes de Paulo não é bem claro o que a gente pode fazer com uma fila a gente utilizar ela toda vez que a gente quer um acesso justo alguma coisa compartilhada é só que plano aula de hoje eu vou utilizar uma fila para verificar se uma determinada stringhi é um padron então quê que é um patinho de basicamente é uma string que a leitura de trás para frente e de frente para trás

é exatamente a mesma por exemplo o ovo se você ler corro da frente para trás e de trás para frente vai ser a mesma palavra eu coloquei missa e assim isso aí assim se você ler de trás para frente vai de frente para trás vai ser a mesma coisa arara é outra palavra a palavra um desses aqui ela e não é para dentro URSS se você ler de trás para frente de frente para trás vai notar não é a mesma palavra Abrakadabra também não é se você ler de trás para frente de frente para trás

de gravar a bradar cabra que não é um paninho Como é o código que a gente vai gerar com a verificação mas tende a página o nosso código ele vai utilizar tanto fila quanto pilha o que que eu vou fazer eu vou fazer o seguinte toda vez que o usuário colocar um caractere eu vou impedir ar o caracter E enfileirar também o caractere enquanto existirem caracteres sendo adicionados pelo usuário eu vou conta de serem caracteres sendo adicionados pelos vários eu vou tanto empilhar quanto enfileirar Então sempre que tiver um caracter eu coloco na pilha e

na fila que a pilha aqui é a fila ele colocou e vai colocar o anúncio Ah tá Se a filha se o número de caracteres for vazio o que que eu vou fazer eu vou desempilhar e desisti leirar ao mesmo tempo então se eu for dizem pedir a ideia de peneirar a pilha ela vai ser desempilha de trás para frente por ter porque o último a entrar vai ser o primeiro a sair eu vou comparar com que saiu da fila que foi o primeiro a entrar Ou seja eu vou comparar o último a entrar com

o primeiro a entrar e vou verificar se eles são iguais Se eles forem iguais eu continuo verificando Se eles forem diferentes eu já sei que eu posso parar de verificar por quê Porque eu já sei que não é um página bom então ideia vai ser isso primeiro eu coloco tudo na fila e entrou na pilha e os caracteres depois eu tiro da pilha e tiro da fila e os caracteres tem que ser iguais o que sai da pide aí o que sai da fila sendo que na pilha tá saindo de trás para frente na fila

tá saindo de frente para trás então eu comparo Se eles forem iguais até o terminar ou seja até a pilha EA filha estarem vazias eu sei que eu tenho um padrão é tão enquanto a pilha EA lista não estiverem vazias eu dizem piru e desinflar e verifique os caracteres são iguais se forem caracteres iguais ou continuo a minha busca tentando novos elementos novos novos caracteres na pilha e na fila ao mesmo tempo me desculpa eu coloquei Vista que aqui na verdade é fila então na pilha e na fila Então vou tentar será eu fico nesse

laço aqui se eu perceber que algum momento characteres não são iguais então ele não é palíndromo e se outros eu terminar tudo isso daqui e a pilha EA fila estiverem vazias eu sei que ela para dentro ó e vamos ver aqui o código código Ele é bem simples é a ideia de ficar pedindo para o usuário novos caracteres Então eu tenho uma variável booleana que vai me dizer se é padrinho do meu não por enquanto eu vou inicializar ela como como tu para dizer olha ela vai ser padrinho dorme até que se prove o contrário

Então eu eu inicializo Art Tech EA Bio creme com ela e coloca o variáveis o alcance para os caracteres o que vai entrar faz seu carácter aqui vai ser inserido pelo usuário eu vou colocar na variável caractere eu vou o caracter que sai da pilha vai ser Tec tor e o caracter que sai da fila vai ser qual é o filme tio tchau tchau bom Então primeiramente primeiro passo usuário está inserindo caracteres de um por um o que é que eu faço pega o caracter coloco na pilha dando um peixe coloco na fila dando incrível

até o usuário até Osório tá em barra e me bem aqui e enquanto for palindrome ou seja não provei que não é para dentro e enquanto a fila estiver não estiver vazia A Fila EA pilha vão ter a mesma quantidade de elementos Isso é fato porque porque eu tô empilhando e enfileirando ao mesmo tempo então não tem como as treinamentos diferentes aqui eu decidi Só checar utilizando as pílulas Mas você poderia ter colocado ne certo aqui e daria no mesmo que que eu faço dentro desse Lion eu retiro da pilha Tô dando um Pop Retiro

da fila dando de Queen verifique Os seres são iguais Os seres são iguais eu não faço nada porque porque eu só quero provar que eles são diferentes Se eles forem que eu só quero provar que não é para vidro Se eles forem diferentes Eu sei que não é para vidro se eu sei que não é pode ir dormir eu já digo pagto uma igual a Fox o que indica que eu vou sair do laço já que se lascou uma das condições é ser pai livro ele vai sair até ser laço quando ele está em desse

lá só tenho que entender porque ele saiu do laço se ele saiu do laço porque o palindrome era igual após ou se ele saiu do laço Por que acabaram os caracteres E se ele saiu do laço porque o paninho dormir era igual a false significa que eu só tenho que dizer a restringir não é para mim Dom já aviso aí para pessoa que invocou o código se ele saiu do laço pooh-pooh por esse segundo motivo aqui já tinha ficado vazia Então o senhor eu não consegui provar que não era para vidro se eu não conseguir

provar que não era para mim dormir então é para livro e eu escrevo aqui na saída stringhi é pagpronto e eu gosto desse exemplo ele é um exemplo bem simplificado mas ele é interessante por ele utilizar tanto pilha quanto fila é um exemplo do que a gente pode fazer combinando estruturas de dados diferentes E aí E é isso que eu tinha para falar na aula de hoje a agradeço por terem assistido essa aula até aqui caso não tenha ficado entendido alguma coisa recomendo que você só Éden o vídeo novamente e a olhar o vídeo novamente

tem que ser a as dúvidas não esqueçam que esse vídeo ele vem acompanhado no material de apoio do código Todo Esse vídeo foi tem o os códigos estão slides também estão no arquivo justamente para você ir lá no arquivo colocar as gemas mais e depois executar o arquivo de vocês tentem fazer modificação até brincar um pouco a melhor maneira Como já disse de aprender é tô fazendo códigos e executando um forte abraço que a gente se vê na próxima a E aí [Música]