Filas | Estruturas de Dados #8

Подписаться 198 тыс.

Просмотров 13 тыс.

50% 1

O que é uma Fila? Como implementar uma Fila? Para que serve esta estrutura de dados?
Nesse vídeo, apresentamos e implementamos uma estrutura de dados chamada Fila. Prosseguimos com os conceitos aprendidos com as Listas em alocação Encadeada e as Pilhas, nos focando na implementação de uma nova política de acesso.
Uma fila é uma estrutura de dados cuja política de acesso é conhecida pela sigla em inglês FIFO (First In First Out), que significa "primeiro a chegar, primeiro a sair". É uma ideia intuitiva de pensar, pois replica no computador o que já estamos habituados a chamar de fila no dia a dia. Por exemplo, se alguém chega primeiro na fila de um banco, está pessoa deve ser a primeira a ser atendida. No vídeo, explicamos detalhadamente o conceito e funcionamento das filas e implementamos uma fila com alocação de memória encadeada utilizando a linguagem de programação Python. Filas são estrutura de dados estudadas com frequência em cursos de graduação de computação como Ciência da Computação, Engenharia de Computação e Análise e Desenvolvimento de Sistemas em uma disciplina chamada Estrutura de Dados (que as vezes é unida a outra denominada Algoritmos).
Em todas as estruturas de dados estudadas, você deve ter atenção à complexidade da busca, inserção e remoção na estrutura. Em uma fila, os métodos de inserção e remoção recebem os nomes especiais de push e pop, respectivamente.
💯 Aprenda a programar em Python do Jeito Certo: go.pgdinamica.com/pythondojeit...
📌 Código do vídeo: github.com/python-cafe/data_s...
🔥 Faça parte da comunidade gratuita Programação Mais Dinâmica: bit.ly/pgsparkle (baixe o app e entre na comunidade)
▶️ Acompanhe o curso de estrutura de dados nesta playlist: • Estrutura de Dados
📚 Livros de Algoritmos e Estruturas de Dados: amzn.to/3d5wK4m
📚 Livros recomendados de Data Science: amzn.to/2XZyxUr
🎥 SetUp - Equipamentos: amzn.to/37Cg3N2
🟣 Canal na Twitch para lives: / pgdinamica
🟦 Canal do Telegram para receber os vídeos: t.me/joinchat/AAAAAFaoNgZTMRv...
✉️ E-mails:
- Propostas comerciais: pgdinamica@brunch.ag
- Demais assuntos: contato@programacaodinamica.com.br
👩🏾‍💻👨🏾‍💻 Confira mais conteúdo em nosso blog: blog.programacaodinamica.com.br
🔥 Faça parte da comunidade gratuita Programação Mais Dinâmica: bit.ly/pgsparkle (baixe o app e entre na comunidade)
📸 Nos siga no Instagram: / pgdinamica
📸 @kizzy_terra @hallpaz
🐦 Nos siga no Twitter: / pgdinamica
🐦 @kizzy_terra @hallpaz
* Curta a Programação Dinâmica no facebook: pgdinamica
* Nosso repositório no Github: github.com/programacaodinamica
* Confira o nosso Medium: medium.com/programacaodinamica
* Confira os artigos no Python Café: pythoncafe.com.br
🥰 Se você gosta do nosso trabalho e acha relevante a nossa atuação no RU-vid, considere nos apoiar se tornando membro do canal: ru-vid.com...
▶️ Se você não tem experiência com Python, mas gostaria de aprender a programar e desenvolver uma base sólida de programação usando esta linguagem, confira o nosso curso Python do Jeito Certo: vai.pgdinamica.com/pjc-eda

Опубликовано:

19 сен 2018

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 51

@wallacesantos0 5 лет назад

"Sou hallison paz" Finalmente consegui entender o que vc fala no início do vídeo!! kkkk Eu não sei se nos outros aparecia o nome ali no canto, mas eu nunca conseguia entender. Sempre entendia algo como "suave são pais" kkkk

@pgdinamica 5 лет назад

E olha que nesse vídeo eu já tinha alguma experiência gravando xD

@jairrocha772 3 года назад

Valeu, Hallison! O Programação Dinâmica tá me ajudando um bocado. Você e a Kizy arrasam!

@pgdinamica 3 года назад

Que ótimo! Muito obrigado!

@herculessouza1861 5 лет назад

Top mano..só conteúdo de qualidade.. obrigado!!!

@pgdinamica 5 лет назад

Muito obrigado, Hercules!

@TheAndozio 4 года назад

Obrigado cara. Explicou bem, e clareou bastante. abraços.

@pgdinamica 4 года назад

Valeu, Caio! Obrigado! Bons estudos 🖖🏾

@danielcampos4756 3 года назад

Brabo mano. Canal muito bom

@pgdinamica 3 года назад

Muito obrigado 🙂🤙🏾

@marcosrodrigodutra6640 4 года назад

Parabéns Hallison! Seu conteúdo tem me ajudado muito em meus estudos.

@pgdinamica 4 года назад

Valeu, Marcos!

@mikewescleyrodriguescorreia Год назад

