PRG29003: Introdução a Filas

Próxima aula

• Uma aplicação de filas em roteadores

Uma fila é uma estrutura de dados linear. Os dados nela armazenados são dispostos por ordem de entrada, formando uma sequência. A retirada de dados também respeita a ordem de chegada, assim os dados saem de uma fila na mesma ordem em que entraram. Esse comportamento é denominado FIFO (First In First Out).

Uma fila real ... (fonte da imagem)

Existem várias aplicações para filas em programas. Tipicamente, quando algum dado precisa esperar para ser processado, ele pode ser armazenado em uma fila. Alguns exemplos:

• Eventos em um ambiente gráfico de um sistema operacional, tais como clique de mouse, tecla pressionada, e apresentação de elementos gráficos, são processados na ordem em que ocorrem. Esses eventos são armazenados em uma fila de espera.
• Sistemas operacionais costumam manter uma fila de processos que estão aptos a executar, ou que estão em espera pela ocorrência de um evento (lembrem disso lá na disciplina de Sistemas Operacionais).
• Programas de computador, incluindo o sistema operacional, precisam usualmente oferecer uma área de espera para mensagens entre processos, subsistemas ou mesmo aplicações de rede. Essa área de espera, por vezes chamada de buffer, costuma ser implementada na forma de uma fila.
• Existem algoritmos específicos que dependem de filas para funcionarem. Um exemplo é o algoritmo de busca em largura (breadth-first).

No caso mais geral, uma fila funciona como mostrado na figura a seguir:

Uma fila é acessada com três operações principais (existem outras):

• enfileiramento: usada para acrescentar um dado ao final da fila
• desenfileiramento: usada para retirar um dado do início da fila
• frente: usada para acessar o dado que está no início da fila, porém sem retirá-lo

Nesta primeira etapa da disciplina, o estudo de filas se dará com o uso de uma fila já implementada. A biblioteca Prglib oferece implementações para as estruturas de dados que são o assunto da disciplina. A declaração da Fila nessa biblioteca é esta (note que ela é declarada como um template):

template <typename T> class fila {
public:
    // construtor: cria fila com capacidade N
    fila(unsigned int N);
    
    // construtor: cria fila que é cópia da fila "orig"
    fila(const fila<T>& orig);
    
    // destrutor
    virtual ~fila();
    
    // operador de atribuição: torna esta fila uma cópia da "outra" fila
    fila<T>& operator=(const fila<T> & outra);
    
    // enfileira um dado
    void enfileira(const T & algo);
    
    // desenfileira um dado
    T desenfileira();
    
    // retorna uma referência ao dado que está no início da fila
    const T & frente() const;
    
    // testa se fila está vazia
    bool vazia() const;

    // testa se fila está cheia
    bool cheia() const;
    
    // retorna a quantidade de dados armazenados
    unsigned int comprimento() const;
    
    // retorna a capacidade da fila (quantos dados cabem)
    unsigned int capacidade() const;
    
    // expande a capacidade da fila para o novo valor "N"
    void expande(unsigned int N);
    
    // remove todos os dados da fila
    void esvazia();
};

Arquivo libs/fila.h

... e um exemplo de uso é mostrado a seguir:

#include <iostream>
#include <string>
#include "prglib.h"

using namespace std;

int main() {
  // uma fila com capacidade de armazenar 20 inteiros
  prglib::fila<int> numeros(20);

  // uma fila com capacidade de armazenar 20 string
  prglib::fila<string> coisas(20);

  numeros.enfileira(6);
  numeros.enfileira(8);
  numeros.enfileira(10);
  numeros.enfileira(12);

  coisas.enfileira("banana");
  coisas.enfileira("graviola");
  coisas.enfileira("sapoti");
  coisas.enfileira("siriguela");
  coisas.enfileira("caju");

  cout << "Fila de numeros tem comprimento=" << numeros.comprimento() << endl;
  cout << "Fila de string tem comprimento=" << coisas.comprimento() << endl;

  while (not numeros.vazia()) {
    cout << "Numero: " << numeros.desenfileira() << endl;
  }

  while (not coisas.vazia()) {
    cout << "String: " << coisas.desenfileira() << endl;
  }
}

Exercícios

• Introdução_C++

1. Resolva os seguintes exercícios sobre filas:
   • Enfileirador de caracteres
   • Fila de substrings
   • Filtro de fila
   • Concatenador de filas