c ++ deque vs queue vs stack

Question

队列和堆栈是广泛提到的结构.但是,在C++中,对于队列,您可以通过两种方式完成:

#include <queue>
#include <deque>

但对于堆栈,你只能这样做

#include <stack>

我的问题是,队列和双端队列之间有什么区别,为什么提出两个结构？对于堆栈,可以包含任何其他结构吗？

Answer 1

Moron/Aryabhatta是正确的,但更多细节可能会有所帮助.

队列和堆栈是比deque,vector或list更高级别的容器.通过这个,我的意思是你可以从较低级别的容器中构建一个队列或堆栈.

例如:

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

将使用deque作为底层容器和使用列表作为底层容器的双精度队列来构建一堆int.

您可以将其s视为受限制的双端队列和q限制列表.

所有必要的是低级容器实现更高级容器所需的方法.这些back(),push_back()和pop_back()堆栈和front(),back(),push_back(),和pop_front()队列.

有关详细信息,请参阅堆栈和队列.

关于双端队列,它不仅仅是一个可以在两端插入的队列.特别是,它具有随机访问权限operator[].这使它更像是一个向量,但是一个向量,你可以在开头插入和删除push_front()和pop_front().

详见deque.

Answer 2

Queue:您只能在一端插入并从另一端移除.

Deque:您可以从两端插入和删除.

所以使用a Deque,你可以模拟a Queue和a Stack.

提示:
Deque是短期的" d ouble ê nded 阙 UE".

Answer 3

deque是一个容器模板.它满足了具有随机访问迭代器的序列的要求,就像a vector.

queue它根本不是容器,它是一个适配器.它包含一个容器,并提供不同的,更具体的界面.使用queue时,你要记住(或提醒),以避免操作之外push[_back]和pop[_front],front和back,size和empty.你根本不能看到queue第一个和最后一个内部的元素!

Answer 4

在C++库,既std::stack和std::queue被实现为容器的适配器.这意味着它们分别提供堆栈或队列的接口,但它们本身都不是真正的容器.相反,他们使用一些其他的容器(例如std::deque或std::list实际存储数据),以及std::stack类只是有代码一点点翻译push并pop以push_back和pop_back(和std::queue做大致相同,但使用push_back和pop_front).

Answer 5

双端队列是一个双端队列,可以从任一端轻松插入/移除.队列只允许插入一端并从另一端检索.

Answer 6

deque 支持前后插入/弹出

queue 只支持插入到后面，从前面弹出。您知道，FIFO（先进先出）。