Implementação de uma fila circular sem alocação dinâmica interna em C, através de índices em uma array de tamanho fixo.

test-fila-circular-stack.c

#include <stdio.h>
#include <stdlib.h>

#define CAPACIDADE 5
#define SIMNAO(_b_) ((_b_) ? "sim" : "não")
#define VALOR_PADRAO (0)

// Algumas notas acerca do uso dos índices primeiro e último:
// - f->primeiro é sempre um indice válido que vai de 0 a (CAPACIDADE - 1),
//   apontando para o primeiro elemento da fila
// - f->ultimo é sempre um indice que vai de 1 a CAPACIDADE,
//   apontando para um elemento APÓS o último da lista.
// - Tanto f->ultimo quanto f->primeiro podem (e vão) ser incrementados 
//   em módulo CAPACIDADE, pois a lista é circular. Ou seja:
//   - Se f->primeiro for igual a (CAPACIDADE - 1), a próxima remoção vai
//     atribuir o seu valor a 0.
//   - Se f->ultimo for igual a (CAPACIDADE), a próxima inserção vai
//     atribuir o seu valor a 1.
//
// A ideia utilizada nesta implementação é muito semelhante ao conceito de
// ring buffers.
//
// Com base nestas informações, definimos:
// - A condição inicial da lista é o estado vazio, quando f->ultimo = 0.
// - A lista está em estado "circular" quando f->ultimo <= f->primeiro.
// - f->ultimo > f->primeiro quando a lista não for circular.
// - Uma lista em estado circular estará cheia se f->ultimo == f->primeiro.
//
// Pelas razões citadas acima, deve-se tomar cuidado ao iterar a lista:
//  - O estado vazio não é iterável, e dado o uso dos índices, é fácil
//    indexar a array de valores com um índice inválido.
//  - A iteração em estado não-circular e não-vazio é feita normalmente,
//    (e.g. contador vai de f->primeiro a f->ultimo - 1).
//  - Se a lista estiver em estado não-vazio e circular:
//    - Caso a lista esteja cheia, a iteração de f->primeiro a f->ultimo - 1
//      não finalizará, pois a condição de parada nunca será atingida.
//      (pois neste caso f->ultimo - 1 < f->primeiro).
//    - Caso a lista não esteja cheia, a iteração de f->primeiro a f->ultimo - 1
//      iterará apenas elementos inválidos.
// - A iteração correta caso a lista esteja em um estado circular é 
//   "circular" o iterador (adição em módulo CAPACIDADE). Uma vez
//   "circulado" (voltou à 0), a condição de parada será i >= f->ultimo.

typedef struct fila {
    int primeiro;
    int ultimo;
    int vet[CAPACIDADE];
} fila;

// O método mostrarVetor() é especialmente importante para mostrar como a
// fila está manipulando e apontando para os elementos. O elemento inicial
// é precedido com o caractere ">", e o elemento final é sucedido do
// caractere "<". Em caso de dúvida sobre como o algoritmo funciona, use-o em
// conjunto com a função mostrar(). Eles ajudarão e muito no entendimento (eu acho).
// Alguns exemplos avulsos (considere elementos não utilizados como 0):
// - lista não circular, tamanho 4, primeiro = 0, ultimo = 4 :
//   - vetor: [>1   2   3   4<  0 ]
//   - fila: {1, 2, 3, 4}
// - lista não circular, tamanho 4, primeiro = 1, ultimo = 4 :
//   - vetor: [ 0  >2   3   4<  0 ]
//   - fila: {2, 3, 4}
// - lista circular, tamanho 4, primeiro = 3, ultimo = 2     :
//   - vetor: [ 1   2<  3  >4   5 ]
//   - fila: {4, 5, 1, 2}

// ------


fila* nova() {
	fila* f = calloc(1, sizeof(fila));
	if (f == NULL) {
		// Considerando que a falha em uma alocação
		// é um erro grave. Nunca façam isso em produção!
		exit(1);
	}
	f->primeiro = 0;
	f->ultimo = 0;
	return f;
}

void destruir(fila* f) {
	free(f);
}

int tamanho(fila* f) {
	int tam = 0;

	if (f->ultimo > 0) {
		if (f->ultimo > f->primeiro) {
			tam = f->ultimo - f->primeiro;

		} else if (f->ultimo < f->primeiro) {
			tam = CAPACIDADE - (f->primeiro - f->ultimo);

		} else {
			tam = CAPACIDADE;
		}
	}

	return tam;
}

int vazia(fila* f) {
	return f->ultimo == 0;
}

int circular(fila* f) {
	return f->ultimo > 0 && f->ultimo <= f->primeiro;
}

void mostrarVetor(fila* f) {
	int i;
	const char* sep = "";
	printf("[");
	for (i = 0; i < CAPACIDADE; ++i) {
		printf("%s%s%d%s",
			sep,
			f->primeiro == i ? ">" : "",
			f->vet[i],
			f->ultimo - 1 == i ? "<" : ""
		);
		sep = " ";
	}
	printf("]");
}

int inserir(fila* f, int v) {
	int inserido = 0;
	const int lista_circular = circular(f);

	if (f->ultimo == 0) {
		// Caso seja o primeiro elemento sendo inserido, configuramos a condição inicial
		f->primeiro = 0;
		f->ultimo = 1;
		f->vet[f->primeiro] = v;
		inserido = 1;

	} else if (f->ultimo != f->primeiro) {
		int indice_ultimo = (f->ultimo) % (CAPACIDADE) + 1;
		int circulado = indice_ultimo < f->ultimo;
		int valido = indice_ultimo - 1 != f->primeiro;

		if (valido) {
			f->ultimo = indice_ultimo;
			f->vet[f->ultimo - 1] = v;
			inserido = 1;
		}
	}

	return inserido;
}

