Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM10 - Coggle Diagram
MM10
Stack com array
Componentes principais
array de armazenamento
índice top
capacidade máxima
Funcionamento do topo
top indica posição do último elemento válido
push incrementa top
pop decrementa top
Processo do push
verificar overflow
mover top
armazenar valor
Processo do pop
verificar underflow
acessar topo
decrementar índice
Overflow
Problema principal
pilha cheia
array não possui mais espaço
Vantagens do array stack
excelente localidade de cache
implementação simples
baixo overhead estrutural
Desvantagens
tamanho fixo
desperdício de memória possível
crescimento exige realocação
Stack com lista encadeada
Elementos principais
nós encadeados
ponteiro para topo
Organização
topo normalmente corresponde ao início da lista
Push
cria novo nó
novo nó aponta para antigo topo
topo passa a apontar para novo nó
Pop
remover nó do topo
atualizar ponteiro topo
liberar memória
Diferença para array
memória cresce dinamicamente
cada nó possui overhead de ponteiro
Vantagens
sem tamanho fixo
crescimento flexível
não necessita realocação
Desvantagens
pior cache locality
maior custo por elemento
alocação dinâmica frequente
Queue com array
Problema da implementação linear simples
Remover do início
causaria deslocamento dos elementos
custo O(n)
Solução: fila circular
Índices importantes
front
rear
Funcionamento circular
índices avançam modularmente
ao chegar no fim do array:
retornam ao início
reutilizar posições liberadas
enqueue
inserir em rear
avançar rear
dequeue
remover de front
avançar front
Problemas clássicos
Overflow
fila cheia
Underflow
fila vazia
Vantagens
alta eficiência
boa localidade de memória
sem deslocamentos
Desvantagens
tamanho limitado
controle circular mais complexo
Queue com lista encadeada
Ponteiros principais
front
rear
enqueue
criar novo nó
anexar após rear
atualizar rear
dequeue
remover front
avançar ponteiro
Vantagens
tamanho dinâmico
ausência de overflow estrutural
Desvantagens
overhead de ponteiros
pior desempenho de cache
Stack
Conceito de pilha
Estrutura linear com acesso restrito
Inserção e remoção acontecem apenas no topo
Segue política LIFO:
Last In First Out
Último elemento inserido será o primeiro removido
Operações fundamentais
push
adiciona elemento ao topo
pop
remove elemento do topo
top / peek
consulta elemento do topo sem remover
clear
remove todos os elementos
length / size
informa quantidade de elementos
Natureza operacional da pilha
Não existe acesso aleatório eficiente
Não se percorre a pilha livremente
Toda manipulação depende do topo
Aplicações clássicas
Controle de chamadas de função
Cada chamada gera activation record
Retornos acontecem em ordem inversa
Recursão
Chamadas recursivas usam stack implicitamente
Parsing e compiladores
avaliação de expressões
balanceamento de parênteses
Backtracking
desfazer estados anteriores
Array stack vs Linked stack
Desempenho
Ambos possuem
push O(1)
pop O(1)
Diferença prática
Array stack
geralmente mais rápido
memória contígua favorece cache
Linked stack
mais flexível
melhor para crescimento imprevisível
Uso de memória
Array
espaço reservado antecipadamente
Linked
memória apenas quando necessária
Cenários ideais
Array stack
tamanho previsível
aplicações de alta performance
Linked stack
tamanho variável
necessidade de expansão dinâmica
Array queues vs Linked queues
Array queue
Pontos fortes
memória contígua
desempenho alto
menor overhead
Limitações
tamanho máximo
gerenciamento circular necessário
Linked queue
Pontos fortes
crescimento flexível
memória sob demanda
Limitações
maior consumo estrutural
custo de alocação dinâmica
Array queue
melhor quando tamanho é previsível
Linked queue
melhor quando crescimento é imprevisível
Queue
Conceito de fila
Estrutura linear com acesso restrito
Inserção em uma extremidade
Remoção na outra
Política FIFO
First In First Out
Primeiro a entrar é o primeiro a sair
Operações fundamentais
enqueue
inserir no final
dequeue
remover do início
front
consultar primeiro elemento
rear
consultar último elemento