Filas

Filas são tipos abstratos de dados que representam uma coleção onde elementos são inseridos no final da estrutura e removidos no ínicio. Isto faz com que o primeiro elemento removido seja o primeiro elemento inserido na estrutura, por isso são também conhecidas como estruturas FIFO (First In, Fisrt Out - primeiro a entrar, primeiro a sair).

Duas operações são necessárias na implementação de filas, a operação de inserção de um elemento (enqueue ou push) e a operação de remoção de um elemento (dequeue ou pop). Normalmente, as implementações também oferecem uma forma de consultar o elemento que está no início da fila, sem retirá-lo (peek), e uma operação para testar se a fila está vazia (empty).

As filas são utilizadas em sistemas que precisam armazenar elementos que serão processados posteriormente, na mesma ordem em que foram inseridos, e neste contexto são utilizadas para criar buffers. São normalmente implementadas utilizando como estrutura de armazenamento dos dados buffers circulares ou listas encadeadas.

Operações em filas

Além das duas operações necessárias ao funcionmento das filas, algumas operações são comuns em suas implementações para facilitar a sua utilização. Operações como peek, que consulta o elemento no início da fila sem removê-lo, ou empty, que testa se a pilha está vazia.

enqueue (push)
Insere um novo elemento no final da fila. Em implementações com limite de armazenamento pode gerar um erro de fila cheia.
dequeue (pop)
Remove o elemento no início da fila, retornando-o. Em algumas implementações, pode gerar um erro de fila vazia, caso a fila esteja vazia.
peek
Retorna o elemento no início da fila, sem removê-lo. Em algumas implementações, pode gerar um erro de fila vazia, caso a fila esteja vazia.
empty
Testa se existem elementos na fila.

Implementação

Para a implementação de uma fila eficiente, é importante que as operações enqueue e dequeue sejam muito eficientes, idealmente, com número de operações executadas independente do número de elementos armazenados (\(\Theta(1)\)). Por esse motivo, a implementação de uma fila deve utilizar como estrutura de armazenamento [listas com encadeamento simples] ligeiramente modificadas (adicionando um ponteiro para o último nó da lista), ou um buffer circular.

No caso da implementação com buffer circular, normalmente, o tamanho da fila não é alterado durante a execução, sendo mais utilizado para filas de tamanho fixo. Este tipo de implementação é bastante comum em situações com limite de consumo de memória como em sistemas embarcados ou no kernel de sistemas operacionais.

A implementação apresentada aqui, utiliza buffer circular implementado sobre aranjos estáticos para a área de armazenamento. São utilizados os campos dados, que é um arranjo com tamanho definido pelo usuário, e head e tail, que armazenam um valor inteiro representando, respectivamente, a posição onde se encontram o primeiro (início) e o último (fim) elementos da fila.

Buffer circular

Um buffer circular é uma estrutura de dados que utiliza um array de tamanho fixo, onde as duas pontas são tratadas como se estivessem conectadas. Uma das vantagens de utilizar a estrutura dessa forma é que os elementos não precisam ser movimentados quando é realizada uma inserção ou remoção em qualquer uma das pontas. Assim como os arrays lineares são úteis para implementar estruturas LIFO, os buffers circulares são úteis para implementar estruturas FIFO.

Nos exemplos apresentados a seguir, o início da fila (head), onde os elementos são retirados, é representado pelo símbolo , e o final da fila (tail), onde os elementos são inseridos, pelo símbolo .

As informações necessárias para a criação de um buffer circular são a posição inicial da região de armazenamento, o tamanho da região de armazenamento (normalmente medido em quantidade de elementos), a posição onde o próximo dado será inserido (tail) e a posição onde o próximo dado será retirado (head).

Na criação do buffer, nenhum elemento está armazenado, o que é representado, nesta implementação, pela situação onde head e tail apontarem para o mesmo elemento. Embora normalmente o valor inicial dessas posições para um buffer circular seja 0 (zero), não existe nenhuma restrição contra qualquer valor, desde que esse valor se encontre dentro da área de armazenamento.

Representação em memḿoria do buffer circular. | 0 | 1 | 2 ↑ ↓ | 3 | 4 | |:-:|:-:|:-:|:-:|:-:| |   |   |   |   |   |

Sempre que um valor é inserido, ele é gravado na posição apontada por tail (↓), e essa posição é avançada para o próximo elemento disponível.

Inserção de um novo elemento | 0 | 1 | 2 ↑ | 3 ↓| 4 | |:-:|:-:|:-:|:-:|:-:| |   |   | A |   |   |

Apenas incrementar o valor de tail permite que elementos sejam inseridos na área de armazenamento até que tail aponte para o último elemento. Quando atingimos essa situação, o simples incremento levaria tail para uma posição fora da área de armazenamento.

Inserção de um novo elemento | 0 | 1 | 2 ↑ | 3 | 4 ↓ | |:-:|:-:|:-:|:-:|:-:| |   |   | A | B |   |

Como o valor de tail é utilizado com índice para gravar o novo elemento, não pode ser permitido que o valor torne-se inválido. Por esse motivo, ao inserir um novo elemento quando tail aponta para o último elemento da estrutura é necessário fazer com que o valor "de a volta", retornando para o primeiro índice da área de armazenamento.

Sabendo que a operação mod(x,y) retorna o resto da divisão de x por y, podemos utilizar esta operação para garantir que o índice esteja sempre dentro dos valores válidos. Assim, podemos criar uma função que calcule o próximo indice válido:

