Estruturas de dados: pilha com array e com lista

1. Introdução à Pilha (Stack)

A pilha é uma estrutura de dados linear que segue o princípio LIFO (Last In, First Out), onde o último elemento inserido é o primeiro a ser removido. Imagine uma pilha de pratos: você sempre coloca um novo prato no topo e retira do topo também.

As operações fundamentais de uma pilha são:
- push: insere um elemento no topo
- pop: remove e retorna o elemento do topo
- peek/top: consulta o elemento do topo sem removê-lo
- isEmpty: verifica se a pilha está vazia

Aplicações clássicas em C incluem:
- Controle de chamadas de funções (pilha de execução)
- Sistema de desfazer/refazer em editores
- Avaliação de expressões matemáticas
- Algoritmos de backtracking

2. Implementação de Pilha com Array Estático

A implementação com array estático é a mais simples e eficiente em termos de desempenho.

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Erro: pilha cheia (overflow)\n");
        return;
    }
    s->data[++s->top] = value;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Erro: pilha vazia (underflow)\n");
        return -1;
    }
    return s->data[s->top--];
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Erro: pilha vazia\n");
        return -1;
    }
    return s->data[s->top];
}

Limitações:
- Tamanho fixo definido em tempo de compilação
- Desperdício de memória se o tamanho máximo for superdimensionado
- Impossibilidade de crescimento dinâmico

3. Pilha com Array Dinâmico (Realocação)

Para superar as limitações do array estático, podemos usar alocação dinâmica de memória.

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

typedef struct {
    int *data;
    int top;
    int capacity;
} DynamicStack;

void initDynamicStack(DynamicStack *s, int initialCapacity) {
    s->data = (int*)malloc(initialCapacity * sizeof(int));
    if (!s->data) {
        printf("Erro de alocação de memória\n");
        exit(1);
    }
    s->top = -1;
    s->capacity = initialCapacity;
}

bool isEmpty(DynamicStack *s) {
    return s->top == -1;
}

void resize(DynamicStack *s, int newCapacity) {
    int *newData = (int*)realloc(s->data, newCapacity * sizeof(int));
    if (!newData) {
        printf("Erro ao redimensionar pilha\n");
        return;
    }
    s->data = newData;
    s->capacity = newCapacity;
}

void push(DynamicStack *s, int value) {
    if (s->top == s->capacity - 1) {
        resize(s, s->capacity * 2);  // Estratégia de crescimento: dobra o tamanho
    }
    s->data[++s->top] = value;
}

int pop(DynamicStack *s) {
    if (isEmpty(s)) {
        printf("Erro: pilha vazia\n");
        return -1;
    }
    int value = s->data[s->top--];

    // Reduz capacidade se necessário (fator de carga)
    if (s->top > 0 && s->top < s->capacity / 4) {
        resize(s, s->capacity / 2);
    }
    return value;
}

void freeDynamicStack(DynamicStack *s) {
    free(s->data);
    s->data = NULL;
    s->top = -1;
    s->capacity = 0;
}

4. Implementação de Pilha com Lista Encadeada

A implementação com lista encadeada oferece crescimento dinâmico sem realocação de memória.

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} LinkedListStack;

void initLinkedListStack(LinkedListStack *s) {
    s->top = NULL;
}

bool isEmpty(LinkedListStack *s) {
    return s->top == NULL;
}

void push(LinkedListStack *s, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Erro de alocação de memória\n");
        return;
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

int pop(LinkedListStack *s) {
    if (isEmpty(s)) {
        printf("Erro: pilha vazia\n");
        return -1;
    }
    Node *temp = s->top;
    int value = temp->data;
    s->top = s->top->next;
    free(temp);
    return value;
}

int peek(LinkedListStack *s) {
    if (isEmpty(s)) {
        printf("Erro: pilha vazia\n");
        return -1;
    }
    return s->top->data;
}

void freeLinkedListStack(LinkedListStack *s) {
    while (s->top != NULL) {
        Node *temp = s->top;
        s->top = s->top->next;
        free(temp);
    }
}

5. Comparação entre as Abordagens

Característica Array Estático Array Dinâmico Lista Encadeada
Complexidade push/pop O(1) O(1) amortizado O(1)
Memória Fixa Dinâmica Dinâmica
Overhead de memória Nenhum Pouco (capacidade extra) Ponteiros (8 bytes por nó)
Acesso direto Sim Sim Não
Realocação Não Sim (ocasional) Não

Cenários de uso:
- Array estático: sistemas embarcados com memória limitada e tamanho máximo conhecido
- Array dinâmico: quando o desempenho é crítico e o tamanho varia moderadamente
- Lista encadeada: quando a flexibilidade é prioritária e o overhead de ponteiros é aceitável

6. Tratamento de Erros e Casos Especiais

O tratamento adequado de erros é fundamental para implementações robustas:

// Verificação de pilha vazia em pop e peek
int pop(Stack *s) {
    if (isEmpty(s)) {
        fprintf(stderr, "Erro: tentativa de pop em pilha vazia\n");
        exit(EXIT_FAILURE);  // ou retornar valor de erro
    }
    return s->data[s->top--];
}

// Tratamento de estouro em array estático
void push(Stack *s, int value) {
    if (isFull(s)) {
        fprintf(stderr, "Erro: estouro de pilha (overflow)\n");
        return;  // ou redimensionar se for dinâmico
    }
    s->data[++s->top] = value;
}

// Gerenciamento de memória em lista encadeada
void destroyStack(LinkedListStack *s) {
    Node *current = s->top;
    Node *next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    s->top = NULL;
}

7. Exemplo Completo: Conversão de Decimal para Binário

Aplicação prática usando pilha para converter números decimais em binários.

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

// Implementação com array dinâmico (reutilizando código anterior)
void decimalToBinaryDynamic(int decimal) {
    DynamicStack stack;
    initDynamicStack(&stack, 10);

    if (decimal == 0) {
        printf("0\n");
        return;
    }

    while (decimal > 0) {
        push(&stack, decimal % 2);
        decimal /= 2;
    }

    printf("Binário (array dinâmico): ");
    while (!isEmpty(&stack)) {
        printf("%d", pop(&stack));
    }
    printf("\n");

    freeDynamicStack(&stack);
}

// Implementação com lista encadeada
void decimalToBinaryLinkedList(int decimal) {
    LinkedListStack stack;
    initLinkedListStack(&stack);

    if (decimal == 0) {
        printf("0\n");
        return;
    }

    while (decimal > 0) {
        push(&stack, decimal % 2);
        decimal /= 2;
    }

    printf("Binário (lista encadeada): ");
    while (!isEmpty(&stack)) {
        printf("%d", pop(&stack));
    }
    printf("\n");

    freeLinkedListStack(&stack);
}

int main() {
    int testValues[] = {0, 1, 10, 42, 255, 1024};
    int numTests = sizeof(testValues) / sizeof(testValues[0]);

    for (int i = 0; i < numTests; i++) {
        printf("Decimal: %d\n", testValues[i]);
        decimalToBinaryDynamic(testValues[i]);
        decimalToBinaryLinkedList(testValues[i]);
        printf("---\n");
    }

    return 0;
}

Referências