Início › Disciplinas › IFSudeste › Algoritmos e ED › Tipos Abstratos de Dados › Pilhas

Pilhas

Publicado em por Igor Knop — Seja Você o Primeiro a Comentar! ↓
Share

Uma pilha, no sentido de empilhar, é um conjunto de elementos quaisquer dispostos uns sobre os outros de forma que só podemos incluir e retirar um elemento em seu topo. Caixas, livros, pratos, são exemplos físicos de elementos que são comumente empilhados. Em computação, o conceito de pilha (stack em inglês) é uma abstração onde podemos guardar e retirar elementos da estrutura de forma que o último elemento empilhado será o primeiro a ser desempilhado (LIFO – Last In, First Out: Último a entrar, primeiro a sair).

Várias estruturas de dados podem ser usadas para guardar os elementos mas duas únicas operações que inserem e removem elementos devem ser a empilhar() ou desempilhar() que são encontradas como push() e pop(), respectivamente.

O exemplo abaixo implementa uma pilha de caracteres através de um vetor. Usamos uma estrutura para guardas os dados e um campo inteiro topo que diz onde o próximo elemento deve ser armazenado. Através do valor de topo podemos saber quando a fila está cheia (não permitindo o empilhamento) ou vazia (não permitindo o desempilhamento).

#include <stdio.h>
struct SPilha{
	char dados[3];
	int topo;
};
typedef struct SPilha Pilha;
 
void empilha(Pilha *p, char c){
	if(p->topo >= 3 ){
		printf("Pilha cheia!\n");
		return;
	}
	p->dados[p->topo] = c;
	p->topo++;
}
char desempilha(Pilha *p){
	if(p->topo == 0){
		printf("Pilha vazia!\n");
		return 0;
	}
	p->topo--;
	return p->dados[p->topo];
}
int main(){
 
	Pilha stack;
	stack.topo = 0;
	empilha(&stack,'A');
	empilha(&stack,'B');
	empilha(&stack,'C');
	empilha(&stack,'D');
	printf("%c\n", desempilha(&stack));
	printf("%c\n", desempilha(&stack));
	printf("%c\n", desempilha(&stack));
	printf("%c\n", desempilha(&stack));
	return 0;
 
}

As duas funções encapsulam as operações de forma a sempre manter a coerência dos dados. Entretanto deve-se tomar cuidado para ao se criar a pilha pois o campo topo deve ser iniciado corretamente com 0. Outro problema é que a nossa pilha possui um tamanho fixo definido na estrutura em tempo de compilação.

Para evitar estes problemas podemos criar uma função responsável apenas por iniciar a lista corretamente e ao invés de usar um vetor usaremos alocação dinâmica para guardar os dados. O exemplo a seguir apresenta a estrutura alterada e a nova função. Observe que o programa principal usado para teste muda apenas na construção da estrutura.

#include <stdio.h>
#include <stdlib.h>
struct SPilha{
	char *dados;
	int topo;
	int tamanho;
};
typedef struct SPilha Pilha;
 
Pilha novaPilha(int n){
	Pilha p;
	p.topo = 0;
	p.tamanho = n;
	p.dados = malloc(n*sizeof(char));
	if(p.dados==NULL){
		printf("Sem memória!\n");
		exit(1);
	}
	return p;
}
void empilha(Pilha *p, char c){
	if(p->topo >= p->tamanho ){
		printf("Pilha cheia!\n");
		return;
	}
	p->dados[p->topo] = c;
	p->topo++;
}
char desempilha(Pilha *p){
	if(p->topo == 0){
		printf("Pilha vazia!\n");
		return 0;
	}
	p->topo--;
	return p->dados[p->topo];
}
int main(){
 
	Pilha stack = novaPilha(3);
	stack.topo = 0;
	empilha(&stack,'A');
	empilha(&stack,'B');
	empilha(&stack,'C');
	empilha(&stack,'D');
	printf("%c\n", desempilha(&stack));
	printf("%c\n", desempilha(&stack));
	printf("%c\n", desempilha(&stack));
	printf("%c\n", desempilha(&stack));
	return 0;
}

