A fila pode ser descrita como estrutura de dados lineares não primitivos, seguindo a ordem FIFO na qual os elementos de dados são inseridos a partir de uma extremidade (extremidade traseira) e excluídos da outra extremidade (front end). As outras variações da fila são a fila circular, a fila duplamente terminada e a fila de prioridade.
Gráfico de comparação
| Base para comparação | Fila Linear | Fila Circular |
|---|---|---|
| Basic | Organiza os elementos e instruções de dados em uma ordem seqüencial, um após o outro. | Organiza os dados no padrão circular onde o último elemento está conectado ao primeiro elemento. |
| Ordem de execução de tarefas | As tarefas são executadas na ordem em que foram colocadas antes (FIFO). | A ordem de execução de uma tarefa pode mudar. |
| Inserção e exclusão | O novo elemento é adicionado a partir da extremidade traseira e removido da frente. | Inserção e exclusão podem ser feitas em qualquer posição. |
| atuação | Ineficiente | Funciona melhor que a fila linear. |
Definição de fila linear
Uma fila linear é racionalmente a primeira na primeira lista ordenada. É assim chamado linear porque se assemelha a uma linha reta onde os elementos são posicionados um após o outro. Ele contém uma coleção homogênea dos elementos nos quais novos elementos são adicionados em uma extremidade e excluídos da outra extremidade. O conceito da fila pode ser entendido pelo exemplo de uma fila do público que está esperando do lado de fora do balcão de passagens para obter o bilhete de teatro. Nessa fila, a pessoa se une à extremidade traseira da fila para pegar o ticket e o ticket é emitido no front end da fila.
Existem várias operações realizadas na fila
- Em primeiro lugar, a fila é inicializada para zero (isto é, vazia).
- Determine se a fila está vazia ou não.
- Determine se a fila está cheia ou não.
- Inserção do novo elemento pela extremidade traseira (Enfileirar).
- Exclusão do elemento da extremidade dianteira (Dequeue).
A fila pode ser implementada de duas maneiras
- Estaticamente (usando matrizes)
- Dinamicamente (usando ponteiros)
A limitação da fila linear é que ela cria um cenário em que nenhum novo elemento pode ser incluído na fila, mesmo que a fila contenha os espaços vazios. Esta situação acima é ilustrada na figura abaixo. Aqui a parte traseira está apontando para o último índice enquanto todas as caixas estão vazias, nenhum novo elemento pode ser adicionado.
Definição de fila circular
Uma fila circular é uma variante da fila linear que efetivamente supera a limitação da fila linear. Na fila circular, o novo elemento é adicionado na primeira posição da fila, se a última estiver ocupada e o espaço estiver disponível. Quando se trata de fila linear, a inserção pode ser realizada somente a partir da extremidade traseira e a exclusão do front end. Em uma fila completa após executar séries de deleções sucessivas na fila, surge uma certa situação em que nenhum elemento novo pode ser adicionado ainda, mesmo se o espaço disponível, porque a condição de underflow (Rear = max - 1) ainda existir.
Fila circular conecta as duas extremidades através de um ponteiro onde o primeiro elemento vem depois do último elemento. Ele também mantém o controle da parte frontal e traseira, implementando alguma lógica extra para que possa rastrear os elementos a serem inseridos e excluídos. Com isso, a fila circular não gera a condição de estouro até que a fila esteja cheia em reais.
Algumas condições seguidas pela fila circular:
- Frente deve apontar para o primeiro elemento.
- A fila estará vazia se Frontal = Traseira.
- Quando um novo elemento é adicionado, a fila é incrementada pelo valor um (Rear = Rear + 1).
- Quando um elemento é excluído da fila, a frente é incrementada em um (Frente = Frente + 1).
Principais diferenças entre a fila linear e a fila circular
- A fila linear é uma lista ordenada na qual os elementos de dados são organizados na ordem sequencial. Em contraste, a fila circular armazena os dados na forma circular.
- Fila linear segue a ordem FIFO para executar a tarefa (o elemento adicionado na primeira posição será deletado na primeira posição). Por outro lado, na fila circular, a ordem das operações executadas em um elemento pode mudar.
- A inserção e exclusão dos elementos é fixada na fila linear, ou seja, adição da extremidade traseira e exclusão da extremidade frontal. Por outro lado, a fila circular é capaz de inserir e excluir o elemento de qualquer ponto até que ele esteja desocupado.
- A fila linear desperdiça o espaço de memória enquanto a fila circular faz uso eficiente do espaço.
Implementação da fila linear
O algoritmo abaixo ilustra a adição de elementos em uma fila:
A fila precisa de três variáveis de dados, incluindo uma matriz para armazenar a fila e outra para armazenar a posição inicial frontal e traseira que é -1.
insira (item, fila, n, retaguarda) {if (rear == n) então imprima "estouro de fila"; else {rear = retaguarda + 1; fila [retaguarda] = item; }} O algoritmo fornecido abaixo ilustra a exclusão de elementos em uma fila:
delete_circular (item, fila, traseira, frente) {if (rear == front), em seguida, imprime "underflow de fila"; else {frente = frente + 1; item = fila [frente]; }} Implementação da fila circular
Um algoritmo para interpretar a adição do elemento na fila circular:
insert_circular (item, fila, traseira, frente) {retaguarda = (retaguarda + 1) mod n; se (frente == traseiro), imprima "fila está cheia"; else {queue [rear] = item; }} Algoritmo explica a exclusão do elemento na fila circular:
delete_circular (item, fila, traseira, frente) {if (frente == traseira) e depois imprimir ("fila está vazia"); else {frente = frente + 1; item = fila [frente]; }} Conclusão
A fila linear é ineficiente em certos casos em que os elementos são obrigados a mudar para os espaços vagos para executar a operação de inserção. Essa é a razão pela qual ele tende a desperdiçar o espaço de armazenamento enquanto a fila circular faz uso apropriado do espaço de armazenamento, pois os elementos são adicionados em qualquer posição, se houver um espaço vazio.
