Out-of-series #5 – Implementação de Filas em C/C++

Um dia desses em um projeto que estou desenvolvendo profissionalmente, me deparei com a necessidade do uso de filas (queues). Explicarei apenas brevemente o que são filas, pois pretendo explicá-las mais à frente na sequência de posts didáticos sobre programação. Segundo a nossa amiga Wikipedia, “as filas são estruturas de dados baseadas no princípio FIFO (first in, first out), em que os elementos que foram inseridos no início são os primeiros a serem removidos. Uma fila possui duas funções básicas: ENQUEUE, que adiciona um elemento ao final da fila, e DEQUEUE, que remove o elemento no início da fila”. É como se fosse uma fila normal (dessas que você sempre enfrenta no banco ou no caixa do supermercado…). O primeiro que chega, é o primeiro a ser atendido. Sempre que uma nova pessoa entra, ela é “inserida” no final da fila.

A seguir, mostrarei a implementação em C e em C++ (apesar da STL do C++ já implementar queues…) utilizando listas encadeadas. Espero que possa ser útil a vocês! 🙂

// Em C++
struct dado
{
char conteudo[20]; // Pode ser qualquer tipo... char[20] é um exemplo
struct dado *link; // para o próximo item.
};
struct dado *enqueue(struct dado *queue, const char *novoItem)
{
struct dado *novaEstrutura = new struct message, *ponteiroAuxiliar;
strcpy(novaEstrutura->conteudo, novoItem);
novaEstrutura->link = NULL;
if (queue == NULL) return novaEstrutura;
for(ponteiroAuxiliar = queue; ponteiroAuxiliar->next != NULL; ponteiroAuxiliar = ponteiroAuxiliar->next);
ponteiroAuxiliar->link = novaEstrutura;
return queue;
}
struct dado *dequeue(struct dado *queue, char *item)
{
// Fila vazia - não há o que remover
if (queue == NULL)
{
item = NULL;
return NULL;
}
// Somente um item na fila
if (queue->link == NULL)
{
strcpy(item, queue->conteudo);
delete queue; // desaloca da memória
return NULL;
}
struct dado *ponteiroAuxiliar;
strcpy(item, queue->conteudo);
ponteiroAuxiliar = queue;
queue = queue->link;
delete queue;
return queue;
}
view raw queue.cpp hosted with ❤ by GitHub
// Em C
struct dado
{
char conteudo[20];
struct dado *link;
};
struct dado *enqueue(struct dado *queue, const char *novoItem)
{
struct dado *novaEstrutura = (struct dado*) malloc(sizeof(struct dado)), *ponteiroAuxiliar;
strcpy(novaEstrutura->conteudo, novoItem);
novaEstrutura->link = NULL;
if (queue == NULL) return novaEstrutura;
for(ponteiroAuxiliar = queue; ponteiroAuxiliar->next != NULL; ponteiroAuxiliar = ponteiroAuxiliar->next);
ponteiroAuxiliar->link = novaEstrutura;
return queue;
}
struct dado *dequeue(struct dado *queue, char *item)
{
// Fila vazia - não há o que remover
if (queue == NULL)
{
item = NULL;
return NULL;
}
// Somente um item na fila
if (queue->link == NULL)
{
strcpy(item, queue->conteudo);
free(queue); // desaloca da memória
return NULL;
}
struct dado *ponteiroAuxiliar;
strcpy(item, queue->conteudo);
ponteiroAuxiliar = queue;
queue = queue->link;
free(queue);
return queue;
}
view raw queue.c hosted with ❤ by GitHub

Para utilizar essas funções, basta criar um ponteiro para uma struct dado (struct dado *), inicializá-la com NULL e sempre colocá-la para pegar o retorno das funções.

Até a próxima 😀