Podemos melhorar a função que retorna uma nova pilha pois há um problema de desempenho quando um grande conjunto de dados é gerado: o retorno faz uma cópia dos dados da estrutura. Para evitarmos esta cópia podemos trabalhar apenas com ponteiros para a pilha:

#include <stdio.h>
#include <stdlib.h>
struct SPilha{
	char *dados;
	int topo;
	int tamanho;
};
typedef struct SPilha Pilha;
 
Pilha *novaPilha(int n){
	Pilha *p;
	p = malloc(sizeof(Pilha));
	if(p==NULL){
		printf("Sem memória!\n");
		exit(1);
	}
	p->topo = 0;
	p->tamanho = n;
	p->dados = malloc(n*sizeof(char));
	if(p->dados==NULL){
		printf("Sem memória!\n");
		exit(1);
	}
	return p;
}
void empilha(Pilha *p, char c){
	if(p->topo >= p->tamanho ){
		printf("Pilha cheia!\n");
		return;
	}
	p->dados[p->topo] = c;
	p->topo++;
}
char desempilha(Pilha *p){
	if(p->topo == 0){
		printf("Pilha vazia!\n");
		return 0;
	}
	p->topo--;
	return p->dados[p->topo];
}
int main(){
 
	Pilha *stack = novaPilha(3);
	empilha(stack,'A');
	empilha(stack,'B');
	empilha(stack,'C');
	empilha(stack,'D');
	printf("%c\n", desempilha(stack));
	printf("%c\n", desempilha(stack));
	printf("%c\n", desempilha(stack));
	printf("%c\n", desempilha(stack));
	return 0;
 
}

Por último, podemos “aliviar” nosso programa de teste jogando as linhas de código para arquivos separados de forma a podermos reaproveitar esta solução em outros problemas. Para tanto vamos criar um arquivo de cabeçalho pilha.h e um arquivo com a implementação pilha.c e alterarmos nosso programa principal para ficar da seguinte forma:

#include <stdio.h>
#include <stdlib.h>
#include "pilha.h"
int main(){
 
	Pilha *stack = novaPilha(3);
	empilha(stack,'A');
	empilha(stack,'B');
	empilha(stack,'C');
	empilha(stack,'D');
	printf("%c\n", desempilha(stack));
	printf("%c\n", desempilha(stack));
	printf("%c\n", desempilha(stack));
	printf("%c\n", desempilha(stack));
	return 0;
 
}

O arquivo pilha.h fica com as definições das estruturas, tipos e assinaturas das funções:

struct SPilha{
	char *dados;
	int topo;
	int tamanho;
};
typedef struct SPilha Pilha;
 
Pilha *novaPilha(int n);
void empilha(Pilha *p, char c);
char desempilha(Pilha *p);

O arquivo pilha.c fica com a implementação das funções:

#include <stdio.h>
#include <stdlib.h>
#include "pilha.h"
Pilha *novaPilha(int n){
	Pilha *p;
	p = malloc(sizeof(Pilha));
	if(p==NULL){
		printf("Sem memória!\n");
		exit(1);
	}
	p->topo = 0;
	p->tamanho = n;
	p->dados = malloc(n*sizeof(char));
	if(p->dados==NULL){
		printf("Sem memória!\n");
		exit(1);
	}
	return p;
}
void empilha(Pilha *p, char c){
	if(p->topo >= p->tamanho ){
		printf("Pilha cheia!\n");
		return;
	}
	p->dados[p->topo] = c;
	p->topo++;
}
char desempilha(Pilha *p){
	if(p->topo == 0){
		printf("Pilha vazia!\n");
		return 0;
	}
	p->topo--;
	return p->dados[p->topo];
}

Para compilarmos agora precisamos passar todos os arquivos na linha de comando:

gcc pilhateste.c pilha.c -o pilhateste
Share

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

*