Estruturas Dinâmicas de Dados: Lista, Filas e Pilhas.

Prévia do material em texto

Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 1
Estruturas Dinâmicas de Dados: 
Listas, Filas e Pilhas
Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 2
Listas - Motivação
 Exemplo ilustrativo:
� Imagine uma brincadeira utilizada na entrega de presentes a um 
aniversariante. Consiste em entregar um cartão (no lugar do 
presente) no qual se informa que o presente está guardado debaixo da 
cama. Lá chegando, o aniversariante percebe que existe uma 
mensagem dizendo que o presente se encontra na gaveta do armário; 
ao abri-la, encontra um outro papel que o conduz ao fogão, do fogão 
para debaixo do tapete, daí para o frigorifico e deste para debaixo da 
mesa.
Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 3
Listas - Motivação(cont.)
o que pode ser esquematizado da seguinte forma:
 Devemos notar que:
� as setas utilizadas na ilustração anterior nada são que mero artifício 
ilustrativo, visto que foi possível representar o mesmo encadeamento 
lógico sem elas, e que no exemplo real elas não existem;
� é necessário um ponto de partida (cartão), que não é considerado 
parte integrante da sequência, apenas indicador do seu início;
gaveta fogão tapete frigorifico mesa presente
cama
cartão
cama gaveta fogão tapete frigorifico mesa
Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 4
� cada um dos pontos é composto pela localização do ponto e de uma 
indicação do próximo local. Isso torna-os de tal maneira 
independentes que permite até mesmo uma alteração completa da sua 
disposição, mantendo intacto o encadeamento lógico dos seus 
componentes. 
� Temos, então, um exemplo de uma lista (encadeada) que se define por 
um conjunto de elementos em que cada um referencia um outro 
elemento distinto como sucessor. 
Listas - Motivação (cont.)
presente frigorifico gaveta tapete mesa fogão
cama
cartão
mesa tapete cama fogão frigorifico gaveta
Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 5
Propriedades das Listas
 Podemos definir as seguintes propriedades das listas:
� os nós estão ligados linearmente
� existem dois extremos na lista: o início e o fim
� os nós podem ser adicionados em qualquer ponto da lista
� os nós podem ser removidos em qualquer ponto da lista
� a lista pode ser percorrida a partir de qualquer ponto
Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 6
Filas
 As filas são estruturas de dados que se comportam como as filas que 
conhecemos
 Uma fila não é mais que uma lista na qual é aplicada uma disciplina de 
acesso característica: todo o elemento que entra na lista é inserido no fim 
desta e todo o elemento que sai da lista é removido do início desta
� esta disciplina de acesso é conhecida como FIFO ( First In, First Out )
...2 5 1 7
6
38 5 6 4
7
0
Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 7
Propriedades das Filas
 Podemos definir as seguintes propriedades das filas:
� os nós estão organizados sequencialmente
� existem dois extremos na fila: o início e o fim
� os nós são adicionados no fim da fila 
� os nós são removidos do início da fila
� a fila é percorrida do início até ao fim
Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 8
Pilhas
 Informalmente, podemos definir uma pilha como um conjunto de itens que 
são adicionados e removidos no topo
� por exemplo, uma pilha de pratos
 Uma pilha é uma lista na qual é aplicada a disciplina de acesso LIFO 
(Last In, First Out)
� qualquer elemento que entrar na pilha somente sairá quando todos os 
que entraram depois dele saírem
 Propriedades das pilhas
� os itens encontram-se armazenados sequencialmente 
� o último elemento da pilha denomina-se por topo
� os itens são inseridos no topo da pilha (push)
� os itens são removidos no topo(pop)
� apenas o elemento do topo é visível (top)
Estruturas Dinâmicas de dados: Listas, Filas e Pilhas 9
Modo de funcionamento das pilhas
3
1
9
45
< 3, 1, 9, 45 >
Operações
Criar pilha
Guardar elemento
Ler o valor do elemento no topo
Retirar elemento
Pilha Vazia?
Corrente de Leitura Corrente de Escrita
< 31,9,45, >
Operações Construtoras
Guardar 
elemento
Ler o valor e
retirar elemento
Criar pilha