Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM9 - Coggle Diagram
MM9
Queues
Estrutura FIFO:
First In, First Out
Operações principais
enqueue()
dequeue()
front()
Aplicações
escalonamento
buffers
impressão
BFS
simulações
Array-Based Queues
Estrutura Circular
evita deslocamentos
Índices
front
rear
Enqueue
Processo
inserir no rear
avançar circularmente
Complexidade
O(1)
Dequeue
Processo
remover front
avançar circularmente
Complexidade
O(1)
Circularidade
Uso do módulo: rear = (rear + 1) % maxSize;
Problema Full vs Empty
Soluções
contador
slot vazio reservado
Array-Based Queues
Estrutura Circular
evita deslocamentos
Índices
front
rear
Enqueue
Processo
inserir no rear
avançar circularmente
Complexidade
O(1)
Dequeue
Processo
remover front
avançar circularmente
Complexidade
O(1)
Circularidade
Uso do módulo
rear = (rear + 1) % maxSize;
Problema Full vs Empty
Soluções
contador
slot vazio reservado
Linked Queues
Estrutura
ponteiro front
ponteiro rear
Enqueue
inserir no final
Complexidade
O(1)
Dequeue
remover início
Complexidade
O(1)
Vantagens
tamanho dinâmico
sem desperdício fixo
Desvantagens
overhead de memória
menor localidade de cache
Array-Based Stacks
Estrutura
vetor + índice topo
Top aponta para o último elemento inserido
Push
Processo
incrementar topo
inserir elemento
Complexidade
O(1)
Pop
Processo
remover topo
decrementar índice
Complexidade
O(1)
Vantagens
simples
rápida
cache-friendly
Desvantagens
tamanho fixo
desperdício de memória possível
Linked Stacks
Estrutura
pilha implementada com lista ligada
Topo aponta para o primeiro nó da lista
Push
inserir no início
Complexidade
O(1)
Pop
remover primeiro nó
Complexidade
O(1)
Vantagens
crescimento dinâmico
sem limite fixo
Desvantagens
overhead de ponteiros
pior localidade de memória
Stacks
Conceito
Estrutura LIFO: Last In, First Out
Operações principais
push()
pop()
top()
Aplicações
chamadas de função
recursão
undo
parsing
avaliação de expressões
Array Stack vs Linked Stack
Array Stack
Melhor para
tamanho previsível
desempenho máximo
Linked Stack
Melhor para
tamanho variável
crescimento imprevisível
Custos
Arrays
menos memória extra
Linked
mais flexibilidade
Array Queue vs Linked Queue
Array Queue
Melhor para
eficiência de cache
tamanho conhecido
Linked Queue
Melhor para
crescimento imprevisível
sistemas dinâmicos