Estrutura de Dados Parte 2 - Fila

Continuando a sequência de post's sobre estrutura de dados (8 anos depois =D)

Sempre gosto de começar o post com algum exemplo, e tento aproximá-lo ao máximo de situações que acontece em nosso dia-a-dia. Acredito que associar a algo prático ou a algo da nossa rotina torna mais fácil a compreensão do assunto, e tem algo mais comum que Filas no nosso dia-a-dia? Se vamos ao banco tem fila, se vamos ao supermercado tem fila, se vamos ao cinema na estreia dos Vingadores... tem fila. Apesar delas serem uma parte relativamente irritante da nossa vida, as filas são uma ótima forma de armazenar informações que pretendemos usar depois.

Quando temos que enfrentar filas no nosso dia a dia, procuramos sempre pela menor pois sabemos que quanto menor, mais rápido chegará nossa vez. Em outras palavras, por manterem a ordem, sabemos que quem chega primeiro é atendido primeiro.

Nas filas, ao contrários das Pilhas, o primeiro elemento a entrar é sempre o primeiro elemento a sair. Essa característica é conhecida como FIFO (First In, First Out) e possui apenas duas operações básicas chamadas de INSERT e REMOVE.


INSERT: operação para inserir um elemento no final da fila.
REMOVE: operação para remover um elemento do início da fila.

Outros operações que podem ser úteis:

isFull: operação que indica se a fila está cheia.
isEmpty: operação que indica se a fila está vazia.
size: operação que indica o tamanho da fila.

Uma implementação simples em java seria:

public class Fila {

 int tamanho = 10;
 String[] elementos = new String[tamanho];
 int fim = 0;
 int inicio = 0;

 public void insert(String elemento) {
  elementos[fim] = elemento;

  if (elemento != null && fim < tamanho) {
   fim++;
  }
 }

 public String remove() {
  String elemento = elementos[inicio];

  if (elemento != null) {
   inicio++;
  }
  return elemento;
 }

 public boolean isEmpty() {
  return inicio == fim;
 }

 public boolean isFull() {
  return size() == tamanho;
 }

 public int size() {
  return fim - inicio;
 }
 
 public static void main(String[] args) {
  Fila fila = new Fila();
  fila.insert("1");
  fila.insert("2");
  fila.insert("3");
  
  String e1 = fila.remove();
  System.out.println(e1);
  
  String e2 = fila.remove();
  System.out.println(e2);
  
  String e3 = fila.remove();
  System.out.println(e3);
 }

}

Reparem que ao executar o código, a saída será 1 2 3, nessa ordem, justamente por que o 1 foi o primeiro elemento inserido e será o primeiro a ser removido.

O que acontece se atingirmos a capacidade máxima da nossa fila? como seria possível continuar adicionando elementos? o que ocorre se removemos todos os elementos da lista? será que conseguimos continuar usando?

Há muitas melhorias que podem ser feitas nesta implementação para resolver as questões acima, mas isso deixaria a explicação bem mais complexa. Quem sabe não faço um post avançado sobre o assunto…

Uma coisa importante para ressaltar é que a maioria das linguagens de programação possuem uma biblioteca rica em estrutura de dados e que na maioria das vezes são suficientes para resolver 90% dos problemas. Nesses casos é preferível utilizar essas implementações pois já são otimizadas e testadas.

Filas são amplamente utilizadas na programação para resolver problemas que requerem uma ordem de execução como por exemplo a fila de arquivos para impressão ou o buffer de um vídeo no youtube.

Torcendo para que não leve mais 8 anos, esperem pelo próximo post sobre Listas.