Assunto5 Filas Encadeadas

Listas Encadeadas Especiais:
Filas Encadeadas
Códigos de Alta Performance
PROFa. PATRÍCIA MAGNA -

profpatricia.magna@fiap.com.br
1
Definição
• Uma fila (queue) é um conjunto ordenado de itens onde

a remoção de itens se faz em um extremo e a inserção
em outro.
• É uma estrutura de dados que segue a disciplina FIFO –
First In First Out (primeiro a entrar primeiro a sair).
início ...
E0 E1 En-1 final
2
Operações com Fila
• init():
– inicia a fila deixando-a vazia;
• isEmpty():
– verifica se a fila está vazia, retornando verdade se estiver
vazia e falso, caso contrário;
• enqueue(valor):
– insere um elemento em apenas uma extremidade da fila
(final da fila);
• valor = dequeue():
– remove um elemento em apenas uma extremidade da
fila (início da fila);
• valor = first() :
– lê o elemento que está no início da fila e armazena em valor;
3
Definição do Tipo de Dado Fila
• A definição do tipo de dado fila utilizando alocação dinâmica
deve-se, da mesma forma que para lista encadeada, definir o
nó.
• Assim, como TAD (tipo abstrato de dado):
NO
{
dado: tipo_do_elemento da
FILA
prox: ponteiro para NO
} Último a ser
Primeiro a ser atendido
atendido
4
• Em JAVA:
private class NO {
int dado; //supondo fila armazena valor inteiro
NO prox;
}
5
• Uma fila precisa dos seguintes componentes:

– Local para armazenar cada elemento (nó);
– Uma indicação de início da fila;
– Uma indicação de final da fila.
• Exemplo de fila com 3 elementos:
Último a ser
Primeiro a ser atendido
atendido
6
Fila Encadeada: init
• Inicia a fila deixando-a na condição de fila vazia

– início = fim = NULO
Módulo init()
{
ini = NULO
fim = NULO
}
7
Implementação em JAVA: init
public void init()

{
ini = fim = null;
}
8
Fila Encadeada: IsEmpty
• Verifica se a fila está vazia.
– Retorna verdade se estiver vazia
– falso caso contrário.
modulo IsEmpty()
{
se (ini == NULO) e (fim == NULO) então
retorna(verdade)
senão
retorna(falso)
}
9
Fila Encadeada: enqueue
• Esta operação deve considerar que existem duas

situações distintas:
– se a fila estiver vazia, ambos os ponteiros de início e fim da
fila devem apontar para o mesmo nó;
– caso contrário apenas deve-se movimentar o ponteiro de
fim.
10
Fila Encadeada: enqueue
modulo enqueue(elem)
{
novo: referência para nó
novo = ALOCA nó
novo.dado = elem
novo.prox = NULO
se (isEmpty() == verdade)
ini = novo
senão
fim.prox = novo
fim = novo
11
Exemplo de Inserção na Fila Encadeada
Supondo que a fila está vazia (os ponteiros ini e fim estariam apontando para NULO).
Depois de alocar um novo nó fazendo ser referenciado por novo:
novo = ALOCA nó
Já com o novo nó alocado, a referência de localização do nó sucessor (prox) recebe o valor

NULO: novo.prox = NULO
Enfim, o campo dado recebe valor passado pelo parâmetro elem: novo->dado = elem
12
Exemplo de Inserção na Fila Encadeada (cont)
Finalmente, posicionando os ponteiros ini e fim para apontar a fila em sua nova
configuração
ini = novo;
fim=novo;
13
Exemplo de Inserção na Fila Encadeada
Supondo que v1 seja o primeiro valor quer foi inserido na fila e Inserindo mais um
elemento com valor v2:
novo = ALOCA nó
novo.dado = v2
novo.prox = NULO
Verificando que a fila não está mais vazia, o novo passa a ser o sucessor do que era o
último da fila (fim.prox = novo) e também se torna o último da fila (fim =novo):
14
Implementação em JAVA: enqueue
public void enqueue (int elem) {
NO novo = new NO();
novo.dado = elem;
novo.prox = null;
if (isEmpty())
ini = novo;
else
fim.prox = novo;
fim = novo;
}
15
FIRST
• Retorna o valor do elemento que está no início da fila se

esta não estiver vazia.
Implemente essa operação
16
dequeue
• Retira um elemento do início da fila.

• Considerando as possíveis situações da fila:
– Se fila for composta por apenas 1 elemento:
• As referências ini e fim devem ser alteradas para NULO quando o
elemento for retirado
– Caso tenha mais do que 1 elemento
• O ponteiro ini é o único a ser alterado.
17
Operação dequeue
modulo dequeue()
{
valor = ini.dado
ini = ini.prox
se (ini = NULO)
fim= NULO
retorna (valor)
}
18
Exercícios
1) Elabore um programa que crie uma fila de números

