Estruturas de Dados em C: Fila, Pilha e Deque com Listas Encadeadas

Estruturas de Dados em C: Fila, Pilha e Deque

A seguir, são apresentadas implementações das estruturas de dados fila, pilha e deque utilizando listas encadeadas em linguagem C.

Fila (Queue)

Funções para inicializar, verificar se está vazia, enfileirar e desenfileirar elementos.

void inicializar(Fila * fila){
fila->inicio = NULL;
fila->fim = NULL;
}

int vazia(Fila * fila){
if (fila->inicio == NULL && fila->fim == NULL) {
return 1;
}
return 0;
}

Celula * criarCelula(){
Celula * nova = (Celula*) malloc (sizeof(Celula));
return nova;
}

Elemento criarElemento(char nome[], char telefone[]){
Elemento elemento;
strcpy(elemento.nome, nome);
strcpy(elemento.telefone, telefone);
return elemento;
}

int enfileirar(Fila * fila, Elemento novo){
Celula * novaCelula = criarCelula();

if (novaCelula == NULL){
printf("Erro: Memória cheia\n");
return 0;
}

novaCelula->info = novo;
novaCelula->prox = NULL;
if (vazia(fila)){
fila->inicio = novaCelula;
fila->fim = novaCelula;
return 1;
}

fila->fim = novaCelula;
fila->inicio->prox = novaCelula;
return 1;
}

Elemento desenfileirar(Fila * fila){
Celula *removida;
Elemento removido = criarElemento("","");
if (vazia(fila)){
printf("\nErro: Fila vazia.");
return removido;
}

removida = fila->inicio;
removido = removida->info;

if(fila->fim->prox == NULL){
fila->fim = fila->fim->prox;
fila->inicio = fila->fim;
}
fila->inicio = fila->inicio->prox;
free(removida);
return removido;
}

void imprimirElemento(Elemento elemento){
printf("\nNome: %s\tTelefone: %s", elemento.nome, elemento.telefone);
}

void imprimir(Fila* fila){
Elemento troca;
Fila* fila2;
inicializar(fila2);
if(vazia(fila)){
printf("Erro: Fila vazia");
return;
}
while(!vazia(fila)){
troca = desenfileirar(fila);
enfileirar(fila2, troca);
}
while(!vazia(fila2)){
troca = desenfileirar(fila2);
imprimirElemento(troca);
enfileirar(fila, troca);
}
}

Pilha (Stack)

Implementação de pilha utilizando ponteiro duplo para a célula do topo.

void inicializar(Celula ** pilha){
(*pilha) = NULL;
}

int vazia(Celula ** pilha){
if ((*pilha) == NULL){
return 1;
}
return 0;
}

Celula * criarCelula(){
Celula * nova = (Celula *) malloc (sizeof(Celula));
return nova;
}

Elemento criarElemento(char nome[], char telefone[]){
Elemento elemento;
strcpy(elemento.nome, nome);
strcpy(elemento.telefone, telefone);
return elemento;
}

int empilhar(Celula ** pilha, Elemento novo){
Celula * novaCelula = criarCelula();

if (novaCelula == NULL){
printf("Erro: Memória cheia\n");
return 0;
}

if (vazia(pilha)){
printf("Erro: Lista vazia");
}

novaCelula->info = novo;
novaCelula->prox = (*pilha);
(*pilha) = novaCelula;

return 1;
}

Elemento desempilhar(Celula ** pilha){
Celula * aux1;
Celula * aux2;

Elemento removido = criarElemento("","");
if (vazia(pilha)){
printf("\nErro: Pilha vazia.");
return removido;
}

aux1 = (*pilha);

while (aux1->prox != NULL){
aux2 = aux1;
aux1 = aux1->prox;
}

if (aux1 == (*pilha)){
(*pilha) = NULL;
} else {
aux2->prox = NULL;
}

removido = aux1->info;
free(aux1);

return removido;
}

