Estrutura de Dados: Fila

Prévia do material em texto

Estrutura de Dados 
 
 
 
 
UNIP - Ciência da Computação e Sistemas de Informação 
AULA 6 
Filas 
Estrutura de Dados 
 
A Estrutura de Dados Fila 
• Fila é uma estrutura de dados usada em programação, que tem regras 
para o acesso aos dados: inserções são feitas em uma extremidade, 
chamada final da fila, remoções são feitas na outra extremidade, 
chamada início da fila. 
 
• Dizemos que uma Fila é uma estrutura FIFO (First In, First Out), ou seja, 
o primeiro elemento inserido é o primeiro elemento a ser consultado ou 
removido. 
 
• Vamos analisar o comportamento de uma fila olhando o exemplo a 
seguir. 
 
3 2 1 0 
 
Simulando uma Fila ( tamanho = 4) 
1) Fila Vazia 
inicio = 0 fim = 0 total = 0 
3 2 1 0 
 
Simulando uma Fila ( tamanho = 4) 
1) Fila Vazia 
inicio = 0 fim = 0 total = 0 
3 2 1 0 
 “A” 
2) Enfileirar(“A”) 
inicio = 0 fim = 1 total = 1 
3 2 1 0 
“B” “A” 
Simulando uma Fila ( tamanho = 4 ) 
3) Enfileirar(“B”) 
inicio = 0 fim = 2 total = 2 
3 2 1 0 
“B” “A” 
Simulando uma Fila ( tamanho = 4 ) 
3) Enfileirar(“B”) 
inicio = 0 fim = 2 total = 2 
3 2 1 0 
“C” “B” “A” 
4) Enfileirar(“C”) 
inicio = 0 fim = 3 total = 3 
3 2 1 0 
“D” “C” “B” “A” 
Simulando uma Fila ( tamanho = 4 ) 
5) Enfileirar(“D”) 
inicio = 0 fim = 0 total = 4 
6) Desenfileirar() 
inicio = 1 fim = 0 total = 3 
3 2 1 0 
“D” “C” “B” 
3 2 1 0 
“D” “C” 
Simulando uma Fila ( tamanho = 4 ) 
7) Desenfileirar() 
inicio = 2 fim = 0 total = 2 
8) Enfileirar(“E”) 
inicio = 2 fim = 1 total = 3 
3 2 1 0 
“D” “C” “E” 
3 2 1 0 
“D” “C” “F” “E” 
Simulando uma Fila ( tamanho = 4 ) 
9) Enfileirar(“F”) 
inicio = 2 fim = 2 total = 4 
10) Desenfileirar() 
inicio = 3 fim = 2 total = 3 
3 2 1 0 
“D” “F” “E” 
11) MostrarFila() 
“D” “E” “F” 
Operações de Fila 
 
enfileirar – insere um elemento na fila 
desenfileirar – remove um elemento da fila 
tamanho – informa número de elementos 
fila vazia – verifica se a fila está vazia 
fila cheia - verifica se a fila está cheia 
elemento do início – mostra o elemento que está no início 
da fila 
mostrar fila – exibe todos os elementos que a fila possui. 
Descrição da classe Fila 
• Basicamente, esses métodos são: 
• construtor fila() - cria a fila e inicia o início e o fim 
• enfileirar() - armazena valores no final da fila 
• desenfileirar() – retira e devolve o valor do início da fila 
• tamanho() – informa número de elementos 
• filaVazia() - verifica se a fila está ou não vazia 
• filaCheia() – verifica se a fila está ou não cheia 
• elementoInicio() - consulta e devolve o elemento do início 
sem retirá-lo da fila 
• No caso de fila vazia, ao se tentar buscar o elemento do 
início, deve-se disparar uma exceção, que cuidará dessa 
situação de erro. 
Classe Fila 
public class Fila { 
int tamanho, inicio, fim, total; 
Object vetor[]; 
public Fila (int tam){ 
inicio = 0; 
fim = 0; 
total = 0; 
tamanho = tam; 
vetor= new Object[tamanho]; 
} 
public boolean filaVazia( ) { 
 if (total == 0) { 
 return true; 
 } else { 
 return false; 
 } 
} 
public boolean filaCheia( ){ 
if (total >= tamanho){ 
 return true; 
} else { 
 return false; 
} 
} 
public void enfileirar(Object elemento){ 
if (!filaCheia( )){ 
 vetor[fim] = elemento; 
 fim = fim + 1; 
 total = total + 1; 
 if (fim >= tamanho) { 
 fim = 0; // volta ao início da fila 
 } 
} else { 
 System.out.println("Fila Cheia"); 
} 
} 
public Object desenfileirar( ) { 
Object desenfileirado = null; 
if (filaVazia()) { 
 System.out.println("Fila Vazia"); 
} else { 
 desenfileirado = vetor[inicio]; 
 inicio = inicio + 1; 
 total = total -1; 
 if (inicio >= tamanho) { 
 inicio = 0; // retorna para o começo da fila 
 } 
} 
return desenfileirado; 
} 
public Object elementoInicio( ){ 
if (!filaVazia()){ 
 return vetor[inicio]; 
} else { 
 System.out.println (“Fila Vazia”); 
} 
} 
 
public void mostrarFila( ) { 
int i = inicio; // utilizado com índice 
int cont = 0; // contador do número de elementos 
String result=""; 
while ( cont < total ) { 
result+= "Elemento " + vetor[i] + " posição " + i+"\n"; 
i++; 
if ( i == tamanho ) { 
i = 0; 
} 
cont++; 
} 
System.out.println(result); 
} 
Classe TesteFila, que utiliza os métodos 
public class TesteFila1{ 
 
public static void main (String arg []) { 
 Fila f = new Fila(3); 
 f.enfileirar("A"); 
 f.enfileirar("B"); 
 f.enfileirar("C"); 
 String msg = (String)f.desenfileirar(); 
 System.out.printf("Elemento removido: %s" , msg); 
 // Imprime “A” 
 f.mostrarFila(); // Mostra “B” e “C” 
 System.exit(0); 
 } 
} 
Classe Teste, que utiliza os métodos 
import java.util.Scanner; 
public class TesteFila2 { 
public static void main(String[] args) { 
 Fila objFila = new Fila(5); 
 Scanner ler = new Scanner (System.in); 
 int entrada; 
 int i; 
 for (i = 0; i < objFila.vetor.length; i++){ 
 System.out.print("\nDigite um valor inteiro: "); 
 entrada = ler.nextInt(); 
 objFila.enfileirar(entrada); 
 } 
 objFila.mostrarFila( ); 
 System.exit(0); 
 } 
} 
Exercício 
Fazer um exercício para ler um número em 
binário, e convertê-lo para decimal. 
 
Usar uma Fila na solução do problema 
A função substring() 
 A função substring() é utilizada para retornar uma cópia de 
caracteres de uma string a partir de dois índices inteiros 
especificados. 
 Sintaxe: 
 <string>.substring(<índice inicial>,[<índice final>]) 
 O índice inicial indica o primeiro caracter que será copiado. 
 O índice final indica onde termina a cópia dos caracteres, porém 
deve ser especificado um índice além do que queremos copiar. 
 Exemplo: 
 String a,b; 
 a = “Faculdade UNIP”; 
 b = a.substring(0,9); 
 O valor de b será: “Faculdade” 
Exercício 
Fazer um exercício para ler um número em 
hexadecimal, e convertê-lo para decimal. 
 
Usar uma Fila na solução do problema