Videolivro 3 - filas com uso de vetores

1. Filas

Uma fila é uma estrutura na qual o primeiro elemento a entrar é também o primeiro a sair: FIRST IN FIRST OUT (FIFO).

Exemplo é uma fila no banco:

Fonte da imagem:DIREITOS BRASIL. Lei das Filas: Tempo máximo de espera e punições. [2018]. Disponível em: https://direitosbrasil.com/lei-das-filas-tempo-maximo-de-espera-e-punicoes/. Acesso em: 25 set. 2018.

A lista pode ser implementada como um vetor, no qual o elemento que está na posição 0 (zero) foi o primeiro a chegar na fila e, portanto, será o primeiro a sair.

A Figura a seguir representa um exemplo de uma fila de jogadores de futebol à espera para pegar o uniforme do time.

No exemplo da figura que acabamos de ver, o José foi o primeiro a chegar, enquanto o Cróvis foi o último.

1.1. A classe Fila

Implementaremos a classe Fila da seguinte forma:

1o) Com uma variável do tipo inteiro para definir o tamanho da Fila (sua capacidade), assim como fizemos com a Pilha.

2o.) Com uma variável do tipo inteiro para definir a última posição ocupada na Fila.

3o.) O vetor do tipo Object, pois assim o objeto da classe fila poderá ser do tipo String (como no caso do exemplo que acabamos de mostrar) ou valores numéricos.

4o.) O construtor da classe com a última posição valendo -1 (menos 1), o tamanho e o vetor (assim como fizemos para a Pilha).

Vejamos como fica a classe Fila:

import javax.swing.JOptionPane;
public class Fila {
	int tamanho;
	int ultimapos;
	Object vetor[];
	Fila (int tam){
		ultimapos = -1;
		tamanho = tam;
		vetor = new Object [tam];
	}

}

1.2. Os métodos filaVazia() e filaCheia()

public boolean filaVazia() {
	if (ultimaPos == -1)
		return true;
	else
		return false;	
}

public boolean filaCheia() {
	if (ultimaPos == tamanho - 1)
		return true;
	else
		return false;
}

1.3. Enfileirar elementos

Para enfileirar elementos, primeiramente precisamos testar se a fila está cheia. Neste caso, enviaremos uma mensagem "Fila cheia" e não faremos nada. Caso contrário, somamos mais um à ultima posição da fila e inserimos lá o elemento. 

Lembra-se que a variável ultimaPos, que representa a última posição do vetor, recebeu -1 (menos 1) no construtor da classe? Pois bem, caso seja o primeiro elemento a ser enfileirado a posição -1 vai receber portanto, o valor 0, que será a primeira posição do vetor.

Vejamos o método:

public void enfileirar (Object valor) {
	if (filaCheia())
		JOptionPane.showMessageDialog(null,  "Fila cheia");
	else {
		ultimaPos++;
		vetor[ultimaPos]= valor;
	}
}

Agora que sabemos enfileirar, vamos criar o programa principal que instancia um objeto da classe Fila e enfileira os elementos.

1.4. Programa Principal

Nosso programa Principal vai permitir ao usuário definir o tamanho da fila.

Em seguida, vamos preencher toda a fila

Vejamos:

import javax.swing.JOptionPane;
public class Principal {

	public static void main(String[] args) {
		int tamanho;
		tamanho = Integer.parseInt(JOptionPane.showInputDialog("Qual a tamanho máximo da fila? "));
		Fila pessoas = new Fila (tamanho);
		String nome;
		int cont;
		
		for (cont=0;cont < tamanho; cont++) {
			nome = JOptionPane.showInputDialog("Nome a inserir");
			pessoas.enfileirar(nome);
		}


	}

}

1.5. O método mostrarFila()

A ideia de mostrar toda a fila é simples: percorremos o vetor até a última posição preenchida e mostramos os valores que, em nosso exemplo, guardamos em uma variável do tipo String.

public void mostrarFila() {
	int cont;
	String mensagem = "";
	for (cont=0;cont<=ultimaPos; cont++) {
		mensagem = mensagem + vetor[cont] + " ! ";
		
	}
	System.out.println(mensagem);
}

import javax.swing.JOptionPane;
public class Principal {

	public static void main(String[] args) {
		int tamanho;
		tamanho = Integer.parseInt(JOptionPane.showInputDialog("Qual a tamanho máximo da fila? "));
		Fila pessoas = new Fila (tamanho);
		String nome;
		int cont;
		
		for (cont=0;cont < tamanho; cont++) {
			nome = JOptionPane.showInputDialog("Nome a inserir");
			pessoas.enfileirar(nome);
		}
		pessoas.mostrarFila();
	}
}

1.6. O método desenfileirar ()

Desenfileirar não é um procedimento tão simples.

Veja a figura a seguir, criada hipoteticamente, para representar os jogadores de um time de futebol em uma fila de espera para receber o uniforme do time.

Como podemos notar, o José foi o primeiro a chegar, enquanto Cróvis foi o último.

Veja na próxima figura o que acontece quando José recebe seu uniforme e, portanto, sai da fila:

A posição 0, que era aquela ocupada pelo José, ficou vazia. Com isso, necessitamos mover todos os jogadores uma posição para a frente, de tal forma que a última posição (a de número 5) é que deve ficar vazia. Assim:

Quando o próximo jogador sair da fila (que é o Márcio), novamente a fila se move uma posição para a frente, de tal forma que as duas últimas ficarão vazias, conforme mostra a próxima figura:

O procedimento deve então fazer com que todos os elementos movam uma posição para frente, sempre que alguém sair da fila.

Como em uma fila o primeiro a entrar é o último a sair e, sabemos que o primeiro está sempre na posição 0, basta considerar que, a cada saída, a última posição do vetor diminui de um (lembre-se: a última posição, não o tamanho do vetor, que permanece o mesmo) e todos os elementos são "empurrados" para frente.