next(index, sz):
    return mod(index + 1, sz)

Utilizando a função criada, podemos atribuir a tail o seu resultado, garantindo que os valores atrubuídos estarão dentro do conjunto de índices validos.

tail = next(tail, dados.length)

Seguindo o exemplo anterior, como tail = 4, ao aplicar a função next teríamos o incremento do valor para 5 e o resultado seria o resto da divisão de '5' por 5, ou seja, o valor do índice de tail retornaria para o início da estrutura, com o valor 0.

Inserção de um elemento, forçando a "volta" no buffer | 0 ↓ | 1 | 2 ↑ | 3 | 4 | |:-:|:-:|:-:|:-:|:-:| |   |   | A | B | C |

Com essa abordagem, a inserção mantém sempre o mesmo processo, mantendo a eficiência do algoritmo e a clareza do código.

Inserção de um elemento após a "volta" no buffer | 0 | 1 ↓ | 2 ↑ | 3 | 4 | |:-:|:-:|:-:|:-:|:-:| | D |   | A | B | C |

Para remover um elemento, basta que o índice de head seja incrementado. Assim como ocorreu com tail, pode ser necessário que o head precise retornar ao início do buffer, e por isso, seu incremento deve ser realizado a partir da função next.

Uma vez removidos, os elementos não precisam ser retirados do buffer, pois não serão mais acessados, e serão sobrescritos caso seja necessário.

Remoção de um elemento | 0 | 1 ↓ | 2 | 3 ↑ | 4 | |:-:|:-:|:-:|:-:|:-:| | D |   | a | B | C |

Além da situação onde o "buffer está vazio, quando head e tail possuem o mesmo valor, é necessário controlar a situação onde o buffer está cheio. Esta situação ocorre quando o próximo índice de tail (calculado pela função next) for igual a head.

Nesse caso, dependendo da forma como o buffer circular foi implementado, pode haver um desperdício de uma posição de armazenamento no buffer, o qual chamamos de elemento sentinela.

Note, no próximo exemplo, que a posição 2 embora disponível, não pode ser utilizada, pois incrementar o ponteiro de inserção (tail) faria com que a estrutura atingisse o estado de fila vazia, apesar de estar com todas as posições ocupadas com elementos válidos.

"Sentinela" da implementação, monstrando posição desperdiçada | 0 | 1 | 2 ↓ | 3 ↑ | 4 | |:-:|:-:|:-:|:-:|:-:| | D | E | a | B | C |

Nesta implementação com um elemento sentinela, as funções que testam o estado do buffer para verificar se está vazio ou cheio podem ser implementadas da seguinte forma:

is_empty():
    return tail == head

is_full():
    return next(tail, data.length) == head

Inserção

A operação de inserção de um elemento no final da fila é uma das duas operações essenciais de uma fila e deve ser implementada de forma a ser o mais eficiente possível. Na implementação com listas encadeadas, o elemento é inserido como último elemento da lista, e para a operação ser eficiente, a lista deve manter um ponteiro para o último elemento armazenado.

Quando um buffer circular é utilizado a implementação é simplificada pois a fila e o buffer circular possuem um compontamento parecido.

Inserção de um novo elemento

enqueue ( value ):
    if is_full():
        error OutOfMemory
    dados[tail] = value
    tail = next(tail, dados.length)

Remoção

A operação de remoção do elemento no início da fila é a segunda das duas operações essenciais de uma fila e deve ser implementada de forma a ser o mais eficiente possível. Na implementação com listas encadeadas, isso significa remover o primeiro elemento da lista, operação que pode ser facilmente realizada mesmo nas mais tradicionais implementações de listas com encadeamento simples.

Assim como na inserção, quando é utilizado um buffer circular, a implementação é simplificada pois a fila e o buffer circular possuem um compontamento parecido.

Retirada do elemento no início da fila

dequeue ( ) -> Dado:
    if is_empty()
        error NoSuchElement
    result = dados[head]
    head = next(head, dados.length)
    return result

Consulta

A consulta sem a remoção do elemento do início da fila não é uma operação essencial, porém é muito útil na utilização de uma fila. Pode ser implementada de forma similar à operação dequeue(), e assim como essa operação, pode ocasionar o erro de fila vazia.

Consulta ao elemento no início da fila.

peek ( ) -> Dado:
    if is_empty()
        error StackUnderflow
    return dados[head]

Verificação de elementos

Embora não seja uma função essencial, a verificação da existência de elementos em uma fila pode facilitar ou acelerar a execução de algoritmos que as utilizem, de forma que não precisem tratar erros de falta de espaço ou fila vazia.

As funções do buffer circular is_empty() e is_full() podem ser utilizadas diretamente para este fim.

Aplicações de Filas

As principais aplicações de filas são como estruturas de buffer onde a ordem de avaliação dos elementos deve ser a mesma ordem em que foram inseridos. Encontramos este tipo de comportamento em diversos serviços de sistemas operacionais, como no acesso a hardware (ex. rede) ou no esclonamento de processos.

Filas são também muito utilizadas em aplicações onde uma entidade do sistema produz elementos com uma velocidade, e a outra entidade, que consome os elementos gerados trabalha em outra velocidade, como em aplicações de decodificação de vídeo e/ou áudio.

Algumas técnicas de programação de threads também utilizam filas para organizar o acesso a dados, com o gerenciamento de seções críticas sendo realizado pela própria fila (ex. queue e threads na linguagem Python).