Em uma LISTA CIRCULAR ENCADEADA, o último nó aponta para o primeiro (e não para NULL). Dessa forma, se queremos implementar uma fila, basta um ponteiro para o FIM, pois o COMEÇO será o seu próximo. Implemente um TAD fila completo (declaração da estrutura e funções) com uma lista circular dinâmica e encadeada.
Passo 1
O enunciado pede para implementar um TAD Fila usando lista simplesmente encadeada circular, armazenando apenas um ponteiro para o último nó (fim), já que o próximo desse nó é o início da fila.
Definimos primeiro os tipos: um nó (Node) com campo de dado (aqui um int, mas pode ser genérico) e ponteiro next, e a Fila contendo apenas um ponteiro para o fim.
Definimos primeiro os tipos: um nó (Node) com campo de dado (aqui um int, mas pode ser genérico) e ponteiro next, e a Fila contendo apenas um ponteiro para o fim.
Passo 2
A função de criação (criaFila) aloca a struct Fila e inicializa o ponteiro fim como NULL para indicar fila vazia.
A função filaVazia verifica se o ponteiro fim é NULL; se for, a fila está vazia.
A função filaVazia verifica se o ponteiro fim é NULL; se for, a fila está vazia.
Passo 3
Para enfileirar (enfileira), criamos um novo nó com o valor passado. Se a fila estiver vazia, fazemos next apontar para si mesmo e atualizamos fim para o novo nó. Caso contrário, inserimos o novo nó após fim e atualizamos fim para esse nó.
Passo 4
Para desenfileirar (desenfileira), primeiro tratamos fila vazia como erro. Caso haja apenas um nó (fim->next == fim), removemos e ajustamos fim para NULL. Caso haja mais de um, removemos o nó início (fim->next), atualizamos o next de fim para o próximo e retornamos o valor.
Passo 5
A operação frente retorna o valor do primeiro elemento sem removê-lo, acessando fim->next.
Por fim, liberaFila desaloca todos os nós um a um navegando a partir de início até voltar ao fim, depois libera a struct Fila.
Por fim, liberaFila desaloca todos os nós um a um navegando a partir de início até voltar ao fim, depois libera a struct Fila.
Resposta
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
int data;
struct Node *next;
} Node;
typedef struct Fila {
Node *fim; // aponta para o último nó
} Fila;
Node *fim; // aponta para o último nó
} Fila;
// Cria uma fila vazia
typedef Fila* FilaPtr;
typedef Fila* FilaPtr;
FilaPtr criaFila() {
FilaPtr f = (FilaPtr)malloc(sizeof(Fila));
if (!f) return NULL;
f->fim = NULL;
return f;
}
FilaPtr f = (FilaPtr)malloc(sizeof(Fila));
if (!f) return NULL;
f->fim = NULL;
return f;
}
// Verifica se a fila está vazia
int filaVazia(FilaPtr f) {
return (f->fim == NULL);
}
int filaVazia(FilaPtr f) {
return (f->fim == NULL);
}
// Enfileira um valor v
int enfileira(FilaPtr f, int v) {
if (!f) return 0;
Node novo = (Node)malloc(sizeof(Node));
if (!novo) return 0;
novo->data = v;
if (filaVazia(f)) {
novo->next = novo; // aponta para si mesmo
f->fim = novo;
} else {
novo->next = f->fim->next;
f->fim->next = novo;
f->fim = novo;
}
return 1;
}
int enfileira(FilaPtr f, int v) {
if (!f) return 0;
Node novo = (Node)malloc(sizeof(Node));
if (!novo) return 0;
novo->data = v;
if (filaVazia(f)) {
novo->next = novo; // aponta para si mesmo
f->fim = novo;
} else {
novo->next = f->fim->next;
f->fim->next = novo;
f->fim = novo;
}
return 1;
}
// Desenfileira e retorna o valor removido
// Se fila vazia retorna -1 (ou outro código de erro à escolha)
int desenfileira(FilaPtr f) {
if (filaVazia(f)) return -1;
Node *ini = f->fim->next;
int valor = ini->data;
if (ini == f->fim) {
// único elemento
f->fim = NULL;
} else {
f->fim->next = ini->next;
}
free(ini);
return valor;
}
// Se fila vazia retorna -1 (ou outro código de erro à escolha)
int desenfileira(FilaPtr f) {
if (filaVazia(f)) return -1;
Node *ini = f->fim->next;
int valor = ini->data;
if (ini == f->fim) {
// único elemento
f->fim = NULL;
} else {
f->fim->next = ini->next;
}
free(ini);
return valor;
}
// Retorna o valor da frente sem remover
int frente(FilaPtr f) {
if (filaVazia(f)) return -1;
return f->fim->next->data;
}
int frente(FilaPtr f) {
if (filaVazia(f)) return -1;
return f->fim->next->data;
}
// Libera toda a fila
typedef void (FreeFunc)(void);
void liberaFila(FilaPtr f) {
if (!f) return;
if (!filaVazia(f)) {
Node *p = f->fim->next;
Node *aux;
while (p != f->fim) {
aux = p;
p = p->next;
free(aux);
}
free(f->fim);
}
free(f);
}
typedef void (FreeFunc)(void);
void liberaFila(FilaPtr f) {
if (!f) return;
if (!filaVazia(f)) {
Node *p = f->fim->next;
Node *aux;
while (p != f->fim) {
aux = p;
p = p->next;
free(aux);
}
free(f->fim);
}
free(f);
}
// Exemplo de uso
int main() {
FilaPtr fila = criaFila();
enfileira(fila, 10);
enfileira(fila, 20);
printf(“Frente: %d\n”, frente(fila));
printf(“Desenfileirado: %d\n”, desenfileira(fila));
printf(“Desenfileirado: %d\n”, desenfileira(fila));
liberaFila(fila);
return 0;
}
int main() {
FilaPtr fila = criaFila();
enfileira(fila, 10);
enfileira(fila, 20);
printf(“Frente: %d\n”, frente(fila));
printf(“Desenfileirado: %d\n”, desenfileira(fila));
printf(“Desenfileirado: %d\n”, desenfileira(fila));
liberaFila(fila);
return 0;
}