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

Question

我已经面临这个问题很长时间了。很少有作者说堆栈和队列是线性数据结构，很少有非线性数据结构。哪一个是正确的?为什么？

在维基百科中，给出了队列是线性数据结构。我也相信它们是线性的，因为没有像树的情况下的转移。然而，当尝试在线测试时，它被覆盖，说这些是非线性的。

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

Answer 1

你这里所说的“线性”是什么意思？它们肯定既不是圆形的，也不是球形的。

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

你是说“邻接”吗？

如果你指的是std::stack和std::queue (请去掉问题中的"C“标签)，那么还是要看情况。它们都是容器适配器，这意味着底层实现可以指定为模板参数。默认情况下，std::stack和std::queue构建在std::deque之上-不是保证是连续的。

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

你的意思是“序列”吗？

Standard C++ has three sequence containers：std::vector、std::list和std::deque。这意味着std::stack/std::queue本身不是序列容器，但它的实现可能是，这取决于您选择哪一个。

希望这能有所帮助。

Answer 2

那得看情况!队列/堆栈可以是线性的，就像在FIFO和LIFO的情况下一样，但是在优先级队列的情况下，它可以是非线性的，例如，在优先级队列中，服务元素取决于您指定的某些参数！

所以，两者都有可能是真的！这完全取决于您如何实现您正在使用的数据结构！

然而，很可能堆栈被认为是线性的，队列可以同时是线性的，链表和树是非线性的。

Answer 3

对我来说，队列或堆栈只是一种规范。实现方式可以有所不同。