Please enable JavaScript.
Coggle requires JavaScript to display documents.
Listas, pilhas e filas - Coggle Diagram
Listas
tipos
Lista com Arrays (List :: Array)
Utiliza índices para acessar os elementos.
Acesso aleatório (Random Access): qualquer elemento pode ser acessado diretamente.
limitações
Tamanho pré-definido (ou cresce dinamicamente com realocação).
Pode ter espaços não utilizados.
Lista Encadeada (List :: Linked List)
Usa ponteiros para conectar elementos.
Acesso sequencial (Sequential Access): elementos são acessados percorrendo a lista.
vantagens
Cresce dinamicamente.
Não há alocação desnecessária de memória.
desvantagens
Uso extra de memória para armazenar ponteiros.
Percorrer a lista é mais lento que em arrays.
Lista Simplesmente Encadeada
Cada nó aponta para o próximo.
O último nó aponta para NULL.
Lista Duplamente Encadeada
Cada nó aponta para o próximo e para o anterior.
Melhor para inserções e remoções no meio da lista
Operações Fundamentais
Inserção
Remoção
Busca
Lista como Tipo Abstrato de Dados (ADT)
Um ADT define um conjunto de operações sobre um conjunto de valores.
A implementação de um ADT pode ser feita com diferentes estruturas de dados.
Estrutura de Nós
Nó como Unidade Básica da Lista
Cada nó contém um dado e um ou mais ponteiros.
Diferença entre Arrays e Listas Encadeadas
Arrays usam índices.
Listas encadeadas usam ponteiros.
Vantagens
Lista Encadeada
Crescimento dinâmico.
Sem desperdício de memória com posições vazias.
Lista com Arrays
Acesso direto por índice.
Estrutura mais simples.
Desvantagens
Lista Encadeada
Percorrer a lista pode ser lento.
Manipulação incorreta pode corromper a estrutura.
Lista com Arrays
amanho fixo (ou realocação necessária).
Pode conter espaços não utilizados.
Conceito
Listas são coleções ordenadas de elementos que podem crescer ou diminuir dinamicamente.
pilhas e filas
pilhas
Definição
Estrutura LIFO (Last In, First Out)
Principais Operações
Push - adiciona no topo da lista
Pop - remove do topo da lista
Top - acessa o topo da lista
empty - verifica se a pilha ta vazia
size - retorna o número de elementos
como implementar em c++?
Usando o std::stack da biblioteca <stack>:
a pilha é uma classe pronta
Filas
Definição
Estrutura FIFO (First In, First Out)
Principais Operações
equeue - adiciona um elemento no final da fila
dequeue - remove o elemento do inicio da fila
front - acessa o primeiro elemento da fila
back - acessa o ultimo elemento da fila
back - acessa o ultimo elemento da fila
empty - verifica se a fila ta vazia
size - retorna o numero de elementos presentes na fila
como implementar em c++?
Usando o std::queue da biblioteca <queue>
a fila é uma classe pronta