哪种数据结构最适合 C++ 中的基本堆栈和队列？

Question

我正在用 C++ 解决一些新手 HackerRank 问题，我发现似乎有几种方法可以解决这个问题，我想知道哪种方法使用最广泛 and/or 最有效。该问题需要创建一个 class，其中包含 stack 和 queue 变量以及 stack_push/stack_pop 和 queue_push/queue_pop 为他们服务。

从我用谷歌搜索的结果来看，我似乎可以使用 std::vector、std::stack 和 std::queue，或者 std::deque，也许还有其他。

我不确定如何确定哪个最适合使用。有什么建议吗？

编辑：我对两者都使用 std::vector 实现，然后使用 std::stack 和 std::queue 并且我看到对于小型测试用例两者具有相同的精确性能。编辑2：对于更大的测试用例，std:stack/std:queue 似乎优于 std:vector。我猜这是因为 FIFO 队列的一半对向量效率不高，但我需要对此进行更多测试。

Answer 1

std::stack 使用 std::deque 作为底层容器。 std::queue 也是如此。参见 http://en.cppreference.com/w/cpp/container/stack and http://en.cppreference.com/w/cpp/container/queue

来自参考页面

template<
    class T,
    class Container = std::deque<T>
> class stack;

Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics: back() push_back() pop_back() The standard containers std::vector, std::deque and std::list satisfy these requirements.

如果情况允许，我会使用 std::stack 或 std::queue，而不用担心底层细节。如果非要我控制的话，我会选择std::deque.

Answer 2

经验法则是，首先确定您的所有需求，然后使用满足所有需求的最简单的数据结构。由于您没有搜索要求，最好是实现 C 风格的链表。对于 Stack，您只需要一个指向前端元素的指针，但对于 Queue，您必须维护 2 个指针来跟踪前端元素和最后一个元素。这可能是最快的实施。

哪种数据结构最适合 C++ 中的基本堆栈和队列？

Which data structure is best for basic stacks and queues in C++?

c++

queue

stack

class

deque