Estrutura de Fila em Programação

Prévia do material em texto

ED: filas
Prof. Me. Marcos Frazão
⦁ São listas lineares que adotam a política FIFO (First
In First Out – o primeiro que entra é o primeiro que
sai) para a manipulação de elementos.
⦁ As inserções são feitas no final da fila.
⦁ As remoções são feitas no início da fila.
⦁ A consulta na fila é feita desenfileirando elemento
a elemento até encontrar o elemento desejado ou
chegar ao final da fila.
⦁ Alocação de recursos para impressão de 
documentos em uma impressora (spooler de 
impressão).
⦁ Atendimento de processos requisitados ao 
um sistema operacional.
⦁ Ordenação do encaminhamento dos pacotes 
em um roteador.
⦁ Buffer para gravação de dados em mídia.
fila para pouso
fila para decolagem
b a x m k
x m k
a
a x m k
b
b a x m k
b a x
k
b a x m
m
⦁ Criação
⦁ Destruição
⦁ Inserção de um elemento
⦁ Remoção de um elemento
⦁ Localização de um elemento para consulta ou 
alteração
⦁ Ordenação de uma lista
⦁ Intercalação de duas listas
⦁ Concatenação de duas listas
⦁ Divisão de uma lista em duas
⦁ Para isso devemos fixar o número máximo N 
de elementos na fila.
⦁ Note que o processo de inserção e remoção 
em extremidades opostas fará com que a fila 
“ande” no vetor.
⦁ Exemplo: se inserirmos os elementos
1.4, 2.2, 3.5, 4.0 e depois retirarmos dois 
elementos, a fila não estará mais nas 
posições iniciais do vetor.
1.4 2.2 3.5 4.0 ...
0 1 2 3 4 5
ini fim
3.5 4.0 ...
0 1 2 3 4 5
ini fim
⦁ Observamos que em dado instante, a parte 
ocupada do vetor pode chegar à última 
posição.
⦁ Para reaproveitar as primeiras posições livres 
do vetor sem implementarmos uma re-
arrumação trabalhosa dos elementos, 
podemos incrementar as posições do vetor 
de forma “circular”: se o último elemento 
ocupa a última posição do vetor, inserimos os 
novos elementos a partir do início do vetor.
⦁ Desta forma, em um dado momento, poderíamos ter 
quatro elementos, 20.0, 20.8, 21.2 e 24.3, distribuídos 
dois no fim e dois no início do vetor.
21.2 24.3 ... ... 20.0 20.8
0 1 98 99
fim ini
⦁ Para essa implementação, os índices do vetor 
são incrementados de maneira que seus
valores progridam “circularmente”.
⦁ Desta forma, se temos 100 posições no 
vetor, os valores dos índices assumem os 
seguintes valores:
⦁ 0, 1, 2, 3, ..., 98, 99, 0, 1, 2, 3, ..., 98, 99, 0, 1, ...
⦁ Função auxiliar responsável por incrementar o valor de 
um índice.
⦁ Esta função recebe o valor do índice atual e fornece 
com valor de retorno o índice incrementado, usando o 
incremento circular.
int incr (int i) {
if (i == Fila.MAX - 1)
return 0;
else
return i+1;
}
⦁ Podemos declarar uma estrutura tipo fila como sendo 
uma estrutura com três componentes:
◦ Um vetor vet de tamanho N,
◦ Um índice ini para o início da fila
◦ Um índice fim para o fim da fila
⦁ Onde,
◦ ini marca a posição do próximo elemento a ser retirado da fila;
◦ fim marca a posição (vazia), onde será inserido o próximo 
elemento
⦁ Desta forma a fila vazia se dá ini == fim e a fila cheia se 
caracteriza por ter fim e ini em posições consecutivas 
(circularmente): incr(fim) == ini.
⦁ A estrutura fila pode ser dada por:
// Declaração da classe Fila
public class Fila {
 // Define uma constante MAX que representa a 
capacidade máxima da fila
 static final int MAX = 10; 
 