Nmrl esses seus vídeos são d+. Assisti toda a playlist de Estruturas de Dados, vi sobre árvores e td mais, esse era o ultimo video que faltava pra terminar td, e me ajudou pra caramba! Você vai fazer mais videos de estruturas de dados? Falar sobre grafos, tabela hash?

@pgdinamica Год назад

Tô querendo voltar em agosto 😉

@user-ul7ec6bn7r Год назад

Ótimo conteúdo

@pgdinamica Год назад

Valeu!

@daniellealmeida2673 3 года назад

Hallison, você explica muito bem! Parabéns pelo canal, estou aprendendo muito! Logo estarei vendo os vídeos da Kizy também.

@pgdinamica 3 года назад

Obrigado, Danielle! Bons estudos!

@guilhermeespinati1718 3 года назад

Teu Canal é Massa Mano.. Parabens

@pgdinamica 3 года назад

Obrigado! 🙌🏾

@ahahhasaasasas3274 5 лет назад

Muito foda, tu é demais ^-^

@pgdinamica 5 лет назад

Muito obrigado :D

@jeffersonanalisedesistema7680 2 года назад

O Allison é dez, seus videos são tops, melhores que dos professores da faculdade. O problema é que a aula atinge somente um tipo de publico devido o conteudo ser em ingles. Pessoalmente compreendendo de boa, porque ja ha muito tempo estudo informatica, desde a epoca do DOS, inclusivel venho do COBOL. Tenho pena daqueles que estão começando agora, o conteudo fica bem mais dificil. Por isso, podia trazer conteudos com a lingua nativa - portugues . Com essa sua ditatica e mostrando todos es exemplos em portugues, voce ficaria insuperavel. termos como frist, next, last; poderia subistir por primeiro, fila, proximo, ultimo. So consegui compreender o funcionamento do pyton, quanto comecei estudar tutoriais e exemplos em portugues: self.inicio, self.fim. def enfileirar, etc..

@pgdinamica 2 года назад

Compreendo, mas você não vai encontrar nenhuma implementação prática em português. Da mesma forma que precisa aprender if, else, for, while…precisará importar stack, queue etc e usar seus métodos em inglês. A aula tem uma parte teórica com toda explicação dos nomes em português e uma parte prática em que esses nomes aparecem novamente, desta vez em inglês. Havendo dúvidas quanto à tradução, basta perguntar 🙋🏾‍♂️. Se você quer dominar este conteúdo, deve focar em entender a ideia por trás de cada estrutura de dados e implementar seu próprio código a partir dessas ideias (em qualquer linguagem). Este também não é um tópico que julgo adequado para quem está tendo o primeiro contato com programação. Na playlist “Introdução ao Python por Projetos”, o código é o escrito em português também.

@englishhighlights9327 Год назад

4 anos depois, um bicho de Engenharia da Computação está assistindo seu vídeo para entender esse conceito. Abraço!

@pgdinamica Год назад

Bons estudos!

@kizzy_terra 5 лет назад

👏🏾👏🏾👏🏾👏🏾

@pgdinamica 3 года назад

💯💯

@guilhermegc240 Год назад

O home é bão 😃

@pgdinamica Год назад

Valeu!

@fabriciolopees 3 месяца назад

Olá! Sei que já tem um tempo o vídeo, mas gostaria de saber como é possível armazenar mais do que três valores na pilha e na fila, sendo que as únicas variáveis são: first, next e last? Se cada variável só pode armazenar um valor, sendo assim, assim que adicionar mais que três valores, por exemplo 5 valores, os 2 últimos valores inseridos (exceto o primeiro) pela lógica deveriam serem perdidos, não?

@leandrosoares1663 Год назад

Olá Hallison, tudo bem? Já assisti e implementei juntamente com vc a lista encadeada, pilha e fila. Contudo mesmo debugando o código ainda não consegui entender muito bem a logica por trás do ponteiro Node. Como ele caminha na lista utilizando o .next. Poderia me ajudar a entender?

@raniel0511 3 года назад

Assistido✔️

@pgdinamica 3 года назад

😊

@oznidahora1630 4 года назад

Muito bom seu vídeo Hallison! Me tira uma dúvida... Tinha uma atividade da Faculdade que precisava resolver utilizando esse conceito de Filas. Resolvi de uma forma, mas fui dar pesquisada e encontrei seu vídeo com uma solução totalmente diferente. Então queria saber de vc, qual a diferença/vantagem/desvantagem entre a solução do seu vídeo utilizando o módulo Queue para a solução abaixo: fila = [] print("Funções: inserir() mostrar_fila() remover()") def inserir(): print("Para finalizar digite (sair)") while True: elemento = str(input("Novo elemento: ")) if elemento == "sair": break fila.append(elemento) def mostrar_fila(): if fila.__len__() == 0: print("Lista vazia! Insira elementos.") return for elemento in fila: print(elemento, end=" ") print(f" A fila tem {fila.__len__()} elementos.") print(f"O primeiro elemento é o {fila[0]}. O último elemento é o {fila[-1]}") def remover(): if fila.__len__() == 0: print("A lista já está vazia!") return fila.pop(0) print(fila, end=" ")

