我正在实现拓扑排序的一个变体，它需要一个结构来保存没有传入边的元素。两者看起来都很好queue，stack因为取出它们的顺序无关紧要。问题是：它们中的任何一个明显快于另一个吗？
问问题
5996 次
5 回答
2
queue并且stack都是容器适配器，它们本身并不是完整的容器。两者 stack和默认情况下queue 都在 a 之上实现，std::deque如果您不更改此设置，它们应该具有相似的性能。
这实际上取决于您正在编写什么样的应用程序，并且您可以选择最有利于您想要的那些操作的底层容器。
于 2013-03-31T20:03:13.623 回答
2
回答你的主要问题：我不知道。我不认为它们中的任何一个明显更快，因为std::deque（堆栈和队列的默认内部容器）push_back 和 push_front（以及 pop_back 和 pop_front）是对称的。没有一个应该更快。但是，我建议将普通的旧 std::vector 与push_backandpop_back或等效地一起使用
std::stack<T, std::vector<T>>
请参阅此处了解堆栈默认使用双端队列的原因。
于 2013-03-31T20:04:29.227 回答
1
虽然在性能上queue并stack没有太大的不同，但它们显然会导致不同的节点访问顺序。根据您的节点在内存中的布局方式，其中一个可能会比另一个提供对缓存更友好的顺序。
于 2013-03-31T20:07:03.783 回答
1
它们都具有恒定的复杂性...您只需要计时以确定是否有任何常数更高
http://www.cplusplus.com/reference/stack/stack/pop/
http://www.cplusplus.com/reference/queue/queue/pop/
于 2013-03-31T20:02:57.920 回答
-3
队列和堆栈是不同的。首先是FIFO，堆栈是FILO
于 2013-03-31T19:59:25.997 回答