Pilha

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Estruturas de Dados I
Pilhas e filas
Estudo de listas lineares especiais, com disciplina restrita de organização e de acesso a seus nodos
Estruturas de Dados I
Pilhas e filas
Disciplina restrita 
 acesso permitido somente em alguns nodos
Com disciplina restrita de organização e acesso a seus nodos
Listas lineares especiais
Estruturas de Dados I
Pilha
Listas lineares especiais
mais usuais
Pilhas e filas
Fila
 LIFO Last In First Out	
 	o último componente inserido 
 é o primeiro a ser retirado
 FIFO First In First Out 		 
 o primeiro componente inserido 
 é também o primeiro a ser retirado
Estruturas de Dados I
Consultas
Exclusões
Inserções
Topo
Base
Pilhas e Filas
Início
Final
Inserções
Exclusões
e
Consultas
PILHA
FILA
Estruturas de Dados I
Filas Duplas
exclusões
inserções
exclusões
inserções
Inserções e exclusões podem ocorrer em qualquer extremidade da lista
 Especialização de fila
Estruturas de Dados I
Pilhas e filas
Pilhas
Estruturas de Dados I
 Criar uma pilha vazia
 Inserir um nodo no topo da pilha
 Remover o nodo do topo de pilha
 Consultar / modificar nodo do topo da pilha
 Destruir a pilha
Operações sobre Pilhas
Pilhas
Estruturas de Dados I
 Pilhas
Pilhas implementadas por contiguidade física
Estruturas de Dados I
Pilha - contiguidade física 
Índices
do arranjo
Pilha – contiguidade física
 Implementada sobre um arranjo
 Índices de controle da pilha:
 BASE da pilha
 TOPO atual da pilha
 LIMITE máximo que pode ser ocupado pela pilha
Estruturas de Dados I
Exemplo de manipulação de uma pilha
LIM
TOPO
BASE
PILHA
10
9
8
7
6
5
4
3
2
1
3
LIM
TOPO
BASE
10
9
8
7
6
5
4
3
2
1
3
7
LIM
TOPO
BASE
10
9
8
7
6
5
4
3
2
1
3
7
5
LIM
TOPO
BASE
10
9
8
7
6
5
4
3
2
1
3
7
LIM
TOPO
BASE
10
9
8
7
6
5
4
3
2
1
Retorna “7”
1. Inicializar pilha de valores inteiros,a partir do índice 1, máximo 10 nós
2. Inserir nodo com valor 3
3. Inserir nodo com valor 7
4. Inserir nodo com valor 5
5. Remover nodo do topo
6. Consultar pilha
Pilha – contiguidade física
PILHA
PILHA
PILHA
PILHA
Estruturas de Dados I
Pilha – contiguidade física
TipoPilha = arranjo [1..N] de TipoNodo
Operações
Tipo de dados utilizado nos algoritmos para pilha implementada por contiguidade física:
 Criar uma pilha vazia
 Inserir um nodo no topo da pilha
 Remover o nodo do topo de pilha
 Consultar / modificar nodo do topo da pilha
Estruturas de Dados I
Lim
Topo
Base
Pilha
1. Definir valor do índice de BASE da pilha
2. Definir valor máximo de nodos que a pilha pode ter  LIM
3. Indicar que a pilha está vazia através do valor de TOPO
10
9
8
7
6
5
4
3
2
1
Exemplo:
Base  1
Topo  Base – 1
Lim  6 
Criação da pilha
Pilha – contiguidade física
Estruturas de Dados I
Algoritmo InicializarPilhaArr 
 Entrada: Base (inteiro)
 Saída: Topo (inteiro)
início
 Topo  Base – 1
fim 
Algoritmo: 
Inicializar Pilhas implementada sobre Arranjo
Pilha – contiguidade física
Estruturas de Dados I
Lim
Topo
Base
Pilha
10
9
8
7
6
5
4
3
2
1
Lim
Topo
Base
Pilha
10
9
8
7
6
5
4
3
2
1
Operação PUSH
Inserção de um nodo na pilha
Pilha – contiguidade física
Estruturas de Dados I
Pilha – contiguidade física
Algoritmo: 
Inicializar Pilhas implementada sobre Arranjo
Algoritmo InserirPilhaArr 
 Entradas: Pilha (TipoPilha)
 Lim (inteiro) 
 Topo (inteiro)
 Valor (TipoNodo)
 Saídas: Pilha (TipoPilha)
 Topo (inteiro) 
 Sucesso (lógico)
início
 se Topo < Lim 
 então início
 Topo  Topo + 1
 Pilha[Topo]  Valor
 Sucesso  verdadeiro
 fim
 senão Sucesso  falso
fim 
Estruturas de Dados I
Lim
Topo
Base
Pilha
10
9
8
7
6
5
4
3
2
1
Operação POP
Pilha – contiguidade física
Remoção de um nodo da pilha
Estruturas de Dados I
Algoritmo RemoverPilhaArr 
 Entradas: Pilha (TipoPilha)
 Topo (inteiro) 
 Base (inteiro) 
 Saídas: Pilha (TipoPilha)
 Topo (inteiro) 
 Sucesso (lógico)
 ValorRemovido (TipoNodo)
início
 se Topo  Base 
 então início
 ValorRemovido  Pilha[Topo]
 Topo  Topo - 1
 Sucesso  verdadeiro
 fim
 senão Sucesso  falso
