栈和队列是线性数据结构还是非线性数据结构？

Question

我长期以来一直在面对这个问题。很少有作者说堆栈和队列是线性数据结构，并且很少有非线性的。哪一个是对的，为什么？

在维基百科，它给出的是队列是线性数据结构。我也相信它们是线性的，因为没有像树木那样的改道。但是，在尝试进行在线测试时，它被覆盖，称它们是非线性的。

请准确回答我，这是真的，为什么。

Answer 1

对我来说，队列或堆栈只是一个规范。实施可能会有所不同。

Answer 2

要么是真的。单词“堆栈”和“队列”仅定义允许的访问模式，而不是实现细节。例如，您可以将其实现为链接列表。

Answer 3

这要看！队列/堆栈可以与FIFO和LIFO一样是线性的，但是在优先队列的情况下，队列/堆栈可以是非线性的，例如，服务元素取决于您指定的某个参数！
所以，两者都可以是真的！这完全取决于你如何实现你正在使用的数据结构！
然而，很可能堆栈被认为是线性的，队列可以是两个，链表和树是非线性的。

Answer 4

这是什么意思“线性”？它们当然不是圆形的也不是球形的。

此外，答案将取决于你正在谈论的堆栈/队列。

---

您的意思是“连续”吗？

如果您的意思是std::stack和std::queue（然后请从您的问题中删除“C”标记），那么它仍然取决于。它们都是容器适配器这意味着可以将底层实现指定为模板参数。默认情况下，std::stack和std::queue是建立在std::deque —这不保证是连续的。

对于一些其他任意容器规范，这将取决于。

---

你是不是指“序列”？

标准C++ has three sequence containers：std::vector,std::list和std::deque。这意味着std::stack/std::queue本身不是一个序列容器，但其实施可以是，这取决于你选择哪一个。

---

希望有所帮助。

Answer 5

衬垫数据结构无关，与它的实现细节或它的内存模型。它只是意味着它的所有元素都有它的前面或后面，排除了头部和尾部。不像树或格雷。

衬里数据结构包括队列，堆栈。

如果有人误用班轮作为“连续记忆”，他/她是错误的。