c ++ deque vs队列vs堆栈

队列和堆栈是一个被广泛提及的结构。 但是,在C ++中,对于队列,您可以通过两种方式来实现:

#include <queue> #include <deque> 

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

 #include <stack> 

我的问题是,queue和deque之间有什么区别,为什么两个结构提出? 对于堆栈,可以包含任何其他结构?

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

队列和堆栈是更高级别的容器。 比双列或列表或向量。 通过这个我的意思是你可以build立一个队列或堆栈的低级别的容器。

例如:

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

将使用deque作为底层容器和使用list作为底层容器的double的队列来构build一个ints堆栈。

你可以把s看作一个受限制的deque,把q作为一个限制列表。

所有必要的是,下层容器实现上层容器所需的方法。 这些对于栈来说是back(),push_back()和pop_back(),对于队列是front(),back(),push_back()和pop_front()。

请参阅堆栈和队列以获取更多细节。

关于双端队列,它不仅仅是一个可以插入两端的队列。 特别是它有随机访问操作符[]。 这使得它更像是一个向量,而是一个可以插入和删除push_front()和pop_front()的向量。

详见deque 。

队列:只能在一端插入,从另一端删除。

德克:你可以插入和删除两端。

所以使用一个Deque,你可以build立一个队列以及一个堆栈。

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

queue根本不是容器,它是一个适配器 。 它包含一个容器,并提供了一个不同的,更具体的接口。 使用queue当你想记住(或提醒),以避免除了push[_back]pop[_front]frontbacksizeempty 。 除了第一个和最后一个,你根本看不到queue中的元素!

在C ++库中, std::stackstd::queue都是作为容器适配器实现的。 这意味着它们分别提供了一个栈或一个队列的接口,但它本身并不是一个容器。 相反,他们使用一些其他的容器(例如std::dequestd::list来实际存储数据),而std::stack类只有pop_back代码来将pushpop转换为push_backpop_back (和std::queue大致相同,但使用push_backpop_front )。

deque是一个双端队列,允许从任何一端轻松插入/删除。 队列只允许插入一端,并从另一端进行检索。

deque支持从后面和前面插入/popup

队列只支持插入到后面,并从前面popup。 你知道,一个FIFO(先进先出)。

一个deque是双重的。 队列不是。

优先级队列出队按照某种sorting(优先级)比较而不是排队顺序进行。

例如,您可以将定时事件存储在您想要首先提取最快事件的时间事件中,并查询其计划时间,以便您可以睡到该时间点。

优先级队列通常使用堆实现。