Mais uma estrutura básica, mas é básica mesmo!

Neste artigo aqui dei uma palinha sobre como deve-se lidar com listas de encadeamento simples. Mas, se nem só de listas e árvores vive o desenvolvedor, como seria uma fila?

Fila é uma lista onde você enfia um “registro” por um lado e resgata do outro. “O primeiro que entra é o primeiro que sai” ou FIFO (First In, First Out). E como estou interessado em filas com “registros” ou nós alocados dinamicamente, a implementação mais simples é usando listas de encadeamento duplo.

Relembrando as filas de encadeamento simples, a figura abaixo mostra que temos dois nós usados como “batentes”, que chamei de head (cabeça) e tail (rabo) — o que pode gerar uma piadinha suja do tipo: “enfiar pela cabeça e tirar do rabo”… ha ha ha — e é uma estrutura semelhante que usaremos na fila:

slist2

De novo, para lembrar, os “batentes” estão ai para facilitar a manipulação da lista, por exemplo, quando esta estiver vazia. Uma lista vazia possui apenas os batentes e nenhum dos nós intermediários. E, assim, se tivermos estruturas como:

struct node_s {
  struct node_s *next;
  /* os dados entram aqui... */
};

struct list_s {
  struct node_s *head;
  struct node_s *tail;
};

Determinar se a lista está vazia é apenas questão de verificar se o ponteiro next em head aponta para o mesmo lugar que o ponteiro tail. A mesma coisa pode ser usada para determinar se uma fila está vazia ou não, como veremos adiante…

Na fila precisamos saber tanto qual é o primeiro item da lista quanto o último. A estrutura node_s fica um cadinho diferente. Precisamos adicionar um link para o nó anterior. Mas a estrutura queue_s será idêntica a list_s, acima:

struct node_s {
  struct node_s *next;
  struct node_s *prev;
  /* os dados entram aqui... */
};

struct queue_s {
  struct node_s *head;
  struct node_s *tail;
};

Já que temos agora nós que apontam para o próximo item e para o anterior, este tipo de estrutura só pode ser chamada de lista de encadeamento duplo. Uma fila pode ser implementada com esse tipo de lista e, se ela estiver vazia, ficará assim:

empty_queue
Uma fila vazia.

Inicializar uma lista de encadeamento duplo desse jeito é quase a mesma coisa que fizemos com uma lista de encadeamento simples:

struct queue_s *queue_new(void)
{
  struct queue_s *q;
  struct node_s *h, *t;

  if ((q = (struct queue_s *)
           malloc(sizeof(struct queue_s))) != NULL)
  {
    if ((h = (struct node_s *)
             malloc(sizeof(struct node_s))) == NULL)
    { free(q); return NULL; }

    if ((t = (struct node_s *)
             malloc(sizeof(struct node_s))) == NULL)
    { free(h); free(q); return NULL; }

    h->prev = t->prev = h;
    h->next = t->next = t;
    q->head = h;
    q->tail = t;
  }

  return q;
}

Para determinar se essa lista está vazia basta verificar se head->next aponte para o mesmo lugar que tail (do mesmo jeito que fizemos com a lista de encadeamento simples) ou, se quiser, se tail->prev aponte para o mesmo lugar que head:

int queue_isempty(struct queue_s *q)
{ return q->head->next == q->tail; }

A coisa começa a ficar boa quando usarmos essa lista de encadeamento duplo como uma fila. Se tivermos que enfileirar (enqueue) e desenfileirar (dequeue) nós, de posse dos batentes e dos ponteiros “para frente” e “para trás”, podemos inserir facilmente um novo nó logo depois de head e retirá-lo logo antes de tail:

struct node_s *queue_enqueue(struct queue_s *q, ...)
{
  struct node_s *n;

  if ((n = (struct node_s *)
           malloc(sizeof(struct node_s))) != NULL)
  {
    n->prev = q->head;
    n->next = q->head->next;
    q->head->next = n;

    /* Coloca os dados do nó 'n' aqui... */
    ...
  }

  return n;
}

struct node_s *queue_dequeue(struct queue_s *q)
{
  if (!queue_isempty(q))
  {
    struct node_s *n;

    /* Obtém o último nó. */
    n = q->tail->prev;

    /* Desatarracha o nó da fila... */
    q->tail->prev = n->prev;
    n->prev->next = q->tail;

    /* Obs: Se quiser, coloque NULL em
            next e prev do nó n aqui. */
    #if 0
      n->next = n->prev = NULL;
    #endif

    return n;
  }

  return NULL;
}

É claro que depois de chamar queue_dequeue o nó obtido como resultado terá que ser liberado da memória com free, mas ele não constará mais da fila.

Com essa rotina de desenfileiramento, podemos escrever a rotina de destruição da fila assim:

void queue_destroy(struct queue_s **qq)
{
  struct queue_s *q = *qq;
  struct node_s *n;

  while ((n = queue_dequeue(q)) != NULL)
  {
    /* coloque a destruição dos 
       dados do nó aqui... */

    /* Livra-se do nó. */
    free(n);
  }

  /* Livra-se da fila. */
  free(q->head);
  free(q->tail);
  free(*qq);
}

E zé fini! Temos nossa fila implementada.

PS: Notem que, a não ser pela rotina queue_isempty, uso os próprios ponteiros retornados como indicativo de sucesso ou falha (se retornar NULL) das rotinas.

Anúncios