Um guia para iniciantes para entender as filas e as filas prioritárias

Como programador, você trabalhará com diferentes estruturas de dados, dependendo do escopo de seus projetos. Um desses conceitos é uma estrutura de dados de fila; as filas são essenciais para os alunos e são usadas em muitos algoritmos importantes. Como as filas, as filas prioritárias compartilham um conceito semelhante, mas têm algumas diferenças fundamentais.

Continue lendo para entender as filas e as filas prioritárias.

O que é uma fila?

Uma fila é uma estrutura de dados simples que possui uma variedade de aplicativos em projetos de codificação da vida real. As estruturas de dados são inerentemente abstratas, mas por uma questão de simplicidade, imaginamos que uma estrutura de dados de fila tem uma forma linear com duas extremidades diferentes.

Em termos de complexidade de tempo, uma fila permite a inserção (enfileiramento) e exclusão (dequeue) no tempo O (1). Devido à sua eficiência assintótica, as filas são eficientes para grandes conjuntos de dados. As filas são primeiro a entrar, primeiro a sair (FIFO) por natureza, o que significa que um item de dados inserido primeiro será acessado primeiro. Em contraste, as pilhas têm uma natureza último a entrar, primeiro a sair (LIFO) e têm apenas uma extremidade aberta.

Imagine uma fila de ingressos em um cinema; cada novo cliente que chega entra na fila em uma extremidade. Um por um, cada cliente adquire um bilhete e sai da fila pela frente. A estrutura de dados da fila funciona exatamente como qualquer fila do mundo real, e os dados são inseridos (enfileirados) em uma extremidade e removidos (desenfileirados) na outra. Agora você pode entender o motivo de as filas seguirem uma metodologia FIFO.

Uma fila tem muitos aplicativos de codificação da vida real. É mais comumente usado em aplicativos onde os dados não precisam ser processados ​​imediatamente, mas em uma ordem FIFO. Agendamento de disco, transferência assíncrona de dados, semáforos são alguns aplicativos típicos. Tarefas de agendamento por ordem de chegada, como spool de impressão ou buffers de dispositivo de entrada, também usam uma fila.

O que é uma fila prioritária?

Uma fila prioritária é semelhante a uma fila, mas possui propriedades adicionais. Quando um elemento de dados é enfileirado na fila de prioridade, ele recebe um número de prioridade. Em contraste com o desenfileiramento de uma fila padrão, os elementos de dados com alta prioridade são desenfileirados antes dos elementos de dados com baixa prioridade. A prioridade substitui a ordem de chegada em uma fila de prioridade, razão pela qual as filas de prioridade não têm uma natureza FIFO consistente.

Relacionado: Algoritmos que todo programador deve saber

Os programadores podem implementar uma fila de prioridade de várias maneiras. Uma implementação direta é usar uma matriz com um item de dados de estrutura / classe, e o item de dados conterá a prioridade de cada elemento de dados e os próprios dados. Outra implementação de fila de prioridade primitiva é usar uma lista vinculada. As filas prioritárias implementadas por meio de listas vinculadas são funcionais, mas não ideais devido ao seu desempenho.

Você pode implementar uma fila de prioridade melhor com um heap. Se você se lembrar, os heaps binários fornecem o elemento máximo ou mínimo no tempo 0 (1) e a inserção leva apenas o tempo 0 (logN). Com a ajuda de heaps, as filas prioritárias oferecem um melhor desempenho assintoticamente quando comparadas às filas ou arrays.

Uma fila prioritária também possui uma variedade de aplicativos essenciais. As filas de prioridade são cruciais em algoritmos de gráfico, como o algoritmo Minimum Spanning Tree de Prim e o algoritmo Shortest Path de Dijkstra. Eles também são ideais em algoritmos de agendamento de processos de unidade de processamento de computador (CPU).

Aprenda Estruturas de Dados

Filas e filas de prioridade são estruturas de dados importantes para todos os iniciantes. É crucial que os alunos se sintam confortáveis ​​ao implementar essas estruturas de dados e usá-las em diferentes projetos.

Outras estruturas de dados, como pilhas, pilhas e árvores, são igualmente importantes para alunos e profissionais. Também é muito comum que os entrevistadores questionem os candidatos sobre as estruturas de dados.

Depois de ler este artigo, você agora deve ter uma boa ideia sobre como funcionam as filas e as filas prioritárias. Se tudo ainda parecer um pouco confuso, você os controlará à medida que ganhar mais experiência em usá-los.

Heaps vs. Pilhas: o que os diferencia?

Você já ouviu falar de Heaps and Stacks, mas quando deve usar um em vez do outro?

Leia a seguir

Sobre o autor