deque contre file d'attente en C ++

Question

La file d'attente et la pile sont des structures largement mentionnées. Cependant, en file d'attente, vous pouvez le faire de deux manières:

 #include <queue>
#include <deque>
 

mais pour la pile, vous ne pouvez le faire comme ça

 #include <stack>
 

Ma question est la suivante: quelle est la différence entre queue et deque, pourquoi deux structures proposées? Pour la pile, toute autre structure pourrait être incluse?

Answer 1

C'est correct, mais un peu plus de détails peuvent être utiles.

la file d'attente et la pile sont des conteneurs. que deque ou à une liste ou un vecteur. Par cela, je veux dire que vous pouvez créer une file d'attente ou la pile hors de la baisse du niveau des conteneurs.

Par exemple:

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

Volonté de créer une pile d'entiers à l'aide d'un deque que le conteneur sous-jacent et une file d'attente de doubles à l'aide d'une liste que le conteneur sous-jacent.

Vous pouvez penser de s comme une restriction de l'deque et q ainsi qu'une liste restreinte.

Tout ce qui est nécessaire est que le niveau inférieur du conteneur implémente les méthodes nécessaires par la hausse du niveau de conteneur. Ces sont de retour(), push_back() et pop_back() pour la pile et face(), back(), push_back() et pop_front() pour la file d'attente.

Voir la pile et file d'attente pour plus de détails.

À l'égard de la deque, c'est beaucoup plus qu'une file d'attente où vous pouvez insérer les deux extrémités. En particulier, il a l'accès aléatoire de l'opérateur[]. De ce fait, il est plus comme un vecteur, mais un vecteur où vous pouvez insérer et supprimer au début avec push_front() et pop_front().

Voir deque pour plus de détails.

Answer 2

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

queue n'est pas un conteneur à tous, c'est un adaptateur. Il contient un conteneur et fournit une interface spécifique. Utiliser queue lorsque vous voulez vous rappeler (ou de rappeler) pour éviter les opérations en plus d' push[_back] et pop[_front], front et back, size et empty. Vous ne pouvez pas regarder les éléments à l'intérieur de l' queue d'ailleurs la première et la dernière, à tous!

Answer 3

Dans la bibliothèque C++, les deux std::stack et std::queue sont mis en œuvre en tant que conteneur de cartes. Cela signifie qu'ils fournissent l'interface d'une pile ou d'une file d'attente, respectivement, mais ce n'est vraiment un contenant en lui-même. Au lieu de cela, ils utilisent un autre récipient (par exemple, std::deque ou std::list pour enregistrer les données), et l' std::stack classe a juste un tout petit peu de code pour traduire push et pop de push_back et pop_back (et std::queue fait à peu près la même, mais en utilisant push_front et pop_back).

Answer 4

Un deque est une file d'attente à deux extrémités, ce qui permet une insertion / un retrait facile de l'une ou l'autre extrémité. Les files d'attente permettent uniquement l'insertion à une extrémité et la récupération à partir de l'autre.