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! 🙂

<br />
// Em C++</p>
<p>struct dado<br />
{<br />
   char conteudo[20]; // Pode ser qualquer tipo... char[20] é um exemplo<br />
   struct dado *link; // para o próximo item.<br />
};</p>
<p>struct dado *enqueue(struct dado *queue, const char *novoItem)<br />
{<br />
   struct dado *novaEstrutura = new struct message, *ponteiroAuxiliar;<br />
   strcpy(novaEstrutura-&gt;conteudo, novoItem);<br />
   novaEstrutura-&gt;link = NULL;</p>
<p>   if (queue == NULL) return novaEstrutura;</p>
<p>   for(ponteiroAuxiliar = queue; ponteiroAuxiliar-&gt;next != NULL; ponteiroAuxiliar = ponteiroAuxiliar-&gt;next);<br />
   ponteiroAuxiliar-&gt;link = novaEstrutura;<br />
   return queue;</p>
<p>   auxPointer-&gt;next = newStruct;<br />
   return queue;<br />
}</p>
<p>struct dado *dequeue(struct dado *queue, char *item)<br />
{<br />
   // Fila vazia - não há o que remover<br />
   if (queue == NULL)<br />
   {<br />
       item = NULL;<br />
       return NULL;<br />
   }</p>
<p>   // Somente um item na fila<br />
   if (queue-&gt;link == NULL)<br />
   {<br />
       strcpy(item, queue-&gt;conteudo);<br />
       delete queue; // desaloca da memória<br />
       return NULL;<br />
   }</p>
<p>   struct dado *ponteiroAuxiliar;<br />
   strcpy(item, queue-&gt;conteudo);<br />
   ponteiroAuxiliar = queue;<br />
   queue = queue-&gt;link;<br />
   delete queue;<br />
   return queue;<br />
}<br />

<br />
// Em C</p>
<p>struct dado<br />
{<br />
   char conteudo[20];<br />
   struct dado *link;<br />
};</p>
<p>struct dado *enqueue(struct dado *queue, const char *novoItem)<br />
{<br />
   struct dado *novaEstrutura = (struct dado*) malloc(sizeof(struct dado)), *ponteiroAuxiliar;<br />
   strcpy(novaEstrutura-&gt;conteudo, novoItem);<br />
   novaEstrutura-&gt;link = NULL;</p>
<p>   if (queue == NULL) return novaEstrutura;</p>
<p>   for(ponteiroAuxiliar = queue; ponteiroAuxiliar-&gt;next != NULL; ponteiroAuxiliar = ponteiroAuxiliar-&gt;next);<br />
   ponteiroAuxiliar-&gt;link = novaEstrutura;<br />
   return queue;</p>
<p>   auxPointer-&gt;next = newStruct;<br />
   return queue;<br />
}</p>
<p>struct dado *dequeue(struct dado *queue, char *item)<br />
{<br />
   // Fila vazia - não há o que remover<br />
   if (queue == NULL)<br />
   {<br />
       item = NULL;<br />
       return NULL;<br />
   }</p>
<p>   // Somente um item na fila<br />
   if (queue-&gt;link == NULL)<br />
   {<br />
       strcpy(item, queue-&gt;conteudo);<br />
       free(queue); // desaloca da memória<br />
       return NULL;<br />
   }</p>
<p>   struct dado *ponteiroAuxiliar;<br />
   strcpy(item, queue-&gt;conteudo);<br />
   ponteiroAuxiliar = queue;<br />
   queue = queue-&gt;link;<br />
   free(queue);<br />
   return queue;<br />
}<br />

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 😀