EAD Fila
- os seus elementos são processados por ordem de chegada:
- o primeiro elemento a entrar na Fila é o primeiro a sair
- FIFO (“First In First Out”).
- algumas operações realizam-se na frente/cabeça e outras na cauda da Fila
EAD Fila
- inserção de um novo elemento
- realiza-se na cauda da fila
- consiste em acrescentar deste elemento na cauda da fila,
- torna este elemento a cauda da fila;
- remoção de um elemento
- realiza-se na frente da fila,
- consiste na eliminação do elemento que se encontra na frente da fila,
- torna o elemento que está a seguir na frente/cabeça da fila.
- Fila vazia:
- acontece quando for retirado o último elemento da fila,
- apenas é possível efetuar a operação de inserção de elementos na fila.
EAD Fila - Definição axiomática
Estrutura Fila (Info)
Declarar
Criar()
Vazia(Fila)
→ Fila
→ 1 (verdadeiro) ou 0 (falso)
Juntar(Info, Fila) → Fila
Remover(Fila)
→ Fila
Frente(Fila)
→ Info
tais que ∀ S ∈ Fila, ∀ E ∈ Info sejam
Vazia(Criar ()) = 1 (verdadeiro)
Vazia(Juntar(X, Q)) = 0 (falso)
Remover(Criar()) = ERRO
Remover(Juntar(X,Q)) = Se Vazia (Q) Então Criar() Senão Juntar(X,Remover(Q))
Frente(Criar()) = ERRO
Frente(Juntar(X, Q)) = Se Vazia(Q) Então X Senão Frente(Q)
Fim Fila
EAD Fila
- Operações
- Criar uma Fila Q (vazia): Criar(Q)
- Verificar se uma Fila Q está vazia: Vazia(Q)
- Colocar um novo elemento X na cauda de uma Fila Q: Juntar(X, Q)
- Remover o elemento que está à frente de uma Fila Q: Remover(Q)
- Fornecer o elemento à frente de uma Fila Q: Frente(Q)
- implementada usando listas (tal como na EAD Pilha):
- de armazenamento sequencial (usando arrays) ou
- de armazenamento não sequencial (usando listas ligadas).
EAD Fila
- Neste documento:
- implementação usando listas ligadas simples e duplas.
- Implementação usando listas ligadas simples
- apenas se utiliza um ponteiro associado à frente da Fila (Frente);
- implementação usando listas ligadas duplas, utilização de dois ponteiros:
- um associado à frente/cabeça da Fila (Frente) e
- um outro associado à cauda da Fila (Cauda).
EAD Fila - Implementação usando listas ligadas simples
- Declaração
- a memória para os nodos e para os elementos
- é atribuída quando um elemento é inserido na fila e
- é libertada quando um elemento é removido da fila.
EAD Fila - Implementação usando listas ligadas simples
- indicador de frente/cabeça da fila
- ponteiro que aponta para o elemento mais antigo da fila,
- será o primeiro a ser removido,
- permite acesso à cauda da fila,
- é à frente deste que um novo elemento será inserido.
- quando nulo (NULL) significa fila vazia.
- uma fila nunca está cheia,
- pode acontecer que não haja memória suficiente para alocar novo elemento
EAD Fila simples - Criar uma Fila
EAD Fila simples - verificar se uma Fila está vazia
EAD Fila simples - Juntar elemento a uma Fila
EAD Fila simples - Juntar elemento a uma Fila
EAD Fila simples – Remover elemento duma Fila
EAD Fila simples - Consultar elemento duma Fila
EAD Fila - Implementação usando listas ligadas duplas
- Declaração:
- necessários dois ponteiros:
- um para a frente da fila e
- um outro para a cauda.
- cada nodo aponta
- para o nodo seguinte e
- para o nodo anterior.
EAD Fila - implementação usando listas ligadas duplas
- o primeiro nodo (frente)
- aponta para NULL (ponteiro anterior)
- serve de início da fila.
- o último nodo da fila (cauda da fila)
- aponta para NULL (ponteiro seguinte)
- serve de indicador de fim da Fila
- a memória para os nodos e para os elementos
- é atribuída quando um elemento é inserido na fila e
- é libertada quando um elemento é removido da fila.
EAD Fila - implementação usando listas ligadas duplas
- indicador de frente/cabeça da fila é
- um ponteiro que aponta para o elemento mais antigo da fila e
- o primeiro a ser removido.
- indicador de cauda da fila é
- um ponteiro que aponta para a cauda da fila,
- à frente deste que um novo elemento será inserido.
- fila vazia
- os ponteiros de frente e de cauda são nulos (NULL)
- fila nunca está cheia,
- pode acontecer que não haja memória suficiente para alocar novo elemento
EAD Fila dupla - Criar uma Fila
EAD Fila dupla - Verificar se uma Fila está vazia
EAD Fila dupla - Juntar um elemento a uma Fila
EAD Fila dupla - Juntar um elemento a uma Fila
EAD Fila dupla - Remover um elemento duma Fila
EAD Fila dupla - Consultar o elemento à cabeça duma Fila