 // Variáveis de instância para controlar o início 
e o fim da fila
 private int inicio = 0; // Índice do primeiro 
elemento da fila
 private int fim = 0; // Índice do próximo lugar 
para inserir um elemento
 // Array para armazenar os elementos da fila
 private float vet[] = new float[MAX]; // Vetor que 
contém os elementos da fila
}
⦁ Para inserir um elemento na fila, usamos a 
próxima posição livre do vetor, indicada por fim. 
Devemos verificar se há espaço para a inserção 
de um novo elemento (utilizamos vetor)
// Método que insere um elemento na fila
void insere(Fila f, float v) {
 // Verifica se a fila está cheia
 if (incr(f.fim) == f.inicio) {
 // Se a próxima posição do fim é igual ao início, a fila está cheia
 System.out.println("Capacidade da fila estourou");
 System.exit(1); // Aborta o programa com código de saída 1
 }
 
 // Insere o elemento na próxima posição livre
 f.vet[f.fim] = v; // Atribui o valor v à posição atual do fim da fila
 
 // Atualiza o índice fim para a próxima posição
 f.fim = incr(f.fim); // Incrementa o índice fim para a próxima posição livre
}
⦁ A função para retirar o elemento no início da fila fornece
o valor do elemento retirado como retorno. Verifica-se
antes se a fila está ou não vazia:
// Método que retira e retorna um elemento da fila
float retira(Fila f) {
 float v; // Declara uma variável para armazenar o valor a ser retirado
 // Verifica se a fila está vazia
 if (vazia(f)) {
 // Se a fila estiver vazia, imprime uma mensagem de erro
 System.out.println("Fila vazia.\n");
 System.exit(1); // Aborta o programa com código de saída 1
 }
 // Retira o elemento no início da fila
 v = f.vet[f.inicio]; // Armazena o valor do primeiro elemento da fila na 
variável v
⦁ A função para retirar o elemento no início da fila fornece
o valor do elemento retirado como retorno. Verifica-se
antes se a fila está ou não vazia:
// Atualiza o índice do início para a próxima posição
 f.inicio = incr(f.inicio); // Incrementa o índice inicio para o próximo 
elemento
 
 // Retorna o valor retirado
 return v; // Retorna o valor armazenado em v
}
⦁ A função que verifica se a fila está vazia pode ser dada por:
boolean vazia (Fila f)
{
return (f.inicio == f.fim);
}
⦁ Finalmente, o código para liberar a memória alocada pela fila:
f = null;
⦁ Para testar o código, pode ser útil implementarmos
uma função que imprima os valores armazenados
na fila. A ordem de impressão adotada é do início
para o fim.
// Método que imprime os elementos da fila
void imprime(Fila f) {
 int i; // Variável inteira para o índice
 // Loop que percorre a fila desde o início até o fim
 for (i = f.inicio; i != f.fim; i = incr(i)) {
 // Imprime o elemento no índice atual da fila
 System.out.println(f.vet[i]);
 }
}
public static void main(String[] args) {
 // Cria uma nova instância da fila
 Fila f = new Fila(); 
 
 // Insere elementos na fila
 f.insere(f, 20.0f); // Insere o valor 20.0 na fila
 f.insere(f, 20.8f); // Insere o valor 20.8 na fila
 f.insere(f, 20.2f); // Insere o valor 20.2 na fila
 f.insere(f, 20.3f); // Insere o valor 20.3 na fila
 
 // Imprime o conteúdo atual da fila
 f.imprime(f);
 
 // Remove e imprime o primeiro elemento da fila
 System.out.println("\n Primeiro elemento: " + 
f.retira(f)); 
 // Remove e imprime o segundo elemento da fila
 System.out.println("\n Segundo elemento: " + 
f.retira(f)); 
 
 // Imprime a configuração atual da fila após as 
remoções
 System.out.println("\n Configuracao da fila:");
 f.imprime(f);
 
 // Define a variável f como null, permitindo que a 
fila seja coletada pelo garbage collector
 f = null;
}
A estrutura de dados fila implementa qual 
mecanismo de inserção e retirada de dados?
a) FIFA.
b) FIFO.
c) LIFO.
d) FFLL.
e) FOFL.
A estrutura de dados fila implementa qual 
mecanismo de inserção e retirada de dados?
a) FIFA.
b) FIFO.
c) LIFO.
d) FFLL.
e) FOFL.
A respeito de algoritmos e estruturas de dados, 
julgue o próximo item. Fila de prioridades é um tipo 
abstrato de dados que permite executar algumas 
operações: por exemplo, a operação INSERT (S,x) 
insere o elemento x no conjunto S e a operação 
MAXIMUM (S) retorna o elemento de S que possui a 
maior chave.
( ) Certo
 ( ) Errado
Considere uma estrutura de fila (disciplina FIFO) de números inteiros com 
duas operações: INSERE (n) e RETIRA ( ). Considere, também, que a 
representação do estado da fila em um instante qualqueré realizada listando 
os elementos, de forma 
que o primeiro elemento, da esquerda para a direita, é o mais antigo presente 
na fila.
Se a fila começa vazia, a sequência
INSERE (2)
INSERE (3)
RETIRA ( )
INSERE (1)
RETIRA ( )
INSERE (4)
INSERE (5)
RETIRA ( )
RETIRA ( )
levará a uma fila no estado
a) 1 2 3 4 5
b) 2 3 1 4 5
c) 3 1 4
d) 4 5
e) 5
Considere uma estrutura de fila (disciplina FIFO) de números inteiros com 
duas operações: INSERE (n) e RETIRA ( ). Considere, também, que a 
representação do estado da fila em um instante qualquer é realizada listando 
os elementos, de forma 
que o primeiro elemento, da esquerda para a direita, é o mais antigo presente 
na fila.
Se a fila começa vazia, a sequência
INSERE (2)
INSERE (3)
RETIRA ( )
INSERE (1)
RETIRA ( )
INSERE (4)
INSERE (5)
RETIRA ( )
RETIRA ( )
levará a uma fila no estado
a) 1 2 3 4 5
b) 2 3 1 4 5
c) 3 1 4
d) 4 5
e) 5
A respeito de algoritmos e estruturas de dados, 
julgue o próximo item. Fila de prioridades é um tipo 
abstrato de dados que permite executar algumas 
operações: por exemplo, a operação INSERT (S,x) 
insere o elemento x no conjunto S e a operação 
MAXIMUM (S) retorna o elemento de S que possui a 
maior chave.
( X ) Certo
 ( ) Errado
