Estrutura de dados: Pilha dinâmica

Hector Fernandes — Mon, 14 Dec 2020 00:44:44 +0000

Essa publicação serve como um resumo, para que eu possa consultar com facilidade, porém pode ser de grande ajuda aos iniciantes.

O que é uma pilha?

Pilha é uma estrutura de dado do tipo LIFO (last-in first-out), o que significa que o último elemento colocado, será o primeiro elemento a ser retirado. Portanto, uma pilha só permite interação com o elemento do topo.

Exemplo disso é a imagem da capa, onde para acessar a pedra do meio é necessário retirar as pedras acima, sempre começando do topo. Outro exemplo é o mecanismo de desfazer e refazer dos editores de texto.

Operações principais:

Criação da pilha (createStack)
Inserir elemento na pilha (push)
Remover elemento da pilha (pop)
Mostrar topo (showTop)
Imprimir pilha (printStack)

A pilha a ser desenvolvida, será uma pilha dinâmica na linguagem C.

Primeiro criamos a estrutura:

typedef struct stack{

    int number;
    struct stack *next;

}Stack;

Vamos criar a função que cria a pilha:

Stack **createStack(){

    Stack **varStack = (Stack **)malloc(sizeof(Stack *));
    if(varStack == NULL){

        printf("\nERRO! Memoria insuficiente.\n");
        exit(1);

    }

    *varStack = NULL;

    return varStack;
}

Agora criaremos a função de inserir:

void push(Stack **varStack, int data){

    Stack *elementStack = (Stack *)malloc(sizeof(Stack));
    if(elementStack == NULL){

        printf("\nERRO! Falta de memoria\n");
        exit(1);

    }

    if(isEmpty(varStack)){

        *varStack = elementStack;
        elementStack->number = data;
        elementStack->next = NULL;


    }else{

        elementStack->next = *varStack;
        elementStack->number = data;
        *varStack = elementStack;

    }

}

Agora a função de retirar o elemento:

int pop(Stack **varStack, int *data){

    Stack *aux;

    if(!isEmpty(varStack)){

        aux = *varStack;
        *varStack = aux->next;
        *data = aux->number;

        free(aux);

        return 1;

    }

    return 0;

}

É necessário criar uma função que verifique se a pilha está vazia, então a criaremos:

int isEmpty(Stack **varStack){

    if(varStack == NULL){

        return 1;

    }

    if(*varStack == NULL){

        return 1;

    }

    return 0;

}

Para finalizar as operações principais, criaremos as funções que imprimem os elementos:

void showTop(Stack **varStack){

    printf("\nTopo: %d\n", (*varStack)->number);

}

\\-----------------------------------------------

void printStack(Stack **varStack){

    if(varStack == NULL) return;

    Stack *aux = *varStack;

    printf("\n--------------\n");

    while (aux != NULL){

        printf("\n%d", aux->number);
        aux = aux->next;

    }

    printf("\n\n--------------\n");


}

Fora das operações principais temos duas funções que são usadas para liberar a pilha, já que é uma pilha dinâmica:

void stackFree(Stack **varStack){

    if(varStack == NULL) return;

    elementFree(*varStack);

    free(varStack);

}

void elementFree(Stack *elementStack){

    if(elementStack == NULL) return;

    elementFree(elementStack->next);

    free(elementStack);

}

A função principal pode ser desenvolvida dessa forma:

int main(){

    int op, data;
    Stack **varStack = createStack();

    do{

        printf("\n-----PILHA-----\n");
        printf("\n1 - Adicionar elemento na pilha.");
        printf("\n2 - Remover elemento do topo.");
        printf("\n3 - Imprimir elemento do topo.");
        printf("\n4 - Imprimir pilha.");
        printf("\n0 - Sair");
        printf("\nDigite: ");
        scanf("%d", &op);


        if(op == 1){

            printf("\n\nInserir elemento na pilha.");
            printf("\nDigite o numero: ");
            scanf("%d", &data);

            push(varStack, data);

        }else if(op == 2){

            if(pop(varStack, &data)){

                printf("\nElemento %d retirado.\n", data);    

            }else{

                printf("\nA pilha esta vazia.\n");

            }



        }else if(op == 3){

            showTop(varStack);

        }else if(op == 4){

            printStack(varStack);

        }

    } while (op != 0);

    stackFree(varStack);

    return 0;
}

Com isso finalizamos esse post, espero ter ajudado.
O link para o código está aqui: clique aqui!

DEV Community: Hector Fernandes

Estrutura de dados: Pilha dinâmica

O que é uma pilha?

Operações principais: