No post de hoje vamos implementar uma pilha usando uma lista ligada em C, ou seja, sem usar classes. O mais importante hoje é demonstrar como implementar apropriadamente uma estrutura de dados e as funções que vão manipular os dados.

No próximo post vamos implementar a mesma pilha usando lista ligada utilizando C++, ou seja, utilizando classes, os dois posts em conjunto servirão como exemplo da importância das estruturas de dados no desenvolvimento de software.

Primeiro vamos deixar claro uma coisa. Apesar de aprendermos algoritmos antes de aprender estrutura de dados, desenvolvimento de software não é sobre algoritmos, e sim sobre estrutura de dados, não é à toa que os primeiros cursos de computação chamavam-se processamento de dados.

Por isso da importância de concentrar o desenvolvimento na definição das estruturas de dados, em segundo lugar os algoritmos que manipulam os dados.

Definindo as Estruturas de Dados

Vamos começar definindo duas estruturas de dados, a primeira representa a própria pilha, a segunda cada nó individual da lista ligada da pilha:

typedef struct _node{
    void *data;
    struct _node *prev;
} node;

typedef struct {
    unsigned size;
    node *top;
} _linkedstack;
typedef _linkedstack *linkedstack;

Foi necessário definir o nó primeiro, pra facilitar a definição da struct que representa a pilha. Note também que definimos linkedstack como um ponteiro para a struct, assim a manipulação do ponteiro é transparente para o programador, vamos ver essa simplicidade ao definir as funções que manipulam a pilha.

Definindo as Funções de Interface

Agora que definimos as estruturas de dados, podemos definir as funções que irão manipular a lista:

linkedstack linkedstack_new();
void linkedstack_delete(linkedstack stack);

int linkedstack_push(linkedstack stack, void *data);
void* linkedstack_pop(linkedstack stack);
void* linkedstack_top(linkedstack stack);
unsigned linkedstack_size(linkedstack stack);

Note na declaração das funções, com exceção da linkedstack_new(), todas tem o primeiro parâmetro a estrutura linkedstack. Quem já programa em python já conhece essa técnica, aonde os métodos da classe recebem um ponteiro para o próprio objeto como primeiro parâmetro. Além disso essa técnica elimina a necessidade de variáveis globais, fazendo com que o código possa ser mais facilmente reaproveitado.

Vamos colocar estruturas de dados e declaração de funções em um arquivo .h, que pode ser conferido no git.

Implementando as Funções

Uma vez definida a interface, vamos implementar as funções:

#include "linkedstack.h"
#include <stdlib.h>
linkedstack linkedstack_new() {
    linkedstack stack = (linkedstack)malloc(sizeof(_linkedstack));
    if (!stack)
        return stack;
    stack->size = 0;
    stack->top = NULL;
    return stack;
}
void linkedstack_delete(linkedstack stack) {
    if (!stack)
        return;
    while (stack->top) {
        free(stack->top->data);
        node *delnode = stack->top;
        stack->top = stack->top->prev;
        free(delnode);
    }
    free(stack);
}
int linkedstack_push(linkedstack stack, void *data) {
    node *newnode = NULL;
    if (!stack)
        return 0;
    newnode = (node*)malloc(sizeof(node));
    if (!newnode)
        return 0;
    newnode->data = data;
    newnode->prev = stack->top;
    stack->top = newnode;
    stack->size++;
}
void* linkedstack_pop(linkedstack stack) {
    void *data = NULL;
    if (!stack || !stack->top)
        return NULL;
    data = stack->top->data;
    stack->top = stack->top->prev;
    stack->size--;
    return data;
}
void* linkedstack_top(linkedstack stack) {
    if (!stack || !stack->top)
        return NULL;
    return stack->top->data;
}
unsigned linkedstack_size(linkedstack stack) {
    if (!stack)
        return 0;
    return stack->size;
}

Note que a quantidade de código é relativamente pequena. Cada conjunto de dados tem seu próprio conjunto de funções, e o acesso aos dados é feito exclusivamente através dessas funções.

A menor quantidade de código, e o encapsulamento do código e dos dados, faz com que a manutenção do sistema seja simplificada, reduzindo o tempo de manutenção e aumentando a estabilidade do código.

O arquivo também está disponível no git.

Testando a Pilha

Vamos fazer um programinha que utilize a pilha que acabamos de criar:

#include "linkedstack.h"
#include <stdio.h>
int main() {
    linkedstack stack = linkedstack_new();
    int ct = 0;
    int *p = NULL;
    printf("pushing...\n");
    for (ct = 10; ct--; ) {
        printf("%d ", ct);
        p = malloc(sizeof(int));
        *p = ct;
        linkedstack_push(stack, p);
    }

    printf("\nstack size: %d\n", linkedstack_size(stack));
    printf("stack top: %d\n", *(int*)linkedstack_top(stack));
    printf("popping...\n");
    for (; p = linkedstack_pop(stack); ) {
        printf("%d ", *p);
        free(p);
    }
    printf("\nstack size: %d\n", linkedstack_size(stack));
    linkedstack_delete(stack);
}

Que irá retornar a seguinte saída:

pushing...
9 8 7 6 5 4 3 2 1 0
stack size: 10
stack top: 0
popping...
0 1 2 3 4 5 6 7 8 9
stack size: 0

Indicando que tudo funcionou conforme esperado.

No próximo post vamos trazer o mesmo exemplo implementado com orientação a objetos.

Tags: c, estruturas de dados