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