Estruturas de Dados em C/C++
Aula 14
Prof. Anderson da Cruz
Pilhas
Pilhas são estruturas em que os dados são adicionados e
removidos de acordo com a política LIFO
LIFO = Last-In, First-Out
Os elementos são adicionados e removidos sempre em uma
extremidade (a final), que é chamada de topo da pilha
Resumindo: o primeiro a sair da lista é o último que entrou
2
Pilhas - Implementação
1 - Definir a capacidade da pilha
2 - Inicializar a variável que aponta para o topo da
pilha (top = -1 significa que a pilha está vazia)
3 - Implementar o método que adiciona elementos
na pilha
4 - Implementar o método que remove elementos
da pilha
5 - Implementar o método que informar se a pilha
está vazio ou não
3
Pilha
4
Pilha
5
Pilha
6
Pilha
7
Filas
Pilhas são estruturas em que os dados são adicionados e
removidos de acordo com a política FIFO
FIFO = First-In, First-Out
Os elementos são inseridos no fim da fila e retirados do
início da fila
Resumindo: o primeiro a sair da lista é o primero que
entrou
8
Filas - Implementação
1 - Definir a capacidade da fila
2 - Inicializar a variável que aponta para o início
da fila e a variável que aponta para o final da fila
3 - Implementar o método que adiciona elementos
na lista
4 - Implementar o método que remove elementos
da fila
5 - Implementar o método que informar se a pilha
está vazio ou não
9
Fila
10
Fila
11
Fila
12
Fila
13
Listas Simplesmente
Encadeadas
Uma lista encadeadas básica deve conter
head: referência para o primeiro elemento da lista
tail: referência para o último elemento da lista
node: representa um item da lista
> element: o informação
> next: um atributo para o próximo elemento da lista
14
Listas Simplesmente
Encadeadas
Exemplo de uma lista encadeada
15
Listas Simplesmente
Encadeadas
Inserção uma lista encadeada
16
Listas Simplesmente
Encadeadas
Exclusão do 1º nó de uma lista
encadeada
17
Listas Simplesmente
Encadeadas
Exclusão de um nó no meio da lista
encadeada
18
Listas Simplesmente
Encadeadas
Inserção em uma posição específica da
lista encadeada
19
Listas Duplamente Encadeadas
Possui um ponteiro que aponta para o
próximo nó e um que aponta para o nó
anterior
Próximo
Anterior
Nó
20
Listas Duplamente Encadeadas
Lista duplamente encadeadas
simplificam algumas operações e
permitem percorrer a lista em dois
sentidos
Utilizam mais memória
21
Listas Duplamente Encadeadas
Apontador para
o primeiro nó da
Lista
head
tail
180
180
NULL
Início da Lista
180
180
NULL
Fim da Lista
Apontador para
o último nó da
Lista
Exercício
O conceito de pilhas, filas e listas encadeadas já foram
abordos durante o semestre e revisto na aula de hoje,
Sendo assim, crie uma pilha e uma fila a partir da classe
DLinkedList. Obs.: a classes DLinkedList deve ser genérica
Crie também uma classe de teste para validar a
implementação de ambas as classes
Aproveite para tirar dúvidas sobre listas encadeadas
23
Exercício
Na página da disciplina
24