Pilha
Pilha
Uma pilha é uma estrutura de dados dinâmica na qual novos elementos são
sempre inseridos no topo da pilha e acessados somente pelo topo.
- O único elemento que pode ser acessado e removido é o do topo;
- Elementos são retirados na ordem inversa à ordem em que foram colocados;
- O primeiro que sai é o último que entrou (LIFO - last in, first out)
Pilha
Operações básicas:
- Empilhar (push) um novo elemento, inserindo-o no topo;
- Desempilhar (pop) um elemento, removendo-o do topo;
Pilha
Operações básicas:
- Empilhar (push) um novo elemento, inserindo-o no topo;
- Desempilhar (pop) um elemento, removendo-o do topo;
Pilha
Operações básicas:
- Empilhar (push) um novo elemento, inserindo-o no topo;
- Desempilhar (pop) um elemento, removendo-o do topo;
Pilha
Operações básicas:
- Empilhar (push) um novo elemento, inserindo-o no topo;
- Desempilhar (pop) um elemento, removendo-o do topo;
Pilha
Operações básicas:
- Empilhar (push) um novo elemento, inserindo-o no topo;
- Desempilhar (pop) um elemento, removendo-o do topo;
Pilha
Operações básicas:
- Empilhar (push) um novo elemento, inserindo-o no topo;
- Desempilhar (pop) um elemento, removendo-o do topo;
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Pilha
Uma estrutura do tipo Pilha pode ser implementada como Vetor ou Lista
Encadeada:
Vetor:
Lista Encadeada:
Interface do tipo abstrato Pilha: pilha.h
Função pilha_cria:
- aloca dinamicamente a estrutura da pilha;
- inicializa seus campos e retorna seu ponteiro;
Funções pilha_push e pilha_pop:
- inserem e retiram, respectivamente, um valor real na pilha;
Função pilha_vazia:
- informa se a pilha está ou não vazia;
Função pilha_libera:
- destrói a pilha, liberando toda a memória usada pela estrutura.
Interface do tipo pilha
/* TAD: pilha de valores reais (float) */
typedef struct pilha Pilha;
/* Tipo Pilha, definido na interface, depende da implementação do struct pilha */
Pilha* pilha_cria (void);
void pilha_push (Pilha* p, float v);
float pilha_pop (Pilha* p);
int pilha_vazia (Pilha* p);
void pilha libera (Pilha* p);
Implementação de pilha com VETOR
- Vetor (vet) armazena os elementos da pilha;
- Elementos inseridos ocupam as primeiras posições do vetor;
- Elemento vet[n-1] representa o elemento do topo.
#elemento vet [n-1] representa o elemento do topo
#define N 50 /* número máximo de elementos */
struct pilha {
int topo; /* vet [topo]: primeira posição livre do vetor */
float vet [N]; /* vet [topo-1]: topo da pilha */
/* vet [0] a vet [N-1]: posições ocupáveis */
};
Implementação de pilha com VETOR
Função pilha_cria:
- aloca dinamicamente um vetor;
- inicializa a pilha como sendo vazia (isto é, com o número de elementos igual a
zero);
Pilha* pilha_cria () tipo Pilha:
{
definido na interface
Pilha* p = (Pilha*) malloc(sizeof (Pilha));
if (p==NULL) exit (1);
struct pilha:
p->topo = 0; /* inicializa com zero elementos */ determina a implementação
return p;
}
Implementação de pilha com VETOR
Função pilha_push:
- Insere um elemento na pilha;
- Usa a próxima posição livre do vetor, se houver;
void pilha_push (Pilha* p, float v)
{
if (p->topo == N) { /* capacidade esgotada /*
printf("Capacidade da pilha estourou.\n");
exit(1); /* aborta programa */
}
/* insere elemento na próxima posição livre */
p->vet [p->topo] = v;
p->topo++;
}
Implementação de pilha com VETOR
Função pilha_pop:
- Retira o elemento do topo da pilha, retornando o seu valor;
- Verificar se a pilha está ou não vazia;
float pilha_pop (Pilha* p)
{
float v;
if (pilha_vazia (p)) {
printf("Pilha vazia.\n");
exit(1); /* aborta programa */
}
/* retira elemento do topo */
v = p->vet [p->topo-1];
p->topo--;
return v;
}
Implementação de pilha com VETOR
Função pilha_vazia:
- Retorna 1, se a pilha está vazia, ou 0, caso contrário;
int pilha_vazia (Pilha* p) {
if (p->topo == 0)
return 1;
return 0;
}
Implementação de pilha com VETOR
Função pilha_libera:
- Libera todos os elementos da lista e depois libera a pilha;
float pilha_libera (Pilha* p) { // vetor de float
free(p);
}
void pilha_libera (Pilha* p) { // vetor de ponteiros
int i;
for (i=0; i < p->topo; i++){
free(p->vet[i]);
}
free(p);
}
Implementação de pilha com Lista
Implementação de pilha com lista
- Elementos da pilha armazenados na lista
- Pilha representada por um ponteiro para o primeiro nó da lista;
/* nó da lista para armazenar valores reais */
struct elemento {
float info;
struct elemento *prox;
};
typedef struct elemento Elemento;
/* estrutura da pilha */
struct pilha {
Elemento* topo; /* aponta para o topo da pilha */
}
Implementação de pilha com Lista
função pilha_cria:
- cria e aloca a estrutura da pilha;
- inicializa a lista como sendo vazia;
Pilha* pilha_cria (void)
{
Pilha* p = (Pilha*) malloc(sizeof (Pilha));
if (p==NULL) exit(1);
p->topo = NULL;
return p;
}
Implementação de pilha com Lista
função pilha_push:
- Insere novo elemento n no início da lista;
void pilha_push (Pilha* p, float v) {
Elemento* n = (Elemento*) malloc(sizeof (Elemento));
if (n= NULL) { /* memória esgotada */
printf("Sem memória para alocar elemento.\n");
exit(1); /* aborta programa
}
/* insere elemento na próxima posição livre */
n->info = v;
n->prox = p->topo;
p->topo = n;
}
Implementação de pilha com Lista
float pilha_pop (Pilha* p) {
função pilha_pop: Elemento* t;
- Retira o elemento do início da lista; float v;
if (pilha_vazia (p))
{
printf("Pilha vazia.\n");
exit(1); /* aborta programa */
}
/* retira elemento do topo */
t = p->topo;
v = t->info;
p-> topo = t->prox;
free (t);
return v;
}
Implementação de pilha com Lista
Função pilha_libera:
- Libera todos os elementos da lista e depois libera a pilha;
void pilha_libera (Pilha* p) {
Elemento *t, *q = p->topo;
while (q!=NULL) {
t = q->prox;
free (q);
q = t;
}
free (p);
}
Implementação de pilha com Lista
Função pilha_vazia:
- Retorna 1, se a pilha está vazia, ou 0, caso contrário;
int pilha_vazia (Pilha* p) {
if (p->topo == NULL)
return 1;
return 0;
}