StacksLIFO

Pilhas (Stacks - last in, first out)

Tópicos

Introdução

Uma pilha é uma estrutura de dados linear que segue uma abordagem de “último a entrar, primeiro a sair” (LIFO - Last-In, First-Out). Em outras palavras, o último elemento adicionado à pilha é o primeiro a ser removido. Isso faz com que a pilha seja uma estrutura de dados muito útil em muitos contextos, especialmente quando você precisa manter o controle da ordem de elementos.

A estrutura de dados de pilha pode ser visualizada como uma pilha de pratos, onde você adiciona ou remove pratos apenas no topo da pilha. Para adicionar um novo elemento, você o coloca no topo da pilha, e para remover um elemento, você retira o elemento que está no topo.

Baixar, Compilar e Executar Código de Repositório via Terminal

Pré-requisitos

Antes de prosseguir, certifique-se de que você tenha o seguinte instalado no seu sistema:

Passo 1: Clone o Repositório

Abra seu terminal e execute o seguinte comando para clonar o repositório do GitHub:

git clone "https://github.com/classroom-ufersa/StacksLIFO.git"

Passo 2: Navegue para o Diretório do Repositório em que está a TAD que quer compilar

Use o comando cd para navegar para o diretório do repositório que acabou de ser clonado ou simplesmente abra com terminal integrado na pasta.

cd PilhaLista

Passo 3: Compile o Código

Compile-o usando o compilador C. Por exemplo:

gcc -o main main.c

Passo 4: Execute o Programa

Agora, você pode executar o programa compilado usando o comando ./ no terminal:

./main

Porque utilizar uma TAD?

Pilha Com Vetor

Descrição Pilha Com Vetor

imagem tirada do site: UFRJ

Estrutura Pilha Com Vetor

Estrutura struct pilha

struct pilha
{
    float *data; 
    int size;  
    int capacity; 
};

Vantagens de uma Pilha com Vetor:

  1. Simplicidade: Pilhas com vetores são fáceis de implementar e entender. A lógica de inserção (push) e remoção (pop) é direta.

  2. Eficiência de Acesso: O acesso aos elementos de uma pilha com vetor é rápido, já que os elementos são armazenados em uma estrutura de dados contígua na memória.

  3. Espaço de Memória Fixo: A pilha com vetor tem um tamanho máximo fixo definido pela capacidade do vetor. Isso pode ser benéfico quando se deseja limitar o consumo de memória.

  4. Apropriado para Uso Limitado: Para casos em que o número máximo de elementos na pilha é conhecido antecipadamente, uma pilha com vetor pode ser a escolha certa.

Desvantagens de uma Pilha com Vetor:

  1. Tamanho Fixo: O tamanho da pilha é fixo, o que significa que, se você atingir a capacidade máxima, não poderá adicionar mais elementos, a menos que aloque um vetor maior e copie os elementos existentes.

  2. Desperdício de Memória: Se a capacidade do vetor for definida muito grande, pode ocorrer desperdício de memória, especialmente se a pilha não estiver sendo totalmente utilizada.

  3. Overflows: É crucial gerenciar corretamente a pilha para evitar estouro (overflow). Essa responsabilidade recai sobre o programador de ter que reallocar.

  4. Ineficiente para Tamanhos Variáveis: Se a pilha precisa acomodar um número variável de elementos, uma estrutura de dados dinâmica, como uma lista encadeada, pode ser mais eficiente, pois pode crescer ou diminuir conforme necessário.

Algumas funções da TAD pilhavet

pilha_cria

Descrição: Esta função cria uma nova pilha alocando memória para a estrutura da pilha e o vetor de dados associado. Ela define a capacidade inicial da pilha.

Código:

Pilha *pilha_cria(void)
{
    Pilha *p = (Pilha *)malloc(sizeof(Pilha));
    p->data = (float *)malloc(d * sizeof(float));
    p->size = 0;
    p->capacity = d;
    return p;
}

Exemplo de Uso:

Pilha *minhaPilha = pilha_cria();

pilha_push

Descrição: Esta função insere um elemento no topo da pilha. Se a capacidade da pilha for excedida, o vetor de dados é redimensionado para acomodar mais elementos.

Código:

void pilha_push(Pilha *p, float v)
{
    if (p->size == p->capacity)
    {
        p->capacity++;
        p->data = (float *)realloc(p->data, p->capacity * sizeof(float));
    }
    p->data[p->size] = v;
    p->size++;
}

Exemplo de Uso:

pilha_push(minhaPilha, 42.5);

pilha_pop

Descrição: Esta função remove e retorna o elemento do topo da pilha. Ela também verifica se a pilha está vazia ou nula antes de tentar desempilhar.

Código:

float pilha_pop(Pilha *p)
{
    if (p == NULL || pilha_vazia(p))
    {
        printf("Erro: Pilha vazia ou nula!\n");
        exit(1);
    }
    return p->data[--p->size];
}

Exemplo de Uso:

float elemento = pilha_pop(minhaPilha);

Função pilha_vazia

Descrição: Esta função verifica se a pilha está vazia, retornando 1 se estiver vazia ou 0 caso contrário.

Código:

int pilha_vazia(Pilha *p)
{
    return (p->size == 0);
}

Exemplo de Uso:

if (pilha_vazia(minhaPilha)) {
    printf("A pilha está vazia.\n");
}

pilha_libera

Descrição: Esta função libera a memória alocada para a pilha, incluindo o vetor de dados e a própria estrutura da pilha.