@pgdinamica 4 года назад

A diferença mais notória é eficiência das operações, mas só será percebida com muitos elementos. A fila realiza inserção e remoção em O(1), complexidade constante. Se você utilizar uma lista do Python na função de fila, como no exemplo digitado, você consegue inserir em O(1) ao final da lista, mas a remoção do início com "pop(0)" acontece em O(n). Como a lista não pode ter "buracos", a remoção do primeiro elemento implica em mover todos os outros uma posição a frente, então custa mais caro. Se você comparar com a fila de verdade da biblioteca padrão do Python, pode ser que haja, ainda, alguma diferença no tratamento de concorrência, algo que é importante considerar se o seu programa precisa acessar a estrutura a partir de múltiplas threads diferentes. Nós não estamos tratando problemas de concorrência no vídeo, por ser um assunto mais avançado que exigira uma atenção especial (as listas comuns do Python também não tratam).

@henriquemoreira7950 3 года назад

Muito bom Parabéns!! Mas no algoritmo do pop não seria necessário setar o valor para self.last como nulo caso estivesse removendo o último valor da fila?

@pgdinamica 3 года назад

Sim, você tem razão 💯. Tá corrigido no código, mas esqueci de adicionar à descrição, obrigado! O código está aqui: github.com/python-cafe/data_structures/blob/master/fila/queue.py

@StanKiew Год назад

Precisava de uma fila em alocação contígua, to estudando na Estácio e a maioria dos códigos deles não funciona

@wsricardo23 2 года назад

Estava na dúvida sobre como verificar se meu algoritmo de fato está correto e me deparei com termos como "corretude" e "invariante de laço". Fiquei pensando como eu poderia de fato verificar se meu algoritmo está correto e retorna o resultado esperado para o qual o algoritmo foi projetado pra um dado problema.

@pgdinamica 2 года назад

Você precisa entender o que é uma prova matemática para provar a corretude de um algoritmo. Um algoritmo *é* um procedimento matemático - inclusive, no ensino fundamental, temos contato com o algoritmo de Euclides para determinação do Máximo Divisor Comum (MDC) entre dois números. Muitos desses algoritmos que estudamos possuem uma estrutura de repetição (laço), até porque um dos grandes interesses deste estudo é medir o quanto de recursos precisamos em relação ao tamanho do dado que iremos processar. Você não sabe quantas vezes um laço irá executar a priori e você deseja que o algoritmo dê a resposta correta para todos os casos, independentemente de serem 1 iteração ou 1 bilhão de iterações. Por isso, é importante identificar elementos *invariantes* ao longo dessas repetições, padrões que vão lhe permitir concluir que o algoritmo está caminhando (tecnicamente convergindo) para a resposta correta. Livros com um embasamento mais matemático como o Cormen costumam abordar isso.

@wsricardo23 2 года назад

@@pgdinamica exato. Estava com dúvida nisto principalmente como identificar o "invariavelmente de laço"

@poseidon8036 3 года назад

Um erro que pode passar desapercebido durante o vídeo é quando a fila é preenchida e depois esvaziada, o valor da variável last não fica None, mas sim o último elemento inserido.

@pgdinamica 3 года назад

Sim, faltou tratar isso no vídeo. No código disponibilizado, tá corrigido e com um comentário :)

@amigopython8254 3 года назад

alguém pode me da uma ajuda no URI 3005 junger Uma jardineiro tem um monte de pedaços de granito em forma de paralelepípedo e quer formar uma escultura empilhando dois desses blocos. Ele pode virar convenientemente os blocos, mas só pode empilhar os dois blocos se a face do bloco que vai ficar em baixo tiver ambas as dimensões maiores que as da face que será empilhada. Faça um programa para ajudá-lo nessa tarefa. Entrada A entrada consiste de uma série de testes. A primeira linha contém um único inteiro indicando o número n (1 ≤ n ≤ 20) de casos de testes. A seguir vêm n linhas contendo, cada uma, um caso de teste. Cada caso de teste se compõe de 6 inteiros: os três primeiros são as dimensões do primeiro bloco e, as três últimas, as dimensões do segundo bloco. Saída Para cada caso de teste imprima, em uma linha, um inteiro de 0 a 3, com o seguinte significado: 0, se nenhum bloco pode ser empilhado sobre o outro. 1, se apenas o primeiro bloco pode ser empilhado sobre o segundo. 2, se apenas o segundo bloco pode ser empilhado sobre o primeiro. 3, Se cada bloco pode ser convenientemente empilhado sobre o outro. tentei fazer assim: # teste n = int(input()) bloco1 = [] bloco2 = [] cont_0 = 0 cont_1 = 0 cont_2 = 0 if 1

@Lowcarb_receitas01 3 года назад

Alguém pode me ajudar tenho uma atividade de algoritmos e não tou conseguindo fazer?

@ricardogomesdemelo2347 Год назад

o que é O[n] ? Por exemplo: O[1], O[2]

@pgdinamica Год назад

Tá explicado aqui: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-UQzCFkRbIrE.html mas recomendo ver este outro primeiro ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-KVlGx-9CuO4.html pra aprender desde o começo.