代码之家 › 专栏 › 技术社区 › Austin

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

deque queue stack class c++

Austin · 技术社区 · 9 年前

我正在用C++做一些新手HackerRank问题,我发现似乎有几种方法可以解决这个问题,我想知道哪种方法使用最广泛和/或最有效。这个问题需要创建一个包含这两者的类 stack 和 queue 变量以及 stack_push / stack_pop 和 queue_push / queue_pop 功能。

根据我在谷歌上的搜索结果,我可以使用 std::vector , std::stack 和 std::queue 或 std::deque ,也许还有其他人。

我不知道如何确定哪一种是最好的。有什么建议吗?

编辑: 我使用 标准::矢量 用于两者,然后使用 标准::堆栈 随着 std::队列 在一个小的测试用例中,我看到了两者的性能完全相同。编辑2: 对于更大的测试用例,它看起来像 std:stack / std:queue 跑赢大市 std:vector .我猜这是因为FIFO队列的一半对向量无效,但我需要对其进行更多测试。

2 回复 | 直到 9 年前

Arun 9 年前

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

从引用的页面

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

容器—用于存储元素。容器必须满足序列容器。此外,还必须提供以下内容具有通常语义的函数:back()push_back(pop_back) 标准容器std::vector、std:、deque和std:;list满足这些要求。

如果情况允许,我会使用 标准::堆栈 或 std::队列 而不必担心潜在的细节。如果我必须掌握更多的控制权,我会选择 标准::deque .

Manish 9 年前

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

推荐文章

Nwerx_user · 在C#中,如何在不使用static关键字的情况下使用类外的方法?

4 月前

iasonas · 如何检查自定义注释?

4 月前

NaturalDemon · 无法使用嵌套类、指针将类型为“test_nested*”的右值(又名“test::test_nester*”)的“test_nest*”类型的变量初始化

5 月前

Norbert Horváth · Dafny中使用PriorityQueue的Dijkstras算法

5 月前

Svyat · 如何创建一个类设置,其中两个类各包含另一个类的实例?

5 月前

Mark · 实现抽象类

5 月前

F-22 Destroyer · 遇到super()问题

9 月前

Nick X Tsui · 当使用带有std::map()[复制]的智能指针时,调用隐式删除的复制构造函数

10 月前

simply lemon · python上链表的添加方法

10 月前

Minty · 自定义类中使用numpy数组进行左加法/右加法的不同行为

10 月前