Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pilhas, Filas - Coggle Diagram
Pilhas
-
-
Pilhas encadeadas
-
-
O nó header não é usado porque não há necessidade de casos especiais para listas com 1 ou 0 elementos.
Método Empilha
Empilha primeiramente modifica o apontador next para apontar para o top da pilha e então coloca top para apontar para o novo nó.
-
É uma estrutura no formato de listas, onde os elementos só podem ser inseridos e removidos de um final.
Menos flexível do que as listas, mas mais eficiente e fácil de implementar.
-
Estrutura conhecida como "LIFO(Last-In, First-Out)" que significa que Pilhas removem elementos em ordem contrária à da chegada.
Elementos não são inseridos, nem removidos, eles são empilhados e desempilhados.
Pilhas podem ser usadas para implementação de recursão, porém só são eficientes quando a qtde. de informação necessária é pequena.
Filas
Filas baseadas em Array
-
Se o final da lista for a posição 0, então o método desenfileirar ocorrerá em Θ(1), porém o método enfileirar ocorrerá em Θ(n) porque os elementos teriam que andar 1 posição no array.
Se o começo da lista for a posição 0, ocorrerá o contrário, o método enfileirar em Θ(1) e o método desenfileirar em Θ(n), o que também não é muito eficiente.
-
Para o problema de saber se a Fila está cheia ou vazia, uma solução é fazer o array com tamanho n+1, mas permitir que só n elementos sejam armazenados.
Atributos da Fila
-
int maxSize: tamanho máximo da fila, usado para controlar o movimento circular.
-
-
-
-
Filas encadeadas
-
-
-
Porém, o apontador primeiro estará sempre apontado para o header, enquanto o apontador último estará apontado para o último elemento da fila.
-
-
Como a pilha, filas são estruturas no formato de listas com acesso restrito aos seus elementos.
-
Estrutura conhecida como "FIFO(First-In, First-Out)", ou seja, liberam seus elementos de acordo com a ordem de chegada.