Acerca da estrutura de dados do tipo filas, considere as 
operações de inserção e remoção de uma fila F abaixo:
1. enfileira ('amarelo', F) 2. enfileira ('branco', F) 3. enfileira 
('verde', F) 4. enfileira ('vermelho', F) 5. desenfileira (F) 6. 
desenfileira (F) 7. enfileira ('azul', F) 8. enfileira (desenfileira 
(F), F)
O resultado final das operações resulta em:
a) [verde, azul, vermelho].
b) [branco, azul, amarelo].
c) [verde, azul].
d) [amarelo, branco].
e) [vermelho, azul, verde].
Acerca da estrutura de dados do tipo filas, considere as 
operações de inserção e remoção de uma fila F abaixo:
1. enfileira ('amarelo', F) 2. enfileira ('branco', F) 3. enfileira 
('verde', F) 4. enfileira ('vermelho', F) 5. desenfileira (F) 6. 
desenfileira (F) 7. enfileira ('azul', F) 8. enfileira (desenfileira 
(F), F)
O resultado final das operações resulta em:
a) [verde, azul, vermelho].
b) [branco, azul, amarelo].
c) [verde, azul].
d) [amarelo, branco].
e) [vermelho, azul, verde].
Analise as seguintes afirmativas sobre estruturas de dados: listas, filas e pilhas.
I. Em uma lista linear em alocação sequencial, cada nó é formado por campos 
que 
armazenam características distintas dos elementos da lista. Cada nó da lista 
pode possuir um 
identificador denominado chave, que deve ser único na lista para evitar 
ambiguidades.
II. A fila é um caso particular de listas onde as inserções e as remoções são 
realizadas apenas em uma das extremidades da lista.
III. A pilha é um caso particular de listas onde as inserções são realizadas em 
uma extremidade e as remoções na outra extremidade da lista.
É correto afirmar que a(s) afirmativa(s)
a) I é verdadeira.
b) II é verdadeira.
c) III é verdadeira.
d) I e II são verdadeiras.
e) I e III são verdadeiras.
Analise as seguintes afirmativas sobre estruturas de dados: listas, filas e pilhas.
I. Em uma lista linear em alocação sequencial, cada nó é formado por campos 
que 
armazenam características distintas dos elementos da lista. Cada nó da lista 
pode possuir um 
identificador denominado chave, que deve ser único na lista para evitar 
ambiguidades.
II. A fila é um caso particular de listas onde as inserções e as remoções são 
realizadas apenas em uma das extremidades da lista.
III. A pilha é um caso particular de listas onde as inserções são realizadas em 
uma extremidade e as remoções na outra extremidade da lista.
É correto afirmar que a(s) afirmativa(s)
a) I é verdadeira.
b) II é verdadeira.
c) III é verdadeira.
d) I e II são verdadeiras.
e) I e III são verdadeiras.
Um conjunto ordenado de itens a partir do qual podem ser eliminados itens em 
uma extremidade e no qual podem ser inseridos itens na outra 
extremidade é denominado de
a) fila.
b) pilha.
c) lista simples.
d) lista encadeada.
e) árvore.
Um conjunto ordenado de itens a partir do qual podem ser eliminados itens em 
uma extremidade e no qual podem ser inseridos itens na outra 
extremidade é denominado de
a) fila.
b) pilha.
c) lista simples.
d) lista encadeada.
e) árvore.
Considerando as definições para listas (pilhas e 
filas), assinale a alternativa correta.
a) Uma lista é um tipo de fila que se caracteriza por considerar que
 o primeiro elemento a entrar é o primeiro a sair.
b) Lista é um conjunto de filas e pilhas e se compõe por elementos que 
podem ser ligados ou não.
c) Uma lista pode ter uma configuração que possa ser uma arvore 
balanceada ou não.
d) Lista é uma sequência finita de elementos ligados entre si. Podem ser 
organizada de tal forma que implemente uma fila ou uma pilha.
Considerando as definições para listas (pilhas e 
filas), assinale a alternativa correta.
a) Uma lista é um tipo de fila que se caracteriza por considerar que
 o primeiro elemento a entrar é o primeiro a sair.
b) Lista é um conjunto de filas e pilhas e se compõe por elementos que 
podem ser ligados ou não.
c) Uma lista pode ter uma configuração que possa ser uma arvore 
balanceada ou não.
d) Lista é uma sequência finita de elementos ligados entre si. Podem ser 
organizada de tal forma que implemente uma fila ou uma pilha.
	Slide 1: ED: filas
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37