No último post implementamos uma pilha usando lista ligada usando C, neste post vamos implementar a mesma pilha, mas utilizando orientação a objetos. O foco é na implementação correta da uma estrutura de dados, em primeiro lugar os dados, e depois o algoritmo que manipulam os dados.

Os dois posts em conjunto vão servir para ilustrar a importância da estrutura de dados sobre o algoritmo. No próximo post vamos discorrer um pouco mais sobre porque dar tanta importância aos dados e não ao algoritmo.

Vamos começar definindo a interface da classe, os dados e os métodos de acesso:

template <class T>
class CStack {
    protected:
        class CNode {
            public:
                T data;
                CNode *prev;
                CNode(T adata, CNode *aprev) : data(adata), prev(aprev) { };
        };

        unsigned size;
        CNode *topnode;

    public:
        CStack() : size(0), topnode(nullptr) { };
        ~CStack();

        void push(T adata);
        T pop();
        T top();
        unsigned getSize();
};

Comparando com a versão em C, foi utilizado um template <class T>, comparado com um ponteiro void da outra versão. Essa prática facilita muito a vida do programador, que não precisa lidar com ponteiros para utilizar a classe.

Além disso utilizamos uma classe protegida dentro da classe principal, afinal o programador não precisa de detalhes de como o armazenamento é implementado. Esse é o chamado encapsulamento de dados e código, método que faz com que a utilização da classe fique mais simples, reduz a manutenção do código, e melhor a estabilidade do sistema.

Também implementamos os mesmos métodos implementados na versão C ANSI.

O código da declaração da classe está disponível no git.

Implementando os Métodos

Vamos implementar os métodos de acesso aos dados:

#include "CStack.h"
template<class T> CStack<T>::~CStack() {
    while (topnode) {
        CNode *delnode = topnode;
        topnode = topnode->prev;
        delete delnode;
    }
}
template<class T> void CStack<T>::push(T adata) {
    CNode *newnode = new CNode(adata, topnode);
    topnode = newnode;
    size++;
}
template<class T> T CStack<T>::pop() {
    if (!topnode)
        return T();
    T data = topnode->data;
    CNode *delnode = topnode;
    topnode = topnode->prev;
    delete delnode;
    size--;
    return data;
}
template<class T> T CStack<T>::top() {
    if (!topnode)
        return T();
    return topnode->data;
}
template<class T> unsigned CStack<T>::getSize() {
    return size;
}

Note como a quantidade de código necessária também é pequena. Mesmo com a burocracia necessária para declarar o template. O arquivo também está disponível no git.

Testando a Pilha

O programa para testar a pilha em C++ é bem mais compacto:

#include <iostream>
#include "CStack.h"
int main() {
    CStack<int> stack;
    std::cout << "Pushing..." << std::endl;
    for (int ct = 10; ct--; ) {
        stack.push(ct);
        std::cout << ct << " ";
    }
    std::cout << std::endl << "Stack size: " << stack.getSize() << std::endl;
    std::cout << "Stack top: " << stack.top() << std::endl;
    std::cout << "Popping..." << std::endl;
    while (stack.getSize())
        std::cout << stack.pop() << " ";
    std::cout << std::endl << "Stack size: " << stack.getSize() << std::endl;
}

Aqui é possível notar uma das vantagens do C++, não há necessidade de se preocupar com ponteiros, toda a alocação de memória é gerenciada pela classe CStack e pelo compilador. O código fica mais compacto e mais fácil de manter. Claro que o código também está disponível do git.

No próximo post vamos discutir as vantagens do desenvolvimento centrado nos dados.

Tags: c++, estruturas de dados