Neste resumo irei abordar os seguintes tópicos:
Introdução:
- Conceito geral de fila
- Fila circular
- Fila de prioridade
Conceito Geral:
Hoje irei abordar sobre a fila. Essa estrutura de dados é muito parecida com a fila que temos na vida real. Em uma fila, o primeiro a chegar é o primeiro a ser atendido e o último a chegar, será o último a sair. Com isso, temos o principal conceito de uma fila FIFO(first-in-first-out), ou seja, o primeiro elemento a ser inserido, será o primeiro elemento a ser removido.
Para inserir um item nessa estrutura, nós iremos enfileirar, o que significa que iremos adicionar o dado no final da fila. Para remover, iremos desenfileirar, assim, retiramos o elemento do início do vetor. Por fim, para visualizarmos um elemento, nós iremos ver o primeiro da fila.
Fila Circular:
Irei abordar um conceito muito importante nessa estrutura que é a fila circular. Como vimos em vetores ordenados e vetores não ordenados, se excluirmos um dado no início ou no meio do vetor, nós iremos remanejar todos os itens posteriores para que não haja nenhuma casa vazia, com essa imagem ficará fácil de visualizar:
Essa abordagem aumenta um número n de passos de acordo com o tamanho de dados do vetor. A fila circular faz com que esse remanejamento não aconteça, melhorando, dessa maneira, a performance da aplicação. Ela funciona da seguinte forma: existem dois ponteiros, um que representa o início da fila e outro que representa o final, quando entra um elemento novo, o ponteiro do final da fila muda de posição e quando sai um elemento, o ponteiro de início da fila também muda de posição. Imagina uma fila de banco, só que quando você entra na sua posição da fila você não pode mais se mover, somente se for para sair. Vamos supor que tem uma fila montada e que ninguém foi atendido e assim que você chega a pessoa que era última te entrega a placa que identifica que agora você é o último. A primeira pessoa quando for atendida ninguém sai do lugar, mas ela passa a plaquinha para o segundo da fila para informar que o segundo agora é o primeiro. Quando chegar uma próxima pessoa, ela vai para o lugar vazio, que é onde estava o primeiro, assim, você entrega a placa de último lugar para ela.
Observe na imagem para facilitar a visualização:
O número 6 é o primeiro da fila e o 5 é o último. Após isso chega o número 7 que recebe a plaquinha do último da fila, o número 6 sai da fila e quando chegar o número 1, este ocupa a casa que o 6 deixou, mas recebe a placa de último da fila e os dados irão circulando entre as posições.
Quando utilizamos as filas normais, o Big-O será linear O(n), mas quando utilizamos as filas circulares o Big-O será constante. Isso faz com que as filas circulares tenham um excelente desempenho, quando comparamos com as demais estruturas.
Irei contextualizar com Javascript e Python:
Com JS, inserimos os dados em um array com o push( ), pois ele sempre será inserido no final da fila. Para excluirmos um dado, utilizamos o método de array shift( ). E para a pesquisa é só pegar o primeiro item, array[0]. Lembrando que essa ideia de fila que estou passando é uma fila comum e não circular.
Para realizarmos algoritmos com filas circulares, podemos fazer por meio de classes ou funções. Segue um exemplo de um algoritmo circular feito em python:
Fila de prioridade
Neste tipo de estrutura, os itens são ordenados por valor-chave, em que os elementos com o valor alto ou baixo (depende de como será definido), terão prioridade na fila. Vamos supor que quanto menor o número da chave, mais será a prioridade. Dessa maneira, se temos um array com valores [1,5,10,15,24,30] e entrar o item com chave número 3, ele ficará na segunda posição [1, 3, 5, 10, 15, 24, 30]. Pensa nos grupos prioritários em uma fila de mercado, banco e etc.
Veja este outro exemplo para ficar mais claro:
Deixarei um algoritmo feito em python que representa uma fila de prioridade:
Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!
Este resumo é baseados no curso: Estruturas de dados e algoritmos em python
Top comments (0)