Fila
C++ KotlinDefinição
A fila é uma estrutura de dados para conter objetos obedecendo a ordem de entrada FIFO( First In First Out ). Isso significa que o primeiro elemento a ser adicionado sera o primeiro elemento a sair. Em sua forma mais clássica ela implementa as seguintes operações:
- Peek : essa operação retorna o primeiro elemento da fila, em alguns casos pode ser também implementada como Front
- Push: a operação adiciona um elemento na última posição da fila
- Pop : essa operação remove um elemento da primeira posição da fila. Em algumas implementações, a operação remove e retorna o elemento que removeu
Complexidades
| Operação | Caso médio | Pior caso |
|---|---|---|
| Espaço | O(n) | O(n) |
| Busca | O(n) | O(n) |
| Peek | O(1) | O(1) |
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
Implementação
A fila pode ser implementada de duas maneiras: através de um vetor estático com tamanho fixo onde é armazenado o índice da posição inicial e esse valor vai rotacionando pelo vetor, ou através de uma lista encadeada.
Ao se implementar com uma lista encadeada é necessário manter um ponteiro para a última posição da lista de forma que a inserção mantenha a complexidade O(1).