09_Pilhas

Prévia do material em texto

PILHAS ESTÁTICAS E DINÂMICASPILHAS ESTÁTICAS E DINÂMICAS
.: ESTRUTURA DE DADOS :..: ESTRUTURA DE DADOS :.
André Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo Santana
andremacedo@ufpi.edu.br
PilhasPilhas EstáticasEstáticas SequenciaisSequenciais
• Pilha é um conceito muito utilizado na Ciência da Computação. Consiste em uma
metáfora emprestada do mundo cotidiano para resolver muitos problemas de
forma simplificada, pois é uma estrutura muito simples e muito poderosa como
elemento básico de solução de problemas complexos;
• São estruturas lineares com disciplina de acesso;
ConceitosConceitos
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Uma Pilha é um caso especial de lista na qual as inserções e retiradas são feitas
em uma extremidade denominada topo, cujo critério de acesso é denominado
LIFO -Last In First Out;
• Em uma Pilha só se admite ter acesso ao elemento no topo da pilha, ou seja,
todas as inserções e/ou remoções são feitas por essa extremidade;
• Em outras palavras, uma Pilha é uma sequencia em que só o primeiro
componente é diretamente acessível;
Pilha Estática Sequencial
Procedimentos básicos:
• inicializar pilha;
• inserir um elemento - empilhar;
• excluir um elemento - desempilhar;
• acessar um elemento - topo;
EstruturaEstrutura e e OperaçõesOperações
PilhasPilhas EstáticasEstáticas SequenciaisSequenciais
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Antes de começar a carregar a Pilha com os dados é necessário declarar a
estrutura e inicializá-la. O processo de inicialização é realizado por uma função
que atribui o valor de -1 à variável topo;
• Outra função primitiva de pilha é a que realizar a tarefa de empilhar. Se a pilha
não estiver cheia, incrementamos a variável topo de uma unidade para indicar o
endereço em que será inserido o novo elemento;
OperaçõesOperações: : InserirInserir ouou EmpilharEmpilhar
PilhasPilhas EstáticasEstáticas SequenciaisSequenciais
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Outra função primitiva de pilha é a que realiza a tarefa de desempilhar, ou seja,
elimina o elemento que está no topo da pilha. Para tal, basta decrementar a
variável topo de uma unidade;
• Na área computacional existem inúmeras aplicações em Pilha:
• Caminhamento em árvores;
• Avaliação de expressões;
• Inversão de listas;
• Conversão de notações;
• Exemplo:
AplicaçõesAplicações
PilhasPilhas EstáticasEstáticas SequenciaisSequenciais
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Exemplo:
• (A+B) / (C+D)
• {A+[B-C]+[(A+C)/(B-C)]}
• Notações
Infixa Prefixa Posfixa
A-B+C +-ABC ABC+-
(A-B)/(C+D) /(-AB)(+CD) (AB-)(CD+)/
A*(B-C) -(* A)BC A(BC-)*
• Podemos implementar duas Pilhas em um só vetor. Basta que delimitemos onde
se iniciará a primeira e onde começará a seguinte. Assim, teremos várias pilhas
em um único vetor;
DuasDuas PilhasPilhas emem um um únicoúnico vetorvetor
PilhasPilhas EstáticasEstáticas SequenciaisSequenciais
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Pilha Estática com Encadeamento
Procedimentos básicos:
• inicializar pilha;
• inserir um elemento - empilhar;
• excluir um elemento - desempilhar;
• acessar um elemento - topo;
EstruturaEstrutura e e OperaçõesOperações
PilhasPilhas EstáticaEstática com com EncadeamentoEncadeamento
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• A função inicializar_pl() inicia a pilha atribuindo valores iniciais para as
variáveis topo e disp
OperaçõesOperações: : InicializarInicializar
PilhasPilhas EstáticaEstática com com EncadeamentoEncadeamento
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• O procedimento empilhar_pl() recebe o endereço da estrutura Pilha e o elemento
a ser inserido x.
OperaçõesOperações: : EmpilharEmpilhar
PilhasPilhas EstáticaEstática com com EncadeamentoEncadeamento
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• A rotina desempilhar_pl() retira o elemento do topo da pilha.
OperaçõesOperações: : DesmpilharDesmpilhar
PilhasPilhas EstáticaEstática com com EncadeamentoEncadeamento
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Como o elemento principal de uma Pilha é o topo, normalmente constrói-se
uma função para acessar o valor desse elemento.
OperaçõesOperações: : ConsultarConsultar TopoTopo
PilhasPilhas EstáticaEstática com com EncadeamentoEncadeamento
André M. Santana UFPI - CCN - DIEEstruturas de Dados
pilha.h
InterfaceInterface
PilhasPilhas DinâmicasDinâmicas com com EncadeamentoEncadeamento
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• A função criar_pl() aloca dinamicamente uma estrutura pilha, inicializa seus
campos e retorna seu ponteiro; as funções push() e pop() inserem e retiram,
respectivamente, um elemento da pilha; a função pilhavazia() informa se a
apilha está ou não vazia; e a função liberar_pl() destrói a pilha e libera toda a
memória usada pela estrutura;
FunçõesFunções
PilhasPilhas DinâmicasDinâmicas com com EncadeamentoEncadeamento
Criar uma pilha
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir elemento na pilha
Excluir elemento da pilha
FunçõesFunções
PilhasPilhas DinâmicasDinâmicas com com EncadeamentoEncadeamento
Testar se a pilha está vazia
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Liberar pilha
EXERCÍCIOSEXERCÍCIOS
PilhasPilhas
André M. Santana UFPI - CCN - DIEEstruturas de Dados