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
}
}
Repositório de exercícios
Todos os exercícios estão disponíveis no GitHub, um serviço de armazenamento e compartilhamento de projetos de software. Cada exercício está no formato de um projeto CLion, e pode ser obtido com este procedimento:
- Execute o CLion e siga uma destas duas instruções:
- Se aparecer uma tela de abertura com opções de criação de um novo projeto, clique na opção Check out from Version Control.
- Se o CLion abrir com um projeto já existente (ou se ele já estava em execução com algum outro projeto), clique no menu VCS->Git->Clone.
- Em ambos os casos, aparecerá uma pequena janela com título Clone Repository
- Copie a URL (link) do exercício para a caixa de texto URL, e em seguida clique em Clone
- O projeto CLion será baixado do GitHub e criado em seu CLion
Exercícios
O seguinte programa ilustra o uso de fila para armazenar dados que estão em espera por processamento.
- Objetivo: Escrever um programa que copie um conjunto de arquivos para dentro de um determinado diretório.
- Descrição: O programa a ser escrito deve receber como dados de entrada o diretório de destino e os nomes dos arquivos a serem copiados. O diretório de destino deve ser lido do teclado, seguido então dos nomes dos arquivos. Quando o usuário digitar uma linha vazia (pressionar somente ENTER), então o programa faz a cópia dos arquivos.
Antes de escrever esse programa, resolva estes exercícios para se familiarizar com filas. Observe que eles estão disponibilizados no GitHub (ver instruções de acesso):