inteiros inserindo valores até que seja digitado um
valor negativo. E depois retire cada elemento inserido
na fila apresentando na tela de saída.
19
Exercícios
2) Implemente um programa que simule a inserção e

remoção de processos na fila de uso do processador,
para tanto o programa deve ter um menu com as
seguintes opções:
1. Submete processo: lê do teclado a identificação do processo
(pid - valor inteiro) e insere na fila de processos;
2. Processa: retira da fila 1 processo (apresente o pid) e depois lê
do teclado se este foi concluído
• Se sim escreve na tela de saída mensagem de conclusão do
processo (pid).
• Se não processo deve retornar ao final da fila.
3. Encerrar programa, permitido apenas se a fila estiver vazia.
20
Exercícios
3) Simule em um programa o atendimento de pacientes

em um consultório que não trabalha com agenda de
horário colocando os pacientes em uma fila por ordem
de chegada. Cada paciente para entrar na fila deve
informar o seu nome.
4) Modifique o programa anterior para que cada paciente
tenha como atributos além do nome sua idade.
21
Referências Bibliográficas
•ASCÊNCIO, A.F.G; ARAUJO, G.S. Estruturas de Dados: Algoritmos, Análise

de Complexidade e Implementações em JAVA e C/C++. São Paulo,
Ed.Pearson Prentice Hall, 2010.
•PEREIRA, S.L.; Estruturas de Dados Fundamentais: Conceitos e
Aplicações. São Paulo, Ed. Érica, 1996.
•TENEMBAUM, A.M et al.; Estruturas de Dados usando C. Makron Books
Ltda, 1995.
•DEITEL, P; J.; Deitel, H.M., Java: como programar - 8ª edição, São Paulo,
Ed.Pearson Prentice Hall, 2010.
22
Copyright © 2024
Profa: Patrícia Magna
Todos direitos reservados. Reprodução ou divulgação total

ou parcial deste documento é expressamente proibido
sem o consentimento formal, por escrito, dos professores.
23

Assunto5 Filas Encadeadas

Enviado por

Direitos autorais:

Formatos disponíveis

Assunto5 Filas Encadeadas

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Assunto5 Filas Encadeadas

Enviado por

Direitos autorais:

Formatos disponíveis

Listas Encadeadas Especiais:

PROFa. PATRÍCIA MAGNA -

• Uma fila (queue) é um conjunto ordenado de itens onde

• Uma fila precisa dos seguintes componentes:

• Inicia a fila deixando-a na condição de fila vazia

public void init()

• Esta operação deve considerar que existem duas

Já com o novo nó alocado, a referência de localização do nó sucessor (prox) recebe o valor

• Retorna o valor do elemento que está no início da fila se

Implemente essa operação

• Retira um elemento do início da fila.

1) Elabore um programa que crie uma fila de números

2) Implemente um programa que simule a inserção e

3) Simule em um programa o atendimento de pacientes

•ASCÊNCIO, A.F.G; ARAUJO, G.S. Estruturas de Dados: Algoritmos, Análise

Todos direitos reservados. Reprodução ou divulgação total

Você também pode gostar