C++ deque vs队列vs栈

Question

队列和堆栈是广泛提及的结构。然而，在C++中，队列你可以做到这一点有两种方式：

#include <queue> 
#include <deque> 

但对于栈你只能做这样的

#include <stack> 

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

Answer 1

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

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

例如：

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

将建成使用双端队列作为底层容器和使用列表作为底层容器双打的队列整数的堆叠。

您可以将s视为受限制的双列队列表，并将q视为受限列表。

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

有关详细信息，请参见stack和queue。

对于双端队列，它远远超过了你可以插入两端的队列。特别是，它有随机访问operator[]。这使得它更像是一个向量，但是它可以在开头以push_front()和pop_front()插入和删除。

详情请参见deque。

Answer 2

德克是双端的。队列不是。

Answer 3

队列：您可以只插入一端，并从另一端删除。

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

因此，使用一个Deque，你可以建立一个队列以及一个堆栈。

Answer 4

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

Answer 5

双端队列支持从背面&前

队列只支持插入到后面，和从正面弹出插入/弹出。你知道，一个FIFO（先进先出）。

Answer 6

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

queue根本不是容器，它是一个适配器。它包含一个容器并提供了一个不同的，更具体的接口。当您想要记住（或提醒）以避免除push[_back]和pop[_front],front和back,size和empty之外的操作时使用queue。除了第一个和最后一个，你根本看不到queue里面的元素！

Answer 7

在C++库中，std::stack和std::queue均作为容器适配器实现。这意味着它们分别提供堆栈或队列的接口，但它们本身都不是一个容器。相反，他们使用一些其他的容器（例如std::deque或std::list实际存储的数据），和std::stack类只是有代码一点点到push和pop转化为push_back和pop_back（和std::queue做大致相同，但使用push_back和pop_front）。

Answer 8

优先级队列出队根据某种排序（优先级）比较而不是排队顺序发生。

例如，您可以将定时事件存储在想要首先提取最早事件并查询其计划时间的事件中，以便您可以在该时间点之前休眠。

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