fila

Prévia do material em texto

Fila
A linguagem nada mais é do que uma ferramenta para concretizar essa solução.
Nesta aula, estudaremos a Estrutura de Dados conhecida como fila. 
A fila representa um conjunto dinâmico, cujos elementos são inseridos e retirados de
acordo com o seguinte protocolo: o primeiro elemento que entra no conjunto é o
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências

Fe
ed
ba
ck
primeiro que sai. Esse protocolo é amplamente conhecido como FIFO, do inglês
First in, First out (primeiro a entrar, primeiro a sair).
Ou seja, é possível inserir um elemento na fila a qualquer momento, mas somente o
elemento que está na fila há mais tempo pode ser removido a qualquer momento. O
nome fila deriva-se da metáfora de uma fila de pessoas em banco ou em um parque
de diversões (GOODRICH; TAMASSIA, 2013).
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências
Fe
ed
ba
ck
A fila é outra estrutura de dados fundamental, que tem sido utilizada em diversos
tipos de aplicações, desde comerciais (como em sistemas que controlam a chamada
de pessoas para atendimento em um banco) até sistemas operacionais (uma das
políticas mais simples de escalonamento de processos em um sistema operacional é
baseada em uma fila simples).
As principais operações que devem estar presentes em uma ED do tipo fila são:
Principais operações que devem estar presentes em uma ED do tipo fila. Fonte: elaborado pelo autor.
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências
Fe
ed
ba
ck
criar()
Cria e retorna uma fila vazia.
enfileirar(f, item)
Também conhecida como enqueue, enfileira o elemento “item” no final da fila “f”.
desenfileirar(f)
Também conhecida como dequeue, desenfileira o elemento do início da fila “f” e o
retorna.
inicio(f)
Retorna o elemento do início da fila “f”, sem retirá-lo dela.
tamanho(f)
Retorna a quantidade de elementos existentes na fila “f”.
vazia(f)
Retorna se a fila “f” está vazia ou não.
liberar(f)
Desaloca a memória ocupada pela fila “f”.
O quadro – Sequência de operações em uma ED fila –, apresenta uma série de
operações e seus efeitos sobre uma fila inicialmente vazia. 
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências
Fe
ed
ba
ck
Considere que o elemento mais à direita do conjunto de dados representa o final da
fila e o elemento mais à esquerda, o início da fila (de onde os elementos são
removidos).
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências
Fe
ed
ba
ck
Sequência de operações em uma ED fila. Fonte: elaborada pelos autores.
Assim como no caso das EDs lista e pilha, podemos implementar uma fila de pelo
menos duas formas:
utilizando vetores;
utilizando estruturas ligadas (ou encadeadas). 
Nesta aula, será apresentada a implementação por meio de estruturas ligadas.
Observe a ilustração de uma fila ligada, na figura a seguir:
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências
Fe
ed
ba
ck
Ilustração de uma fila ligada. Fonte: elaborada pelos autores.
Uma fila ligada consiste em uma sequência de elementos denominados nós
(representados por retângulos com uma seta em uma de suas extremidades na figura
- Ilustração de uma fila ligada). 
Cada nó contém uma informação (valor que aparece dentro do retângulo, na figura –
Ilustração de uma fila ligada) e um ponteiro para o próximo nó da fila (seta na
extremidade direita do retângulo).
O último nó da fila aponta para NULL, representando que não existe um próximo
nó na fila. A fila, propriamente dita, é representada por dois ponteiros, um para o
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências
Fe
ed
ba
ck
primeiro nó da fila, chamado de Inicio na figura – Ilustração de uma fila ligada –, e
outro para o último nó da fila, chamado Fim da mesma figura.
E por que dois ponteiros? 
A resposta é que, diferentemente da lista simplesmente ligada e da pilha ligada, na
fila os elementos são manipulados em ambas as extremidades. Por isso, é necessário
um ponteiro para o início e outro para o final da fila, permitindo, assim, a
manipulação dos elementos sem a necessidade de percorrer toda a estrutura de
dados.
_______
🔁 Assimile
Ao contrário da ED pilha, para a qual nós podemos ter apenas um ponteiro que
aponta para o topo de pilha, no caso da fila nós precisamos de dois ponteiros, um
para o início e outro para o final da fila. 
Isso faz sentido, pois o protocolo da fila é First in, first out, ou seja, nós inserimos
elementos no final da fila e removemos os elementos do início dela.
Avalie este conteúdo Escolha de 1 a 5 estrelas
Customização Dúvidas ao tutor
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências
Fe
ed
ba
ck
Conteúdo anterior Próximo conteúdo
Unidade 2 / Aula 3
Filas
100%
Introdução da aula
Fila
Fila ligada
Fila vazia
Vídeoaula: Fila
Vídeoaula: Exercício Listas
Conclusão
Referências
Fe
ed
ba
ck