Pilha

Métodos Computacionais

Pilha

Definição de Pilha
Pilha é uma estrutura de dados dinâmica onde: Inserção e remoção de elementos no topo da pilha O primeiro elemento que sai é o último que entrou
(LIFO)
Operações básicas: push (empilhar) e pop
(desempilhar)

2

Funcionamento da pilha empilha(a) empilha(b)

empilha(c)

c b a

topo

a

topo

b a desempilha()

topo

c b a

topo

3

Exemplo de Uso: Pilha de Execução de
Funções
#include “stdio.h” int fat ( int n ) ; int main () { int n = 5, r ; r = fat(n) ; printf ( “ Fatorial return 0 ;
}
int fat ( int n ){ int f=1 ; while(n != 0) { f *= n ; n-- ;
}
return f ;
}

= %d \n ”,

r ) ;

4

Pilha de Execução
1 – Início do programa: pilha vazia

main>

2 – Declaração de variáveis: n,r

main>

r n 5

4 – Final do laço
Acesso às variáveis que estão na função do topo

f fat> n r n main> 120
0
5

3 – Chamada da função: empilha variáveis

n fat> r n main>

5
5

5 – Retorno da função: desempilha fat>

r n main>

120
5
5

Interface do tipo Pilha
Criar pilha vazia;
Inserir elemento no topo
(push)
Remover elemento do topo (pop)
Verificar se a pilha está vazia Liberar a estrutura de pilha Em C
/* pilha.h */ typedef struct pilha Pilha;
Pilha* pilha_cria(); void pilha_push(Pilha* p,float v); float pilha_pop(Pilha* p); int pilha_vazia(Pilha* p); void pilha_libera(Pilha* p);

6

Implementação do tipo Pilha
Existem várias implementações possíveis de uma pilha. Podem diferir da natureza dos elementos, maneira como são armazenados e operações disponíveis
Iremos estudar 2 tipos de implementação:
Utilizando Vetor
Utilizando Lista Encadeada

7

Implementando Pilha com Vetor
Estrutura que representa pilha deve ser composta por um vetor para armazenar os elementos e o número de elementos armazenados Vantagem

#define N 50 struct pilha { int n; float vet[N];
};

Simplicidade

Desvantagens
Deve-se saber de antemão o número máximo de elementos
Desperdício de espaço de memória

8

Implementando Pilha com Vetor
Função de Criação
typedef