Contato

  • Jean Paulo Martins (jeanmartins utfpr edu br)
  • Sala 105, Bloco S (UTFPR - Campus Pato Branco)

Conteúdo

Pilhas usando um container abstrato

Em princípio, não há problemas em utilizar as funções de vector para implementar as funcionalidades de stack. Muito pelo contrário, reuso de funções é um dos objetivos da programação estruturada.

No entanto, como mencionado anteriormente, pilhas podem ser implementadas sobre diferentes contêiners. A nossa versão atual, porém, está totalmente acoplada ao contêiner vector.

stack-vector

Como podemos eliminar essa limitação e tornar nossa implementação mais geral ainda? De modo que outros contêiners sequenciais (list, por exemplo) também pudessem ser facilmente utilizados quando necessário. A ideia é introduzir uma interface entre a implementação de um contêiner e sua definição.

stack-container

Essa interface nada mais é do que um arquivo que define todas as funcionalidades que as implementações devem ter para serem um contêiner. Tais arquivos, em geral, contém apenas cabeçalhos de funções e possivelmente definições de tipos de dados.

// **** container.h ****
#define Type int
typedef struct _container container;
// Funções de remoção de elementos
Type pop_back(container* v);
Type pop_front(container* v);
Type erase(container* v, int i);
// Funções de inserção de elementos
void insert(container* v, Type value, int i);
void push_back(container* v, Type value);
void push_front(container* v, Type value);
Type* at(container* v, int pos);
void set(container* v, int pos, Type value);
Type get(container* v, int pos);
void print(container* v, const char* format);

Dada uma interface que define um contêiner genérico (abstrato), podemos redefinir nossa estrutura stack para que ela utilize essas funções, ao invés daquelas específicas de vector.

// **** stack.c ****
#include "container.h"
// Redefinir o nome vector
typedef container stack;
// Alocação desalocação
stack* new_stack(int initial_capacity) {
    container* s = new_container(initial_capacity);
    return s;
}
void free_stack(stack* v){
    free_container(v);
}
// Inserção e remoção de elementos
Type stack_pop(stack* v) {
    return pop_back(v);
}
void stack_push(stack* v, Type value) {
    push_back(v, value);
}
// Retorna um ponteiro para o topo da pilha
Type* stack_top(stack* v) {
    return at(v, 0);
}

Implementação da interface container.h

Até este momento a implementação de stack não existe de forma concreta, pois ela depende da implementação de funções que não foram implementadas em container.h.

Como já mencionado anteriormente, podem existir diferentes implementações da mesma interface. Qual delas será utilizada por stack.c é uma decisão feita durante a compilação.

Suponhamos a existência de duas implementações de container.h, a primeira em vector.c e a segunda em list.c. Ao passarmos uma das duas ao compilador, elas fornecerão a implementação das funções abstratas utilizadas em stack.c.

gcc main.c stack.c vector.c -o main-vector

gcc main.c stack.c list.c -o main-list