Exercicio de pilha em adt. - C/C#/C++ - Clube do Hardware
Exercicio de pilha em adt.
Por KXSY, 6 de abril em C/C#/C++
Eu fiz esse programa hoje e resolvi compartilhar.
É basicamente uma pilha simples em ADT(Abstract data type).
/* Deixa as declarações da biblioteca pilha privadas para esse arquivo. */
#define PIL_PRIVADO
#define T_NOME 50
#define T_AUX 80
unsigned char idade;
}pessoa_t;
void PressEnter(void);
void RetiraCarriage(char *s);
void DestroiPessoa(pessoa_t *p);
pessoa_t *CriaPessoa(const char *nome, const int idade);
int cont,quant;
char nome[T_NOME],aux[T_AUX],tecla;
pilha_t *pilha;
pessoa_t *pessoa;
/* Pega a quantidade de pessoas */
printf("\nDigite a quantidade de pessoas a ser cadastradas no sistema:\t");
scanf("%i%*c",&quant);
if(quant<=0)
printf("\nQuantidade invalida!");
}while(quant<=0);
pilha=PIL_Cria(quant);
if(pilha==NULL)
for(cont=0; cont<quant; cont++)
/* Pega as informações da pessoa */
/* Pega o nome da pessoa */
printf("\nDigite o nome da pessoa:\t");
fgets(nome,T_NOME,stdin);
RetiraCarriage(nome);
if(strlen(nome)<=2)
printf("\nNome invalido!");
}while(strlen(nome)<=2);
/* Pega a idade */
printf("\nDigite a idade da pessoa:\t");
fgets(aux,T_AUX,stdin);
RetiraCarriage(aux);
/* Passa de string para inteiro */
if(sscanf(aux,"%hhu",&idade)==EOF)
printf("\nValor invalido!");
}while(sscanf(aux,"%hhu",&idade)==EOF);
printf("\nNome:\t%s\nIdade:\t%hhu",nome,idade);
printf("\nO nome e a idade da pessoa está correto\nS/N:\t");
scanf("%c%*c",&tecla);
}while(toupper(tecla)=='N');
pessoa=CriaPessoa(nome,idade);
if(PIL_Coloca(pilha,pessoa)==1)
printf("\nSalva as informações em arquivo\nS/N:\t");
if(toupper(tecla)=='S')
printf("\nDigite o nome do arquivo:\t");
arq=fopen(nome,"w+");
printf("\nErro ao abrir o arquivo.");
pessoa=PIL_Retira(pilha);
if(pessoa==NULL)
fprintf(arq,"Nome:\t%s\nIdade:\t%hhu\n",pessoa->nome,pessoa->idade);
DestroiPessoa(pessoa);
printf("\nArquivo gravado com sucesso!");
while(PIL_EstaVazia(pilha)==0)
if(pessoa!=NULL)
printf("\nDados descartados.\n");
PIL_Destroi(pilha);
/* Trata erros */
/*EndERRO*/
void PressEnter(void)
printf("\nPressione enter para continuar.\n");
void RetiraCarriage(char *s)
for(cont=0; s[cont]!='\n'&&s[cont]!='0'; cont++);
s[cont]='\0';
void DestroiPessoa(pessoa_t *p)
pessoa_t *CriaPessoa(const char *nome, const int idade)
pessoa_t *pessoa=malloc(sizeof(pessoa_t));
pessoa->idade=idade;
strcpy(pessoa->nome,nome);
return(pessoa);
/* Define a biblioteca como privada
* ao arquivo que a declara
#ifdef PIL_PRIVADO
#define PIL_API static
#define PIL_API
struct Pilha;
typedef struct Pilha pilha_t;
/* Destrói a pilha.
* Essa função não se importa com o conteúdo da pilha.
PIL_API void PIL_Destroi(pilha_t *p);
/* Cria uma pilha.
* tam é o tamanho da pilha.
* retorna NULL em caso de falha.
PIL_API pilha_t *PIL_Cria(int tam);
/* Checa se a pilha está vazia.
* Retorna 1 se estiver é 0 se estiver cheia.
PIL_API int PIL_EstaVazia(pilha_t *p);
/* Checa se a pilha está cheia.
* Retorna 1 se estiver é 0 se estiver vazia.
PIL_API int PIL_EstaCheia(pilha_t *p);
/* Coloca informações na pilha
* Retorna 0 em caso de sucesso e 1 em caso de falha.
PIL_API int PIL_Coloca(pilha_t *p, void *info);
/* Retira informações da pilha.
PIL_API void *PIL_Retira(pilha_t *p);
/* Pega a informação da pilha sem retirá-la da pilha.
PIL_API void *PIL_Pega(pilha_t *p);
/* Definição da estrutura */
void **pilha;     /* Guarda os endereços */
unsigned short tamanho,posicao;
PIL_API void PIL_Destroi(pilha_t *p)
free(p->pilha);
PIL_API pilha_t *PIL_Cria(int tam)
pilha_t *p=malloc(sizeof(pilha_t));
p->pilha=malloc(sizeof(void*)*tam);
free(p);    /* Remove o ponteiro p */
p->tamanho=tam;
p->posicao=0;
PIL_API int PIL_EstaVazia(pilha_t *p)
if(p->posicao<=0)
PIL_API int PIL_EstaCheia(pilha_t *p)
if(p->posicao>=p->tamanho)
PIL_API int PIL_Coloca(pilha_t *p, void *info)
/* Checa se há espaço na pilha */
if(PIL_EstaCheia(p)==0)
/* Coloca a informação na pilha */
p->pilha[p->posicao]=info;
p->posicao++;
PIL_API void *PIL_Retira(pilha_t *p)
/* Checa se a pilha está cheia */
if(PIL_EstaVazia(p)==0)
/* Retira a informação da pilha */
p->posicao--;
return(p->pilha[p->posicao]);
PIL_API void *PIL_Pega(pilha_t *p)
return(p->pilha[p->posicao-1]);     /* Pega a informação se retirar da pilha */
Agora uma pergunta que vem na minha mente. é será que e difícil chamar isso (a biblioteca) em C++?
ADT para quem não conhece C patterns.
Foi mal ai não seguir com os nomes padrões (push and pop).
fonte compactado pilha.zip
arfneto 979
Foi mal ai não seguir com os nomes padrões (push and pop)
Nem push() nem pop() nem peek()
Muito bom ter se preocupado em manter a estrutura genérica e ter resistido a colocar atributos de dados na estrutura.
Usar (void*) para um item de dados é o mais importante. Ou a estrutura deixa de ser abstrata e útil afinal.
Eu gostaria de poder declarar como
Pilha  pessoas;
Pilha* acesso;
Pilha  muitas_pilhas[20];
Pilha* pratos = NULL;
E não o contrário:
pilha_t* pilha;
Mas entendo que use essa convenção de sufixos.
Se optou por tamanho fixo podia oferecer uma maneira de mudar o tamanho. Parece um pouco restritivo na prática. E usar na struct Pilha um void **pilha foi uma decisão curiosa.
Quando apaga a pilha não deveria antes apagar os elementos presentes? Confesso que não li com atenção.
Usar em C++ não teria dificuldades. Apenas definir se vai usar como estático ou DLL e declarar certo para o linker e para o compilador enxergar os includes. Talvez tenha que usar extern "C" nas declarações no programa em C++.
No entanto pode não ser muito útil. Em geral STL é muito rápido e o container stack --- a pilha --- também é. Então provavelmente seria mais fácil declarar e usar como
unsigned int idade;
Pessoa() { nome = ""; idade = 0; };
Pessoa(string nome, unsigned int idade) : nome(nome), idade(idade) {};
stack <Pessoa> Pilha;
if (Pilha.empty()) cout << "pilha vazia agora" << endl;
Pessoa um("um", 20);
Pessoa dois("dois", 5);
Pilha.push(um);
Pilha.push(dois);
cout << Pilha.size() << " na pilha agora" << endl;
if ( ! Pilha.empty())
cout << "pilha nao esta mais vazia" << endl;
17 horas atrás, arfneto disse:
Se optou por tamanho fixo podia oferecer uma maneira de mudar o tamanho. Parece um pouco restritivo na prática.
Fiz pensando na pilha da era pcdos, em que a pilha crescia de cima para baixo. mas desisti de implementar igual a um ibm pc.
Quando apaga a pilha não deveria antes apagar os elementos presentes?
Isso atrapalharia no fator herança (eu acho que programei demais com objetos), sendo mais interessante o próximo objeto implementar essa função.
No entanto pode não ser muito útil.
Pois é, eu já tinha visto que em C++ tem a biblioteca boost e o stl que torna esse meu algorítimo bem inútil olhando pelo lado do C++.
A minha única duvida mesmo é como seria chamar a biblioteca e a encapsular em um objeto. Mas acabei de ver que seria uma coisa trivial.
Eu postei o código ontem e não reparei que tinha postado o que eu estava testando anteriormente, então eu acabei fazendo algumas correções na postagem e coloquei os arquivos para download compactados.
ligeiramente OFF TOPIC
Vou comentar sobre isso de estruturas e talvez teoria sobre orientação a objetos aqui um pouco mais porque tenho visto que é difícil ver exemplos dessas coisas em português e comentados e tal. E como isso aparece, claro, nas pesquisas então pode ser útil a outras pessoas.
Foi numa busca que eu acabei lendo um post deste forum pela primeira vez afinal.
Espero que os amigos moderadores compreendam
Fiz pensando na pilha da era pcdos, em que a pilha crescia de cima para baixo. mas desisti de implementar igual a um ibm pc
Não sei se entendo o que quer dizer com isso. Estruturas de Dados é um campo de estudo que precede em muito o IBM PC. Ou qualquer PC
Não consigo imaginar o que seria "a maneira ibm pc de implementar uma pilha" e nunca imaginei que uma marca de computador ou uma "era pcdos" caracterizariam uma estrutura de dados
Eis que posso dizer: a disciplina de retirada de dados numa estrutura como a pilha é classificada como FIFO ou LIFO. Esses termos vem de "FIrst in First Out" e "Last In First Out"
O que você implementou com relativo sucesso é a disciplina LIFO em que você retira da pilha o último objeto inserido: ultimo que entra é o primeiro que sai, como na abreviatura em inglês. E é mais condizente com a noção de pilha no mundo concreto, a tal pilha de pratos, a tal pilha de cartas de baralho, os exemplos mais comuns dos livros de estruturas de dados
A outra disciplina para retirar os dados da pilha --- FIFO --- é muito mais útil e comum, e é a noção clássica de fila no mundo concreto. Está disponível em C++ na classe queue ou em java na interface Queue, que é implementada por uma legião de classes. Para citar as mais comuns, PriorityQueue e LinkedList. Como vê, a pilha FIFO é bem mais usada: LinkedList é uma fila, e faz sentido. E em java as listas ligadas são implementadas através de uma pilha FIFO.
Não se trata do jeito pcdos ou ibm de implementar esses modelos abstratos.
E de acordo com o objetivo de orientação a objetos não faz diferença se a pilha cresce para cima ou para baixo. Trata-se do encapsulamento: você pode implementar como achar melhor.
Isso atrapalharia no fator herança (eu acho que programei demais com objetos), sendo mais interessante o próximo objeto implementar essa função
Não entendo o que quer dizer com isso também. Como atrapalharia a herança? Como seria mais interessante o próximo objeto TER que implementar (corrigir) uma classe? Quem garante que vai existir um próximo objeto? Em que linguagem "programou demais com objetos"? Nesses casos você declararia a classe como abstrata. Não em C. Vou explicar:
Apagando os ponteiros para a raiz da pilha sem liberar antes a memória alocada para cada elemento dos dados simplesmente leva a um vazamento de memória. É apenas um bug. Sua classe seria excluída de qualquer ambiente assim que isso fosse identificado. E não ia demorar nadinha.
Nada tem a ver com herança.
Entenda: a noção de herança envolve encapsulamento da classe herdada e não a complementação dela em algo tão importante quanto alocar ou liberar memória
Herança ou derivação significa especialização
Uma classe derivada de pilha_t pode sempre (quase sempre) estender métodos de pilha_t, e redefinir métodos e propriedades que ache importantes. E você poderia declarar esses métodos de pilha_t como virtuais de modo que mesmo um ponteiro para a classe base saberia como chamar a função certa.
Todo método pode ser redefinido pela classe herdada, a princípio, mas apenas métodos explicitamente declarados virtuais podem ser chamados corretamente a partir de ponteiros para a classe base. A classe derivada simplesmente escreve outros métodos onde for importante. Isso se chama override.
Falando em termos de classes, que é o caso aqui: É bem possível que uma classe não tenha informação suficiente para executar uma operação importante, talvez "sendo mais interessante o próximo objeto implementar essa função"
Isso se chama classe abstrata em termos OOP. E se está acostumado com isso como disse sabe que isso se implementa em java ou C++ (ou seja lá qual for a linguagem que use) através do que se chama pure virtual functions, um nome pomposo e besta. Em C++ você simplesmente escreveria
PIL_API virtual void PIL_Destroi() = 0;
E passaria a bola.
A menos desse caso a implementação da classe não pode deixar nada contando com um eventual "próximo objeto". Isso contraria a própria noção de orientação a objetos
Se a classe é abstrata você não pode declarar uma instância dela
Em C não existe esse suporte, mas também não tem esse peso todo de uma linguagem gigante ou uma jvm
Claro que isso sempre foi resolvido em C. Como?
Você passa a responsabilidade de apagar os items para a "instância da classe". Nome disso? callBack ou hook ou sei lá como se chamam isso em português
Você escreveria algo em C como
PIL_API void PIL_Destroi(pilha_t* p, int(*f)(void*) )
O usuário de sua classe escreveria por exemplo uma função
int apaga_Pessoa( Pessoa* p );
Que ele mesmo escreveu e testou e sabe que apaga a Pessoa apontada por p.
Em muitos muitos casos na prática isso é absolutamente essencial porque os itens na lista --- ou na pilha, no heap, seja lá o que você implementou --- alocam memória e só quem escreveu a classe pode saber ao certo como apagar. Pode ter que ir ao banco de dados, acessar outras máquinas, o diabo. Para um estudante pode ser mesmo só um int. Mas na prática pode ser algo muito complexo.
E desconhecido por quem escreveu a pilha_t. Esse é o poder dos tais objetos.
E aí ao apagar a pilha de Pessoa ele chama
PIL_Destroi(pilha, apaga_Pessoa);
E é genial: sua rotina PIL_Destroi verifica se apaga_Pessoa é NULL e se for manda bala e apaga tudo. Estará errado, mas a culpa não será sua.
Se não for NULL você simplesmente chama (*f)((void*) Pessoa) para seu exemplo de Pessoa. Para cada item da pilha.
E se f() retornar algo diferente de 0 ou o que for esperado você cancela tudo, mostra umas mensagens, gera um log e se livra do problema.
O Windows funciona assim, javascript funciona assim, drivers funcionam assim... Na verdade essa construção é o método map() de javascript e java.
A minha única duvida mesmo é como seria chamar a biblioteca e a encapsular em um objeto. Mas acabei de ver que seria uma coisa trivial
A STL, Standard Template Library --- é a stdio.h do C++, e como já tem as classes stack e queue tornam difícil justificar uma implementação C dessas coisas a menos que seja muito rápida ou especializada.
Não é assim uma coisa trivial. É preciso, como eu disse, criar uma biblioteca --- lib no Windows --- ou uma DLL. E seguir vários passos. E na hora de rodar o programa a DLL tem que estar disponível se optou por esse modelo. E tem uns outros detalhes. Apenas poder abrir a lista de métodos no IDE ou até compilar o programa C++ não significa o fim do processo. A dor de cabeça pode vir no LINK. Ou na hora de rodar.
5 horas atrás, KXSY disse:
Eu postei o código ontem e não reparei que tinha postado o que eu estava testando anteriormente, então eu acabei fazendo algumas correções na postagem e coloquei os arquivos para download compactados