fim 
Algoritmo: Remover nodo do topo de Pilha implementada sobre Arranjo
Estruturas de Dados I
?
Lim
Topo
Base
Pilha
10
9
8
7
6
5
4
3
2
1
Pilha – contiguidade física
Acesso à pilha
 Somente ao nodo do topo da pilha
 Para consulta e/ou modificação
Estruturas de Dados I
Algoritmo ConsultarPilhaArr 
 Entradas: Pilha (TipoPilha)
 Base (inteiro) 
 Topo (inteiro)
 Saídas: Valor (TipoNodo)
 Sucesso(lógico)
início
 se Topo  Base 
 então início
 Valor  Pilha[Topo]
 Sucesso  verdadeiro
 fim
 senão Sucesso  falso
fim 
Algoritmo: Consultar nodo do topo de Pilha implementada sobre Arranjo
Estruturas de Dados I
 Pilhas
Pilhas implementadas por encadeamento
Estruturas de Dados I
PtPilha
Info Elo
Topo da pilha
Base da pilha
Endereço do topo da pilha
Pilha implementada por encadeamento
TipoNodo = registro
 Info: TipoInfo
 Elo: TipoPtNodo
 fim registro
Tipo de dados utilizado nos algoritmos:
Estruturas de Dados I
Pilha por encadeamento
Criação de pilha encadeada
 Pilha criada vazia
 Atribuir endereço nulo para apontador que contém o endereço do topo da pilha
Estruturas de Dados I
Algoritmo: 
Criar Pilha Encadeada
Pilha por encadeamento
Algoritmo CriarPilhaEnc 
 Entradas: -
 Saída: PtPilha (TipoPtNodo)
início
 PtPilha  nulo
fim 
Estruturas de Dados I
Topo
Inserção de um nodo em pilha encadeada
Topo
Pilha por encadeamento
 Novo nodo inserido sempre no topo da pilha
PtPilha
PtPilha
Topo
Novo nodo
Base
Base
Estruturas de Dados I
Algoritmo InserirPilhaEnc 
 Entradas: PtPilha (TipoPtNodo)
 	 Valor (TipoInfo)
 Saída: PtPilha (TipoPtNodo)
 Variável local: PtNovo (TipoPtNodo)
início
 alocar(PtNovo)
 PtNovo.Info  Valor
 PtNovo.Elo  PtPilha
 PtPilha  PtNovo
fim 
Algoritmo: 
Inserir nodo em Pilha Encadeada
Pilha por encadeamento
Estruturas de Dados I
PtPilha
Topo
Remoção de um nodo de uma pilha encadeada
Pilha por encadeamento
Topo
PtPilha
Base
Base
 Só pode ser removido o nodo do topo da pilha
Nodo a ser removido
Estruturas de Dados I
Pilha por encadeamento
Algoritmo: 
Remover nodo de Pilha Encadeada
Algoritmo RemoverPilhaEnc 
 Entrada: PtPilha (TipoPtNodo) 
 Saídas: PtPilha (TipoPtNodo)
 Sucesso (lógico)
 Variável local: PtAux (TipoPtNodo)
início
 se PtPilha  nulo
 então início
 PtAux  PtPilha
 PtPilha  PtPilha.Elo
 liberar(PtAux)
 Sucesso  verdadeiro
 fim
 senão Sucesso  falso
fim 
Estruturas de Dados I
Acesso à pilha encadeada 
Pilha por encadeamento
 Só pode ser acessado o nodo do topo da pilha
Topo
PtPilha
Base
Nodo que pode ser acessado
Estruturas de Dados I
Pilha por encadeamento
Algoritmo: 
Consultar nodo do topo de Pilha Encadeada
Algoritmo ConsultarPilhaEnc 
 Entrada: PtPilha (TipoPtNodo) 
 Saídas: Valor (TipoInfo)
 Sucesso (lógico) 
início
 se PtPilha = nulo
 então Sucesso  falso
 senão início
 Sucesso  verdadeiro
 Valor  PtPilha.Info 
 fim
fim 
Estruturas de Dados I
Pilha por encadeamento
Algoritmo: Desempilhar
Consulta nodo do topo da pilha, e o remove da pilha
Algoritmo Desempilhar 
 Entrada: PtPilha (TipoPtNodo)
 Saídas: PtPilha (TipoPtNodo)
 Valor (TipoInfo)
 Sucesso (lógico) 
 Variável local: PtAux (TipoPtNodo)
início
 se PtPilha = nulo
 então Sucesso  falso 
 senão início
 Sucesso  verdadeiro
 Valor  PtPilha.Info
 PtAux  PtPilha
 PtPilha  PtPilha.Elo
 liberar(PtAux)
 fim
fim 
Estruturas de Dados I
PtPilha = nil
Base
Topo
Base
Topo
Base
Topo
Base
Topo
PtPilha
PtPilha
PtPilha
Destruição de uma pilha encadeada 
Pilha por encadeamento
 Liberar espaço ocupado pelos nodos, sempre a partir do topo da pilha
 No final: apontador para o topo = endereço nulo
Estruturas de Dados I
Pilha por encadeamento
Algoritmo: 
Destruir Pilha Encadeada
Algoritmo DestruirPilhaEnc 
 Entrada: PtPilha (TipoPtNodo)
 Saída: PtPilha (TipoPtNodo)
 Variável local: PtAux (TipoPtNodo)
início
 enquanto PtPilha ≠ nulo
 faça início
 PtAux  PtPilha
 PtPilha  PtPilha.Elo
 liberar(PtAux)
 fim
fim 
*
*
*