Código:

void pilha_libera(Pilha *p)
{
    free(p->data);
    free(p);
}

Exemplo de Uso:

pilha_libera(minhaPilha);

pilha_imprime

Descrição: Esta função imprime os elementos da pilha, se houver elementos presentes.

Código:

void pilha_imprime(Pilha *p)
{
    int i;
    if (p->size == 0)
        printf("A pilha está vazia.\n");
    else
    {
        printf("Pilha: \" ");
        for (i = 0; i < p->size; i++)
        {
            printf("%.1f ", p->data[i]);
        }
        printf("\"\n");
    }
}

Exemplo de Uso:

pilha_imprime(minhaPilha);

Pilha Com Lista

Descrição Pilha Com Lista

imagem tirada do site: ARISA

Estrutura Pilha Com Lista

Estrutura struct listad (Nó da Lista Duplamente Encadeada):

struct listad
{
    float info;          
    struct listad *prox; 
    struct listad *ant;
};

Estrutura struct pilha (Pilha com Lista Duplamente Encadeada):

struct pilha
{
    struct listad *topo; 
}

Vantagens Pilha Com Lista

  1. Tamanho Variável: Ao contrário das pilhas com vetor, uma pilha com lista encadeada pode crescer ou encolher dinamicamente conforme necessário, sem a necessidade de definir um tamanho máximo antecipadamente.

  2. Eficiência de Inserção e Remoção: Inserir ou remover elementos no topo de uma pilha com lista encadeada é uma operação eficiente, pois requer apenas a atualização de ponteiros, sem realocação de memória.

  3. Uso Eficiente de Memória: A pilha com lista encadeada utiliza apenas a quantidade de memória necessária para armazenar os elementos atuais, o que a torna eficiente em termos de uso de memória quando o tamanho da pilha é variável.

Desvantagens Pilha Com Lista

  1. Complexidade de Acesso Aleatório: O acesso a elementos em posições específicas da pilha (não no topo) é menos eficiente em uma lista encadeada do que em uma pilha com vetor, já que requer percorrer a lista a partir do topo.

  2. Memória para Ponteiros: Cada nó em uma lista encadeada possui um ou dois ponteiros (um para o próximo nó e outro para o nó anterior, se for uma lista duplamente encadeada), o que pode causar um pequeno gasto de memória em comparação com um vetor.

  3. Complexidade de Implementação: Implementar uma pilha com lista encadeada pode exigir um código ligeiramente mais complexo do que uma pilha com vetor devido ao gerenciamento dinâmico de memória e aos ponteiros.

Algumas funções da TAD pilhalist

pilha_cria

Descrição: Esta função cria uma nova pilha vazia alocando memória para a estrutura da pilha.

Código:

Pilha *pilha_cria()
{
    Pilha *novo = (Pilha *)malloc(sizeof(Pilha));
    novo->topo = NULL;
    return novo;
}

Exemplo de Uso:

Pilha *minhaPilha = pilha_cria();

pilha_push

Descrição: Esta função empilha (insere) um elemento no topo da pilha.

Código:

void pilha_push(Pilha *p, float v)
{
    Lista *novo = (Lista *)malloc(sizeof(Lista));
    if (novo == NULL)
    {
        printf("[ERRO] Memória insuficiente!");
        exit(1);
    }
    novo->info = v;
    novo->prox = p->topo;
    novo->ant = NULL;
    if (p->topo != NULL)
        p->topo->ant = novo;

    p->topo = novo;
}

Exemplo de Uso:

pilha_push(minhaPilha, 42.5);

pilha_pop

Descrição: Esta função desempilha (remove e retorna) o elemento do topo da pilha.

Código:

float pilha_pop(Pilha *p)
{
    if (p->topo == NULL)
    {
        printf("Pilha vazia!");
        exit(1);
    }

    float v = p->topo->info;
    Lista *antigo = p->topo;
    p->topo = antigo->prox;

    if (p->topo != NULL)
        p->topo->ant = NULL;

    free(antigo);
    return v;
}

Exemplo de Uso:

float elemento = pilha_pop(minhaPilha);

pilha_vazia

Descrição: Esta função verifica se a pilha está vazia, retornando 1(verdadeiro) se estiver vazia ou 0(falso) caso contrário.

Código:

int pilha_vazia(Pilha *p)
{
    return (p->topo == NULL);
}

Exemplo de Uso:

if (pilha_vazia(minhaPilha))
{
    printf("A pilha está vazia.\n");
}

pilha_libera

Descrição: Esta função libera a memória utilizada pela pilha, incluindo todos os elementos.

Código:

void pilha_libera(Pilha *p)
{
    Lista *atual = p->topo;
    while (atual != NULL)
    {
        Lista *proximo = atual->prox;
        free(atual);
        atual = proximo;
    }
    free(p);
}

Exemplo de Uso:

pilha_libera(minhaPilha);

pilha_imprime

Descrição: Esta função imprime os elementos da pilha, se houver elementos presentes.

Código:

void pilha_imprime(Pilha *p)
{
    if (p->topo == NULL)
        printf("A pilha está vazia.\n");
    else
    {
        printf("Pilha: \" ");
        Lista *atual = p->topo;
        while (atual != NULL)
        {
            printf("%.1f ", atual->info);
            atual = atual->prox;
        }
        printf("\"\n");
    }
}

Exemplo de Uso:

pilha_imprime(minhaPilha);