Projeto de Algoritmos | Índice Remissivo

Módulo de implementação de uma fila (versão 3)

[Enunciado]  Minha solução implementa a fila num vetor fila[0..N-1]. O vetor é alocado dinamicamente e realocado num espaço maior sempre que a fila fica cheia.  O primeiro elemento da fila é fila[p] e o último é fila[u-1]. Portanto, 0 ≤ p ≤ u ≤ N.

As variáveis fila, N, p e u são globais no módulo.  Graças à declaração static, essas variáveis são privadas (ou seja, não são acessíveis diretamente aos usuários do módulo).  Os usuários só têm acesso à fila através das funções definidas no módulo.

Eis o arquivo  filadeints.c  que implementa o módulo:

// Arquivo filadeints.c.

#include "fileadeints.h"

// Variáveis globais do módulo.
// A fila reside em fila[p..u-1].
static int *fila;
static int p, u, N;

void criafila (void) {
   N = 100;
   fila = malloc (N * sizeof (int));
   p = 0, u = 0;
}

int filavazia (void) {
   return p >= u;
}

static void redimensiona (void) {
   N *= 2;
   fila = realloc (fila, N * sizeof (int));
   for (int i = p; i < u; i++)
      fila[i-p] = fila[i];
   u -= p;
   p = 0;
}

void colocanafila (int y) {
   if (u == N) redimensiona ();
   fila[u++] = y;
}

// Supõe que p < u.
int tiradafila (void) {
   return fila[p++];
} 

void liberafila (void) {
   free (fila);
}

Uma versão do redimensionamento que não usa realloc:

static void redimensiona (void) {
   N *= 2;
   int *nova = malloc (N * sizeof (int));
   for (int i = p; i < u; i++)
      novo[i-p] = fila[i];
   u -= p;
   p = 0;
   free (fila);
   fila = nova;
}

Eis o arquivo  filadeints.h  que serve de interface entre o usuário e a implementação filadeints.c:

// Arquivo filadeints.h.
// Exporta funções de manipulação
// de uma fila anônima de inteiros.

#ifndef _FILADEINTS_H
#define _FILADEINTS_H

// Cria uma fila vazia.
void criafila (void);

// Devolve 1 se a fila estiver vazia
// e 0 em caso contrário.
int filavazia (void);

// Coloca y na fila.
void colocanafila (int y);

// Tira um elemento da fila e devolve
// o seu valor. Não deve ser invocada
// se a fila estiver vazia.
int tiradafila (void);

// Libera o espaço ocupado pela fila.
// A fila deixa de existir.
void liberafila (void);

#endif