int remover(fila* f) {
	int valor = VALOR_PADRAO;
	const int lista_circular = circular(f);

	if (f->ultimo > 0) {
		int indice_primeiro = (f->primeiro + 1) % (CAPACIDADE);
		int circulado = indice_primeiro < f->primeiro;
		int valido = 0;

		if (lista_circular) {
			valido = !circulado || indice_primeiro <= f->ultimo;

		} else {
			valido = indice_primeiro <= f->ultimo;
		}

		if (valido) {
			valor = f->vet[f->primeiro];
			f->primeiro = indice_primeiro;

			if (f->primeiro == f->ultimo) {
				// Caso o último elemento tenha sido removido, a lista fica vazia.
				f->primeiro = 0;
				f->ultimo = 0;
			}
		}
	}

	return valor;
}

void mostrar(fila* f) {
	const int lista_circular = circular(f);
	int finalizado = f->ultimo == 0;
	int circulado = 0;
	int i;
	const char* sep = "";
	printf("{");

	for (i = f->primeiro;
		!finalizado;
		i = (i + 1) % (CAPACIDADE), circulado = i < f->primeiro
	) {
		printf("%s%d", sep, f->vet[i]);
		sep = ", ";

		if (lista_circular) {
			finalizado = circulado && i >= f->ultimo - 1;

		} else {
			finalizado = circulado || (i >= f->ultimo - 1);
		}
	}
	printf("}");
}

int main(void) {
	fila* f = nova();
	int inserido, inicial = 200, tam, sucesso;
	int v, r, i;
	printf(
		"* Estado inicial - vazia? %s"
		", circular? %s"
		", tamanho = %d",
		SIMNAO(vazia(f)),
		SIMNAO(circular(f)),
		tamanho(f)
	);
	printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");

	v = 102;
	sucesso = inserir(f, v);
	printf(
		"* %d inserido? %s"
		", vazia? %s"
		", circular? %s"
		", tamanho = %d",
		v, SIMNAO(sucesso),
		SIMNAO(vazia(f)),
		SIMNAO(circular(f)),
		tamanho(f)
	);
	printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");

	r = remover(f);
	printf(
		"* removido %d"
		", correto? %s"
		", vazia? %s"
		", circular? %s"
		", tamanho = %d",
		r,
		SIMNAO(r == v),
		SIMNAO(vazia(f)),
		SIMNAO(circular(f)),
		tamanho(f)
	);
	printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");

	r = remover(f);
	printf(
		"* removido %d"
		", correto? %s"
		", vazia? %s"
		", circular? %s"
		", tamanho = %d",
		r,
		SIMNAO(r == VALOR_PADRAO),
		SIMNAO(vazia(f)),
		SIMNAO(circular(f)),
		tamanho(f)
	);
	printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");

	for (i = 0; i < CAPACIDADE; ++i) {
		v = inicial * (i + 1);
		inserido = inserir(f, v);
		printf(
			"* (%d de %d) %d inserido? %s"
			", vazia? %s"
			", circular? %s"
			", tamanho = %d",
			i + 1, CAPACIDADE, v, SIMNAO(inserido),
			SIMNAO(vazia(f)),
			SIMNAO(circular(f)),
			tamanho(f)
		);
		printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");
	}

	v = inicial;
	r = remover(f);
	printf(
		"* %d removido"
		", correto? %s"
		", vazia? %s"
		", circular? %s"
		", tamanho = %d",
		r,
		SIMNAO(r == v),
		SIMNAO(vazia(f)),
		SIMNAO(circular(f)),
		tamanho(f)
	);
	printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");

	tam = tamanho(f) - 1;
	for (i = 0; i < tam; ++i) {
		r = remover(f);
		printf(
			"* (%d de %d) %d removido"
			", vazia? %s"
			", circular? %s"
			", tamanho = %d",
			i + 1, tam, r,
			SIMNAO(vazia(f)),
			SIMNAO(circular(f)),
			tamanho(f)
		);
		printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");
		sucesso = inserir(f, r);
		printf(
			"\t* %d inserido? %s"
			", vazia? %s"
			", circular? %s"
			", tamanho = %d",
			r, SIMNAO(sucesso),
			SIMNAO(vazia(f)),
			SIMNAO(circular(f)),
			tamanho(f)
		);
		printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");
	}

	sucesso = inserir(f, inicial);
	printf(
		"* inserido? %s"
		", vazia? %s"
		", circular? %s"
		", tamanho = %d",
		SIMNAO(sucesso),
		SIMNAO(vazia(f)),
		SIMNAO(circular(f)),
		tamanho(f)
	);
	printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");

	sucesso = inserir(f, inicial);
	printf(
		"* inserido? %s"
		", correto? %s"
		", vazia? %s"
		", circular? %s"
		", tamanho = %d",
		SIMNAO(sucesso),
		SIMNAO(!sucesso),
		SIMNAO(vazia(f)),
		SIMNAO(circular(f)),
		tamanho(f)
	);
	printf(", fila = "); mostrar(f);
		printf(", vetor = "); mostrarVetor(f);
		printf("\n");

	tam = tamanho(f);
	for (i = 0; i < tam + 1; ++i) {
		r = remover(f);
		sucesso = inserir(f, r);
		printf(
			"* (%d de %d) %d removido"
			", inserido? %s"
			", vazia? %s"
			", circular? %s"
			", tamanho = %d",
			i + 1, tam + 1, r,
			SIMNAO(sucesso),
			SIMNAO(vazia(f)),
			SIMNAO(circular(f)),
			tamanho(f)
		);
		printf(", fila = "); mostrar(f);
			printf(", vetor = "); mostrarVetor(f);
			printf("\n");
	}

	destruir(f);

	return 0;
}