Filas e Pilhas - Notas de Aula
Fila
queue. Trata-se de uma classe template, que aceita como parâmetro uma classe container para usar como implementação. Os containers sugeridos são o deque ou list.
O deque é um container que permite que você insira elementos tanto no início quanto no final da fila. Ou seja, trata-se de uma "double ended queue". Geralmente o deque é implementado como um array dinâmico.
Logo, a inserseção e remoção de elementos nos extremos é O(1).
Considerando as operações padrão de uma fila,
top
enqueue
dequeue
Esse container é bastante adequado. Mais informações sobre o deque: http://www.cplusplus.com/reference/deque/deque/
O outro container que você pode usar é o list. São implementados como listas encadeadas, nesse caso, duplamente encadeadas. Para as operações de fila, ela também funciona em O(1). Sua estrutura interna, permite a inserção e remoção de elementos que não estejam nos extremos mais eficientemente que o deque.
Mais informações: http://www.cplusplus.com/reference/list/list/
Uma outra possibildiade seria utilizar a própria classe array ou vector para implementar uma fila. Mas nesse caso você teria que implementar as operações adequadamente. Minha sugestão é que use as classe queue e escolha o container mais apropriado. Na maioria dos casos a escolha será pelo deque. Ele já é a opção padrão, portanto, não é preciso fazer nada especial para usá-lo.
Fila de Prioridade
As 3 principais maneiras de implementar uma fila de prioridades são com um array ordenado, um array desordenado ou um heap.
A tabela abaixo resumo os prós e contras de cada abordagem:
Em C++, você pode utilizar a classe priority_queue.
Ela usa um vector por padrão e, portanto, deveria funcionar com os tempos do array desordenado acima.
Entretanto, ele automaticamente utiliza as funções make_heap, push_heap e pop_heap internamente para manter o vector sempre com uma estrutura de heap. Portanto, a ordem de complexidade dos algoritmos utilizados na classe priority_queue são as mesmas da heap, da tabela acima.
Pilha
A classe stack de C++ é o template para pilhas. Ela pode utilizar como containers o vector, deque ou list. Por padrão utiliza o deque.
Sendo assim, seus tempos são:
push = O(1)
pop = O(1)
top = O(1)