Depois de ter falado sobre a estrutura de dados Stack (pilha) no último post da série, nada melhor do que dar continuidade a série falando de Queue (fila), sua famosa irmã e amiga nas confusões do.. “É FIFO ou é LIFO?”.
Queue ou fila, é uma estrutura de dados muito similar a Stack (pilha), o que acaba gerando confusão. A diferença básica entre elas é a ordem na qual seus itens são consumidos, pois ao contrário da Stack, a Queue sempre vai consumir os itens na ordem que foram inseridos.
| Algoritmo | Big O |
|---|---|
| Espaço | O(n) |
| Busca | O(n) |
| Insert | O(1) |
| Delete | O(1) |
Ou seja, o primeiro item da fila será o primeiro a ser consumido, e ao ser consumido é removido do grupo de itens, passando então o segundo item para primeiro, terceiro para segundo e assim por diante, até o final da fila.
A melhor analogia que podemos fazer com esse algoritmo é pensar, literalmente, em uma fila de supermercado, banco, casa lotérica e etc.. Onde as pessoas são atendidas por ordem de chegada (FIFO: First In First Out).
Filas normalmente tem apenas dois métodos, sendo um para adição de novos itens chamado de enqueue, e outro para remoção de um item chamado de dequeue.
Assim como na estrutura de dados de pilha, as duas formas mais comuns de se implementar uma fila são com arrays ou listas encadeadas (linked list).
Se você quer saber como implementar essa estrutura de dados sem utilizar nenhuma dependência externa, na próxima terça vamos soltar o vídeo no nosso canal do YouTube mostrando como fazer.
Deixem suas dúvidas nos comentários.
Até a próxima!
[…] nossas implementações de estruturas de dados, nesse post vamos mostrar como implementar uma Fila (post teórico) sem qualquer dependência […]