Faça sua própria fila!
As filas são um estrutura tão comum em programação, que várias linguagens já as incluem como uma classe de objetos pronta para uso. Em C++, você pode usar a classe deque que faz parte da biblioteca std. Faz um algum tempo que eu ando pensando em escrever um tutorial, não para que você aprenda sobre as classes existentes, mas para construir sua própria classe deque. Acho que assim, podemos entender melhor programação orientada a objetos, e também porque o compilador para Arduino não inclui a std. A razão para isto é que std é uma biblioteca grande, que ocuparia muito espaço na pequena memória dos micro-controladores ATMEGA. Porém, como tudo está em constante evolução, já podemos encontrar MCUs com memória suficiente para a std e mais um sistema operacional. Mas o que importa é a experiência que vamos tirar desse estudo.
Dificuldade: ☕☕☕
Este tutorial assume que você tenha experiência em programação na linguagem C e possua um ambiente de programação instalado como o Visual Studio, VSCode, Dev-C++, Eclipse C++ ou alguma outra IDE.
O que são stacks, queues e deques?
deque é o acrônimo de double-ended queue, ou filas de ponta dupla. Esse tipo de objeto reserva um espaço na memória pra guardar um sequência de elementos. Você pode acrescentar e retirar valores pela frente ou por trás da sequência. Para estas quatro operações, as deques são objetos muito eficientes em tempo de execução.
Em C++, deque é chamada de container: é um objeto que possui uma determinada interface para armazenar e retirar dados. Não é necessário saber como funciona internamente, a não ser que você queira implementar seu próprio container 😎. A std define duas classes que restringem o comportamento do container deque, a stack (pilha) e a queue (fila). As restrições servem para que o programador não faça 💩.
Filas (queue) é um nome bem apropriado pois as pessoas que entram primeiro na fila também saem primeiro. Esse tipo de dinâmica é chamada de FIFO (first-in-first-out). A dinâmica inversa também é possível com as pilhas (stack) e é chamada de FILO (first-in-last-out): quem entra por último sai primeiro (sim, Jesus que inventou!). Vou dar alguns exemplos.
Filas - FIFO
- Filas de banco, mercado, lojas, etc. Também vale para filas virtuais em sites de compra.
- Mensagens enviadas de um periférico para outro de um sistema de controle (hardware) ou dentro de um programa (software). Para que o programa mantenha uma sequência de eventos coerente, a primeira mensagem enviada deve ser a primeira a ser lida, caso contrário, aparecerá uma tela azul do Windows 7.
- Também vale para o protocolo TCP, que auxilia a transmissão de dados na internet. O TCP garante que os pacotes de dados cheguem na ordem em que foram enviados, caso contrário: não mensagem sentido fará sua a ???
Pilhas - FILO
- Nos jogos de cobrinha: o corpo da cobra é guardado como uma fila de posições (x, y). Quando o corpo se move, uma nova posição é colocado no início da fila para a cabeça, enquanto a posição do rabo é retirada do fim da fila.
- Num jogo de cartas que são distribuídas em pilhas. Em cada pilha, a carta que foi colocada primeiro fica por baixo, portanto será a última a ser retirada.
- E-mails recebidos: muito provavelmente, você vai ler primeiro o último e-mail que chegou (mais recente), seguindo até o primeiro que chegou (mais antigo).
Por onde começo?
Determinando o comportamento esperado
Eu acho uma boa ideia começar escrevendo um trechinho de código que mostra como queremos utilizar a classe. No que segue, iniciamos um objeto do tipo Deque, colocamos alguns valores atrás da fila, depois retiramos cada um pela frente e imprimimos.
// main.cpp
#include <stdio.h>
#include "Deque.h"
int main() {
easy::Deque<int> q; // minha primeira FIFO!
q.push_back(1); // coloca 1
q.push_back(2); // coloca 2
q.push_back(3); // coloca 3
printf("%d -", q.pop_front()); // retira 1 e imprime
printf("%d -", q.pop_front()); // retira 2 e imprime
printf("%d\n", q.pop_front()); // retira 3 e imprime
return 0;
}
Este código mostra que vamos precisar de uma classe Deque com métodos push_back e pop_front. Neste tutorial, vou escrever um código compacto para facilitar a leitura. Também prefiro usar a velha função printf pois ainda não vi razão para mudar pro std::cout. Também costumo usar nomes de variáveis e funções em inglês, já que aprendi a programar lendo livros estrangeiros.
Na parte seguinte, vamos escrever a classe Deque e rodar o programa. O resultado esperado é 1 - 2 - 3. Ou seja, os números devem aparecer na ordem em que foram colocados. A primeira linha da função principal, Deque<int> q; serve para criar uma fila dupla q que vai armazenar elementos do tipo int. Esta é uma prática comum em C++. São os chamados templates. Eles são usados para indicar que a classe vale para qualquer tipo de variável. Assim, podemos criar filas de
- inteiros com Deque<int>
- caracteres com Deque<char>
- frases/strings com Deque<char*>
- etc.
Declaração da classe Deque
As classes escondem suas variáveis e oferecem uma interface com funções para o que a classe se propõe a fazer. A figura abaixo mostra como seria um objeto da classe Deque, com um espaço em memória pros valores e índices que guardam as posições da frente e de trás da fila. Ela tem funções para colocar ou retirar valores da fila. Mais detalhes sobre isso logo abaixo.
Vamos logo para a implementação inicial, no cabeçalho Deque.h:
// Deque.h
#include <assert.h>
namespace easy {
template <typename T>
class Deque
{
T* array; // espaço em memória pra fila
int capacity; // número máximo de elementos
int i0; // índice do primeiro elemento
int i1; // índice do último elemento
bool _full; // a fila está cheia?
public:
Deque(int capacity = 4) { // ---- CONSTRUTOR ----
assert(capacity >= 1); // evita fazer m****
this->capacity = capacity; // guarda a capacidade
array = new T[capacity]; // reserva memória
i0 = i1 = capacity/2; // índices iniciais
_full = false; // começa vazia
};
~Deque() { delete[] array; } // ---- DESTRUTOR -----
};
}
O que aconteceu? Definimos uma classe Queue com algumas variáveis que serão utilizadas para gerenciar a fila. Assim como a std, criamos um espaço nominal chamado easy. Os espaços nominais (namespace) servem para não ter conflito de nomes em projetos muito grandes. Se você não quiser escrever easy::Deque<tipo> toda vez que precisar usar esta classe, coloque using namespace easy; no início do seu código.
Escrevemos template <typename T> antes de criar a classe para dizer que ela pode ser usada com qualquer tipo de variável. Dentro da classe, o tipo de variável é referido por T. O único parâmetro do construtor é capacity. Se você não indicar o valor, o compilador assume que é 4 (como declarado na função, mas você pode mudar este valor).
O velho assert(capacity>=1); previne que você faça 💩. Pra quem não conhece, o assert para o programa e mostra uma mensagem de erro caso a condição entre parênteses não seja satisfeita. Um exemplo seria criar uma Deque com capacidade para 0 elementos. Afinal, não faz sentido ter uma fila em que ninguém possa entrar! Também não faz sentido ter capacity=1 mas o código acima permite.
Reserva-se um espaço em memória suficiente para capacity valores do tipo T. Porém, começamos com uma fila vazia pois os índices do primeiro e último elementos são iguais, i0=i1=capacity/2. Não faz diferença onde começam, mas quero que comecem na metade do array para poder detectar erros nos próximos testes. A variável _full serve para eliminar uma redundância no estado interno da fila: quando ela estiver cheia, i0 e i1 também serão iguais. Neste caso, mudamos o valor de _full para true. O sublinhado como prefixo do nome, é porque também quero escrever uma função full() que não pode ser confundida com o nome da variável.
Finalmente, o destrutor ~Queue() libera o espaço reservado pro array usando delete[]. Se você não sabe o que são construtores e destrutores, vou explicar: você não precisa chamar estas funções explicitamente no código, elas são automaticamente chamadas quando os objetos são declarados ou liberados, dentro de um certo escopo (leia-se dentro de chaves). Veja esse pequeno exemplo:
if (qualquer_coisa == 1)
{ // <-- ABRIU O ESCOPO
Deque<char> q(10); // A função q.Deque(10) é
// automaticamente chamada.
// ... código que usa q
} // <-- FECHOU O ESCOPO
// A função q.~Deque() é
// automaticamente chamada
// Fora do escopo, q não existe mais.
Ainda falta definir as funções push_back e pop_front.
Funções para colocar/retirar elementos da fila
Se você é nerdão como eu 🤓, e gosta de pensar na solução de problemas, vai querer gastar algum tempo para elaborar suas funções push_back e pop_front. Caso contrário, pode encontrar o código completo aqui. Depois de pensar bastante, cheguei nas implementações que seguem. Não faço ideia se parecem com as da std::deque.
push_back() - Coloca elementos atrás da fila
Algumas considerações:
- Se i0 != i1 ou _full == true o último elemento da fila está na posição i1-1 do array. E não na posição i1. Porquê? É apenas uma maneira de representar as posições preenchidas, que devem satisfazer i0 <= i < i1. Fica mais fácil de entender olhando a Figura 1.
- Quando se coloca um elemento atrás da fila, o índice i1 deve avançar, para indicar que agora array[i1] está ocupado. Porém, você deve ter percebido que as posições da fila não correspondem aos índices do array. Portanto, se i1 chegar no valor capacity, ele deve voltar a 0 (primeiro índice) e continuar a partir daí até preencher todo o array.
- Se array estiver quase cheio e um último elemento for colocado, i1 avança e se torna igual i0, a mesma condição inicial! Por isso precisamos mudar a variável _full para true.
// Dentro da classe Deque
void push_back(T item) {
assert(!_full); // não deve estar cheia!
array[i1] = item; // coloca na posição i1
if (++i1 >= capacity) i1 = 0; // avança i1 sem deixar transbordar
if (i1 == i0) _full = true; // se alcançar i0, então está cheia!
}
Acho que só precisa de mais um esclarecimento aqui, relacionado ao operador de incremento ++. Na forma como aparece, ele incrementa i1 antes de compará-lo com capacity. É equivalente a
i1 = i1 + 1; // incrementa if (i1 >= capacity) // compara i1 = 0;
pop_front() - Retira elementos da frente da fila
Também precisamos pensar um pouco no que significa colocar um elemento "na frente".
- Se a fila não estiver vazia, o elemento da frente estará na posição i0.
- Novamente, as posições em memória disponíveis vão de 0 a capacity-1. Se tentarmos acessar uma posição fora deste intervalo, como em array[capacity], o processador vai gerar uma falha de segmentação. Portanto, quando i0 chegar a capacity, ele deve retornar a 0.
- Se a fila estiver cheia e algum elemento for retirado, ela passa a não estar cheia, temos que trocar _full para false.
Para saber se a fila está vazia, é necessário testar duas condições. Por isso é melhor escrever uma função empty() que faça isso.
// Dentro da classe Deque
bool empty() { return !_full && (i0 == i1); }
T& pop_front() {
assert(!empty()); // não deve estar vazia!
_full = false; // também não vai ficar cheia
int i = i0; // guarda a posição da frente
if (++i0 >= capacity) i0 = 0; // avança i0 sem deixar transbordar
return array[i]; // retorna o elemento da frente
}
Note que pop_front() retorna uma referência para uma variável do tipo T. É isso que o caractere & significa. A diferença está no fato que a função não copia o valor para devolvê-lo à função que chamou. O valor da referência pode ser copiado, como se faria normalmente, ou tratado como se fosse um ponteiro para o elemento em array. Veja a distinção neste trecho de código:
easy::Deque<char> d(20);
// ...
// Suponha que i0 = 5
char c1 = d.pop_front(); // <-- COPIA o valor na variável c1
c1 = 'X'; // nada acontece com array[5]
char& c2 = d.pop_front(); // <-- REFERENCIA array[6]
c2 = 'Y'; // agora array[6] = 'Y'
d.push_front('Z'); // agora array[6] = c2 = 'Z'!
Os especialistas dizem que o referenciamento não faz tanta diferença para pequenas variáveis. Mas veremos um caso mais abaixo onde faz toda a diferença.
Funciona?
Só falta compilar o arquivo principal main.cpp e ver o que dá. Qualquer reclamação do compilador sobre faltar isso ou aquilo, verifique se copiou corretamente o código, provavelmente foi um fecha parênteses ) ou um ponto-e-vírgula ; que faltou.
Se você chegou até aqui, parabéns! 🎉
Mas ainda tem mais! Nossa Deque ainda está incompleta! 😱 Ainda falta escrever funções para implementar uma FILO. Pra não me alongar demais, vou deixar como exercício. As respostas encontram-se aqui.
Calculando o tamanho da fila
As pilhas e filas requerem outros métodos para para escrever programas. É importante determinar corretamente o tamanho da fila e sua capacidade. Acredito que estas funções não precisem de comentários:
// Dentro da classe Deque
int size() {
if (full()) return capacity;
if (i0 <= i1) return i1-i0;
return capacity-i0+i1;
}
int get_cap() {
return capacity;
}
Acessando elementos individualmente
Imagine se pudéssemos acessar os elementos da fila como se fossem os elementos de um array, tipo int x=q[5] ou q[5]=10. 🤔 Agora, com os modernos mecanismos do C++, você pode! Isso se chama sobrecarga de operadores, sobrecarga porquê você quer reescrever a maneira como um operador funciona. No caso, o operador seria o par de colchetes, chamado de operador indexador ou subscrito. Escrevemos esta função da seguinte forma:
// Dentro da classe Deque
T& operator[](int i) {
assert(i >= 0); // índice deve estar nos limites
assert(i < size()); // da fila pra não fazer m*
i += i0; // começa do começo (0 = i0, etc.)
if (i >= capacity) // caso tenha transbordado
i -= capacity; // ... recomeça do início
return array[i]; // devolve como referência
}
É aí que as referências fazem toda a diferença! Se a função devolvesse apenas uma cópia do valor, não seria possível modificá-lo. Com a referência podemos modificar cada elemento individualmente. Por exemplo, q[5] = 55.
Acessando os elementos um a um
Frequentemente, será necessário olhar os elementos de uma fila um a um. A maneira usual de fazer isso é escrevendo um contador i com um laço for:
for (int i = 0; i < q.size(); i++) {
// Se q[i] isso, então q[i] aquilo, etc.
}
Mas as linguagens modernas implementam iteradores pra facilitar isso. Assim, para a std::deque, podemos escrever
std::deque<int> dq;
for (auto x : dq) {
// Se x isso, então x aquilo, etc.
}
Você pode ter estranhado o nome auto. Serve para dizer que o tipo da variável x será o mesmo tipo utilizado no armazenamento dq. Infelizmente, para fazer a mesma coisa com easy::Deque, precisaríamos escrever um iterador para isto. Mas a preguiça bateu e vou apenas escrever uma macro em Deque.h:
#define FOR_EACH(element, deque, action) \
for (int _i=0; _i<q.size(); _i++) { \
auto& element = q[_i]; \
action; }
Então, no meu código principal, posso escrever apenas
FOR_EACH(x, dq, // Se x isso, então x aquilo, etc. // Também posso utilizar o índice _i )
Bem prático! Também escrevi uma macro FOR_REVR que faz a mesma coisa de trás pra frente.
Exercícios
As respostas encontram-se no código fonte.
Exercício 1
Escreva as funções push_front() que deve diminuir a posição da frente (--i0) e pop_back() que deve diminuir a posição de trás (--i1) da fila. Lembre-se de colocar asserts! Como saber se funcionam? Você pode usar a função testa_queue():
void preenche_assim(Deque<int>& q) {
for (int i = 0; i < q.get_cap(); i++)
q.push_back(i);
}
void retira_assim(Deque<int>& q) {
do { printf(" %d", q.pop_back());
} while (!q.empty());
}
void preenche_assado(Deque<int>& q) {
for (int i = 0; i < q.get_cap(); i++)
q.push_front(i);
}
void retira_assado(Deque<int>& q) {
do { printf(" %d", q.pop_front());
} while (!q.empty());
}
void testa_vazia(Deque<int>& q) {
printf("Deque q: ");
if (q.empty()) printf("empty");
else if (q.full()) printf("full");
else printf("neither");
printf(" (size = %d)\n", q.size());
}
void testa_queue()
{
printf("Testando easy::Deque\n");
printf("--------------------\n");
Deque<int> q(10);
// Teste simples de uma FIFO
printf("FIFO 1:");
preenche_assim(q);
retira_assado(q);
printf("\n");
printf("FIFO 2:");
preenche_assado(q);
retira_assim(q);
printf("\n");
// Teste simples de uma FILO
printf("filo 1:");
preenche_assim(q);
retira_assim(q);
printf("\n");
printf("filo 2:");
preenche_assado(q);
retira_assado(q);
printf("\n");
testa_vazia(q); // deve estar vazia
preenche_assado(q);
testa_vazia(q); // deve estar cheia
// Verifica o cálculo do tamanho da fila
int i = q.get_cap();
do {
q.pop_back();
assert(q.size() == --i);
if (i == 7 || i == 2) testa_vazia(q);
} while (!q.empty());
// Testa acesso dos elementos um a um
preenche_assim(q);
printf("FOR_EACH: ");
FOR_EACH(x, q,
printf("%d ", x);
x = _i*2
);
printf("\nFOR_REVR: ");
FOR_REVR(x, q, printf("%d ", x));
printf("\n");
}
Exercício 2
Escreva funções front() e back() que retornem referências para os elementos da frente e de trás da fila, respectivamente.
Exercício 3
Considere o famoso "jogo da minhoca". Para desenhar a minhoca, o jogo precisa saber as coordenadas do rabo, das partes do corpo e da cabeça. Num dado momento do jogo, a minhoca pode se apresentar com as coordenadas da figura abaixo.
struct pos_t { int x, y; }; // definição da estrutura "pos_t"
pos_t um{1, 2}; // cria a variável "um" do tipo "pos_t"
dq.push_front( pos_t{5, 5} ); // cria uma pos_t sem nome com x=5 e y=5
Escreva um código que inicialize uma fila com 4 posições consequentes. Depois faça a minhoca andar uma posição na direção x. Isto deve ser feito retirando a posição do rabo e colocando uma nova posição para a cabeça. Na figura, por exemplo, a posição da cabeça muda de {8, 5} para {9, 5}. Minha sugestão é utilizar uma referência para a posição da cabeça,
pos_t& head = snake_pos.front();
pois assim, você pode criar a nova posição usando as coordenadas da posição anterior head.x e head.y. Se você esquecer de retirar a posição do rabo (com pop_back), vai parecer que a minhoca cresceu. Para verificar se a minhoca andou, é possível escrever uma função dentro da estrutura pos_t que imprima suas coordenadas:
// Dentro de pos_t
void print() {
printf("x=%d y=%d\n", x, y);
}
// ... depois para imprimir:
snake_pos.front().print();
snake_pos.back().print();
Conclusão
Se você conseguiu ler todo esse tutorial, espero que tenha aprendido algumas coisinhas,
- Minha insistência em não usar std::cout para imprimir coisas.
- Escrever ou utilizar classes para padrões de código comuns é útil para não fazer 💩.
- Operadores de incremento (++) e decremento (--) reduzem o tamanho do código, e podem ser usados antes ou depois da variável (++i ou i++), para indicar a ordem das operações.
- Construtores e destrutores são funções chamadas automaticamente na criação ou liberação de um objeto no código.
- Referências de variáveis são ponteiros metidos a besta.
- Com sobrecarga de operadores, como o indexador [], seu código fica bonito!
- Quem não tem Iteradores, caça com Macros!
Links úteis
Código para este tutorial
std::deque
std::queue
- https://docs.microsoft.com/en-us/cpp/standard-library/queue-class
- https://www.cplusplus.com/reference/queue/queue
- https://en.cppreference.com/w/cpp/container/queue
Sobrecarga
- https://docs.microsoft.com/en-us/cpp/cpp/operator-overloading
- https://docs.microsoft.com/en-us/cpp/cpp/subscript-operator
Iteradores
- https://www.cplusplus.com/reference/iterator/iterator
- https://docs.microsoft.com/en-us/cpp/standard-library/iterators
Comentários
Postar um comentário