C++ deque vs file d'attente vs pile

Question

File d'attente et pile sont des structures largement mentionnées. Cependant, en C++, pour la file d'attente, vous pouvez le faire de deux façons:

#include <queue> 
#include <deque> 

mais pour pile vous ne pouvez le faire comme ça

#include <stack> 

Ma question est, quelle est la différence entre la file d'attente et deque , pourquoi deux structures proposées? Pour la pile, n'importe quelle autre structure pourrait être incluse?

Answer 1

Moron est correct, mais un peu plus de détails peuvent être utiles. La file d'attente et la pile sont des conteneurs de niveau plus élevé que deque, vecteur ou liste. Par cela, je veux dire que vous pouvez construire une file d'attente ou empiler hors des conteneurs de niveau inférieur.

Par exemple:

std::stack<int, std::deque<int> > s; 
    std::queue<double, std::list<double> > q; 

construira une pile de ints en utilisant un deque comme conteneur sous-jacent et une file d'attente de doubles en utilisant une liste que le conteneur sous-jacent.

Vous pouvez considérer s comme une liste restreinte et q comme une liste restreinte.

Tout ce qui est nécessaire est que le conteneur de niveau inférieur implémente les méthodes requises par le conteneur de niveau supérieur. Ce sont back(), push_back() et pop_back() pour la pile et front(), back(), push_back() et pop_front() pour la file d'attente. Pour plus de détails, voir stack et queue pour plus de détails.

En ce qui concerne le deque, c'est beaucoup plus qu'une queue où vous pouvez insérer aux deux extrémités. En particulier, il a l'accès aléatoire operator[]. Cela ressemble plus à un vecteur, mais un vecteur où vous pouvez insérer et supprimer au début avec push_front() et pop_front().

Voir deque pour les détails.

Answer 2

Une deque est à deux extrémités. Une file d'attente ne l'est pas.

Answer 3

File d'attente: vous ne pouvez insérer qu'une extrémité et la retirer de l'autre.

Deque: vous pouvez insérer et retirer des deux côtés. Donc, en utilisant un Deque, vous pouvez modéliser une file d'attente ainsi qu'une pile.

Answer 4

Une mémoire est une file d'attente à double extrémité, ce qui permet une insertion/suppression facile à chaque extrémité. Les files d'attente ne permettent l'insertion qu'à une extrémité et l'extraction à l'autre.

Answer 5

deque supporte insert/pop de retour avant &

file d'attente

supporte uniquement insérer à l'arrière, et pop de l'avant. Vous savez, un FIFO (premier entré, premier sorti).

Answer 6

deque est un modèle de conteneur. Il satisfait les exigences pour une séquence avec des itérateurs à accès aléatoire, un peu comme un vector.

queue n'est pas un conteneur du tout, c'est un adaptateur . Il contient un conteneur et fournit une interface différente et plus spécifique. Utilisez queue lorsque vous voulez vous rappeler (ou rappeler) d'éviter les opérations en dehors de et pop[_front], front et back, size et empty. Vous ne pouvez pas regarder les éléments à l'intérieur du queue en plus du premier et du dernier, à tous!

Answer 7

Dans la bibliothèque C++, à la fois std::stack et std::queue sont mis en oeuvre en tant que conteneur adaptateurs. Cela signifie qu'ils fournissent respectivement l'interface d'une pile ou d'une file d'attente, mais ni l'un ni l'autre n'est vraiment un conteneur en soi. Au lieu de cela, ils utilisent un autre récipient (par exemple std::deque ou std::list pour stocker réellement les données), et la classe std::stack a juste un petit peu de code pour traduire push et pop-push_back et pop_back (et std::queue-t à peu près le même, mais en utilisant push_back et pop_front).

Answer 8

La file d'attente de file d'attente prioritaire se produit en fonction d'une comparaison de priorité (ordre de priorité) et non de l'ordre de mise en file d'attente. Par exemple, vous pouvez stocker des événements chronométrés dans un événement où vous voulez d'abord retirer l'événement le plus proche et faire une requête pour son heure planifiée afin que vous puissiez dormir jusqu'à ce moment-là.

Les files d'attente prioritaires sont souvent implémentées en utilisant des tas.