Please enable JavaScript.
Coggle requires JavaScript to display documents.
Filas - Coggle Diagram
Filas
Filas baseadas em Arrays
-
Um jeito de eficientemente implementar filas com arrays é permitir que os elementos fiquem "à deriva", ou seja, nem sempre o começo da fila será o começo do array.
Apesar desse jeito garantir que as operações tenham complexidade constante, quando o array está cheio, não vamos conseguir mais adicionar na fila e isso vai acontecer muito mais rápido do que na implementação mais bruta.
Podemos resolver "fingindo" que o array é circular, ou seja, quando a posição da frente da fila chega no final do array, vamos permitir que ela volte para o começo do array, que garantimos que está livre.
-
Se a fila é circular, como eu sei quando ela está cheia ou vazia?
Tendo front como o index da frente da fila e rear como o index do final da fila, se forem iguais significa que temos um único elemento na fila. Ou seja, se o valor de rear for uma vez menor que front, sabemos que a fila está vazia.
No entanto, não conseguimos diferenciar quando a lista está vazia ou cheia, pois no caso da fila circular, mesmo se tivermos todos os elementos, o valor de rear vai ser uma unidade menor que o valor de front também.
-
Outra solução é fazer o array ter tamanho n+1 , mas permitir que somente n elementos sejam armazenados nela.
Nesse caso, se o array estiver cheio front não vai ser igual a rear + 1.
Filas ligadas
Adaptação da lista ligada, com um nó de header que vai permitir evitar os casos especiais quando a fila está vazia.
Na inicialização, tanto front como rear apontam para o mesmo lugar: o nó de header. O front sempre apontará para ele, enquanto rear aponta para o final da fila.
-
Assim como na pilha, a fila é uma estrutura similar a uma lista que dá acesso restrito aos seus elementos.
Elementos de uma fila só podem ser inseridos no final da fila (enqueue) e removidos do começo da fila (dequeue)
-
-