PRG29003: Introdução a Filas

• 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). 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

A declaração da Fila na biblioteca Prglib é esta:

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

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