6PILHA

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