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

Padrão

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;

   auxPointer->next = newStruct;
   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;
}
// 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;

   auxPointer->next = newStruct;
   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;
}

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 😀