PRG29003: Introdução a Filas
Ir para navegação
Ir para pesquisar
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
- Resolva os seguintes exercícios sobre filas: