Buscar

Tema 2 - Pilha_parte02

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 20 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 20 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 20 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Listas 
Luciano Soler 
Listas - Definição 
 
 
Uma lista linear é um conjunto (coleção) de 
n>=0 nós (elementos) L1, L2, ..., LN tais que suas 
propriedades estruturais decorrem, unicamente, 
da posição relativa dos nós dentro da sequência 
linear (SZWARCFITER, 1994). 
Listas 
 Tem-se: 
 se n>0, L1 é o primeiro nó, 
 para 1 < k <= n, o nó Lk é precedido por Lk-1. 
 
 As operações mais frequentes em listas são: a busca, 
a inclusão e a remoção de um determinado elemento. 
essas operações podem ser efetuadas em qualquer 
posição da lista. 
 Se forem consideradas apenas operações restritas aos 
extremos da lista temos casos especiais de estruturas 
de dados amplamente utilizadas na solução de problemas. 
 
Listas 
LISTA 
PILHA 
Inserções, remoções 
e acessos são 
realizados em um 
único extremo 
FILA 
Todas as inserções 
são feitas num único 
extremo e todas 
remoções e acessos 
são realizados no 
outro. 
FILA DUPLA 
(DEQUE) 
Double- Ended-
Queue 
Fila de extremidade 
Dupla. 
Inserções, 
Remoções ou 
acessos são 
realizados em 
qualquer extremo. 
 
 
 FDER 
Fila Dupla de 
Entrada Restrita. 
Inserção restrita a 
um único extremo. 
FDSR 
Fila Dupla de Saída 
Restrita. Remoção 
restrita a um único 
extremo. 
Pilha - Definição 
 
Pilha é uma lista linear onde os elementos 
podem ser inseridos e removidos apenas de 
uma extremidade chamada de topo. Esta 
disciplina de acesso determina que “o último 
elemento que entra é o primeiro a sair” (LIFO 
– Last in First out). 
 
Pilha - Exemplos 
 Para que serve a PILHA? 
 Pilha serve para ordenar a entrada e saída de elementos. 
 
 Onde eu aplico PILHA? 
 A Pilha é aplicada na resolução de problemas onde a ordem de entra 
e saída dos elementos interfere no resultado final. 
 
 Exemplos 
 Ordem de abertura de janelas (linux, windows) 
 Inclusão de imagens do PowerPoint 
 Ctrl + Z 
 Voltar (navegadores) 
 Pilha de livros ou Pilha de pratos. 
Pilha 
http://www.cheeseandburger.com/ 
Pilha – Operações 
 Fundamentais 
 Empilhar (push) – Insere um elemento no topo da pilha 
 
 
 Se a implementação impuser limitação no espaço para a pilha é 
preciso verificar se a PILHA está CHEIA (erro de OVERFLOW) 
 
 Desempilhar (pop) – remove um elemento do topo da pilha 
 
 
 É preciso verificar se a PILHA está VAZIA (erro de UNDERFLOW) 
 B<TOPO> 
A <TOPO> A 
 B<TOPO> 
 A A <TOPO> 
Pilha 
Como executar as OPERAÇÕES? 
 
topo 
-1 
0 
1 
2 
3 
1) Indicar que a pilha esta vazia 
 
2) Inserir um elemento 
 
3) Retirar um elemento 
 
4) Retirar um elemento e visualizar o 
elemento retirado 
Inserir elemento 
 -1 
0 
1 
2 
3 
topo 
Insira os elementos 
 
A e B 
Inserir elemento 
 
-1 
0 
1 
2 
3 
topo 
topo = topo+1 
vetor[topo] = A 
Inserir elemento 
 
 
-1 
0 
1 
2 
3 
topo 
topo = topo+1 
vetor[topo] = B 
Inserir elemento 
 
 
-1 
0 
1 
2 
3 
topo 
Inserir elemento 
 
-1 
0 
1 
2 
3 
topo 
temp =vetor[topo] 
vetor[topo] = null 
topo = topo-1 
 
retorno 
Inserir elemento 
 -1 
0 
1 
2 
3 
topo 
Pilha 
 Demais Operações 
 Acessar elemento do topo (top) 
 
 Checar se está vazia (isEmpty) 
 
 Checar se está cheia (isFull) 
 
 Tamanho (size) 
Pilha 
 Os elementos da Pilha são distribuídos dentro de um 
vetor pré-dimensionado e o topo é coordenado por um 
ponteiro que indica a sua posição (índice da célula do 
vetor). 
 
Pilha 
 Esta alternativa de implementação possui boa 
performance nas operações de inclusão e exclusão. 
 
 Por outro lado, o pré-dimensionamento do vetor com o 
número máximo de elementos pode ser subestimado ou 
superestimado provocando um uso inadequado da 
memória (principalmente em linguagens onde a alocação 
do vetor é estática). 
 
Pilha 
 
Referências 
 GOODRICH, Michael T; TAMASSIA, Robert. Estruturas 
de dados e algoritmos em JAVA. Porto Alegre: 
Bookman, 2002. 
 SZWARCFITER, Jayme Luiz; MARKENZON, Lílian. 
Estruturas de Dados e seus Algoritmos. Rio de 
Janeiro: LTC, 1994. 
 TENENBAUM, Aaron M.; LANGSAM, Y. AUGENSTEIN, M. 
J. Estruturas de Dados Usando C. São Paulo: Makron 
Books, 1995. 
 DEITEL, Harvey M.; DEITEL, Paul J. Java : como 
programar. 8. ed. Porto Alegre: Bookman, 2010.

Outros materiais