Please enable JavaScript.
Coggle requires JavaScript to display documents.
Stacks - Coggle Diagram
Stacks
-
Como a pilha, a fila é uma lista que possui acesso restrito a seus elementos, elementos da fila só podem ser inseridos nas costas, e removido da frente
É como se fosse uma fila da vida real, e utiliza de FIFO, first in, first out
E como a pilha, existe a array based
E para implementá-la, não é tão facil, pois se fizer uma simples conversão de uma array based stack para uma queue, não será efetivo
Se escolhermos o elemento traseiro da fila na posição 0, as operações de desenfileiramento requerem apenas Θ(1) tempo porque o elemento da frente da fila (o que está sendo removido) é o último elemento da array.
Contudo, operações de enfileiramento vai requerer Θ(n) tempo, por que n elementos deverão ser deslocados uma posição da array
já se gostaríamos de pegar o elemento de trás e colocar um na frente, só iria demandar Θ(1) tempo, porque todos os elementos deverão ser deslocados uma vez para trás para manter a propriedade que os n-1 elementos restantes residem nas n-1 primeiras posições da array
Uma implementação bem mais eficiente seria não levar a sério o requerimento de que todos os elementos da fila devem ficar nas primeiras n posições da array
Ainda será necessário que a fila seja implementada em continuas posições do array mas o conteúdo da fila poderá ser mudado sem que a array mude. e ambas as operações de enfileirar e desenfileirar irá custar Θ(1) de tempo porque nenhum outro elemento precisa ser movido
- 1 more item...