PRG29003: Introdução a Filas

• Uma aplicação de filas em roteadores

De forma geral, uma fila é uma estrutura de dados que funciona como mostrado na figura abaixo:

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

template <typename T> class fila : public std::queue<T> {
public:
    fila(unsigned int N);
    fila(const fila<T>& orig);
    virtual ~fila();
    fila<T>& operator=(const fila<T> & outra);
    void enfileira(const T & algo);
    T desenfileira();
    const T & frente() const;
    bool vazia() const;
    bool cheia() const;
    unsigned int comprimento() const;
    unsigned int capacidade() const;
private:
    unsigned int N;
};

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