void imprimirElemento(Elemento elemento){
printf("\nNome: %s\tTelefone: %s", elemento.nome, elemento.telefone);
}

void imprimir(Celula ** pilha){
Elemento troca;
Celula ** pilha2;
inicializar(pilha2);
if(vazia(pilha)){
printf("Erro: pilha vazia");
return;
}
while(!vazia(pilha)){
troca = desempilhar(pilha);
empilhar(pilha2, troca);
}
while(!vazia(pilha2)){
troca = desempilhar(pilha2);
imprimirElemento(troca);
empilhar(pilha, troca);
}
}

Elemento topo(Celula ** pilha){
Celula *removida;
Elemento topo = criarElemento("","");

if (vazia(pilha)){
printf("\nErro: Pilha vazia");
return topo;
}

topo = (*pilha)->info;
return topo;
}

Deque (Double-Ended Queue)

Implementação de deque com lista duplamente encadeada, permitindo inserção e remoção nas duas extremidades.

void inicializar(Deque * deque){
deque->inicio = NULL;
deque->fim = NULL;
}

int vazia(Deque * deque){
if (deque->inicio == NULL && deque->fim == NULL){
return 1;
}
return 0;
}

Celula * criarCelula(){
Celula *nova = (Celula*) malloc (sizeof(Celula));
return nova;
}

Elemento criarElemento(char nome[], char telefone[]){
Elemento elemento;
strcpy(elemento.nome, nome);
strcpy(elemento.telefone, telefone);
return elemento;
}

int inserirNoFim(Deque * deque, Elemento novo){
Deque aux;
Celula * novaCelula = criarCelula();

if (novaCelula == NULL){
printf("Erro: Memória cheia\n");
return 0;
}

novaCelula->info = novo;
novaCelula->ante = NULL;
novaCelula->prox = NULL;

if (vazia(deque)){
deque->inicio = novaCelula;
deque->fim = novaCelula;
return 1;
}

novaCelula->ante = deque->fim;
deque->fim->prox = novaCelula;
deque->fim = novaCelula;
return 1;
}

int inserirNoInicio(Deque * deque, Elemento novo){
Celula * novaCelula = criarCelula();

if (novaCelula == NULL){
printf("Erro: Memória cheia\n");
return 0;
}

novaCelula->info = novo;
novaCelula->ante = NULL;
novaCelula->prox = NULL;

if (vazia(deque)){
inserirNoFim(deque, novo);
return 1;
}

novaCelula->prox = deque->inicio;
deque->inicio = novaCelula;
return 1;
}

Elemento removerNoInicio(Deque * deque){
Elemento removido = criarElemento("","");

if(vazia(deque)){
printf("Erro: Deque vazio!\n");
return removido;
}
removido = deque->inicio->info;
if(deque->inicio == deque->fim){
free(deque->inicio);
deque->inicio = NULL;
deque->fim = NULL;
return removido;
}
deque->inicio = deque->inicio->prox;
free(deque->inicio->ante);
deque->inicio->ante = NULL;
return removido;
}

Elemento removerNoFim(Deque * deque){
Elemento removido = criarElemento("","");
if (vazia(deque)){
printf("\nErro: Deque vazio.");
return removido;
}

removido = deque->fim->ante->info;

if(deque->inicio == deque->fim){
free(deque->fim);
inicializar(deque);
return removido;
}

deque->fim = deque->fim->ante;
free(deque->fim->prox);
deque->fim->prox = NULL;
return removido;
}

void imprimirElemento(Elemento elemento){
printf("\nNome: %s\tTelefone: %s", elemento.nome, elemento.telefone);
}

void imprimir(Deque * deque){
Deque d2;
Elemento troca;

inicializar(&d2);
if(vazia(deque)){
printf("Deque vazio.");
}
while(!vazia(deque)){
troca = removerNoInicio(deque);
inserirNoFim(&d2, troca);
}
while(!vazia(&d2)){
troca = removerNoInicio(&d2);
imprimirElemento(troca);
inserirNoFim(deque, troca);
}
}