6PILHA
637 palavras
3 páginas
PROGRAMAÇÃO
CIENTÍFICA II
Prof. André Quintiliano
1
ROTEIRO
•
Pilha de Arranjo
•
Pilha Encadeada
2
PILHA
•
São listas onde a inserção de um novo item ou a remoção de um item já existente se dá em uma única extremidade, no topo.
•
Os itens são colocados um sobre o outro. O item inserido mais recentemente está no topo e o inserido menos recentemente no fundo.
•
O último item inserido é o primeiro item que pode ser retirado da lista. São chamadas listas lifo (“last-in, first-out”).
3
PILHA
Exclusões
Inserções
Consultas
Topo
PILHA
Base
4
APLICAÇÕES
•
Histórico de páginas visitadas em um navegador na
Web
•
Controle de Desfazer/Refazer ações em um editor de textos •
Encadeamento de chamadas a métodos ou funções em ambientes de execução, como em Pascal, C ou
Java
5
OPERAÇÕES
•
Criar uma pilha P vazia
•
Testar se P está vazia
•
Obter o elemento do topo da pilha (sem eliminar)
•
Inserir um novo elemento no topo de P (empilhar/push)
•
Remover o elemento do topo de P (desempilhar/pop)
6
IMPLEMENTAÇÕES
•
Existem várias opções de estruturas de dados que podem ser usadas para representar pilhas.
•
As duas representações mais utilizadas são as implementações por meio de arranjos e de apontadores. 7
ARRANJOS
•
Os itens da pilha são armazenados em posições contíguas de memória.
•
Como as inserções e as retiradas ocorrem no topo da pilha, um ponteiro chamado topo é utilizado para controlar a posição do item no topo da pilha. a0 a1
a2
0
1
2
...
TAMANHO -1
topo
public class Pilha { private int capacidade; private No pilha[]; private int topo = -1;
}
public class No { private int valor;
}
8
OPERAÇÕES NA PILHA DE
ARRANJO
public interface interfacePilhaArranjo { void criarPilha(int tamanho); //cria pilha com tamanho boolean eCheia(); //verifica se a pilha estar cheia boolean eVazia(); //verifica se a pilha possui elementos int tamanho(); //retorna o número de itens da pilha
NoA push(int valor); //insere um valor no