PRG29003: Introdução a Filas
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 STL (Standard Template Library) oferece implementações para as estruturas de dados que são o assunto da disciplina. A fila disponibilizada nessa biblioteca se chama queue (que significa fila em inglẽs), e suas operações básicas são estas:
- push: enfileira um dado
- pop: desenfileira um dado (descarta-o)
- front: retorna o dado que está na frente da fila
- back: retorna o dado que está no fim da fila (último dado enfileirado)
- size: retorna o comprimento da fila (quantos dados estão armazenados)
- empty: retorna true se fila estiver vazia, e false caso contrário
... e um exemplo de uso é mostrado a seguir:
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {
// uma fila que armazena números inteiros
queue<int> numeros;
// uma fila que armazena string
queue<string> coisas;
// push_back adiciona um dado no fim da fila
numeros.push(6);
numeros.push(8);
numeros.push(10);
numeros.push(12);
coisas.push("banana");
coisas.push("graviola");
coisas.push("sapoti");
coisas.push("siriguela");
coisas.push("caju");
cout << "Fila de numeros tem comprimento=" << numeros.size() << endl;
cout << "Fila de string tem comprimento=" << coisas.size() << endl;
while (! numeros.empty()) {
cout << "Numero: " << numeros.front() << endl;
numeros.pop(); // desenfileira um número
}
while (! coisas.empty()) {
cout << "String: " << coisas.front() << endl;
coisas.pop(); // desenfileira uma string
}
}
Exercícios
- Resolva os seguintes exercícios sobre filas: