c++ - 实现堆栈和队列

Question

什么是实现堆栈和队列的最佳解决方案:

从头开始(列表类似)

使用合成(使用列表)

使用继承(从列表派生)

使用标准:时间复杂度，代码简单性，可维护性。

Answer 1

堆栈和队列是相对简单的数据结构。如果使用得当，则对于所有实现而言，它们的时间复杂度通常为O(1)。您只需要从队列或堆栈的前端获取数据，然后分别在后端或前端插入新数据。因此，您无需搜索数据结构，因为您知道在何处插入和删除数据。 https://www.bigocheatsheet.com/

至于代码的简单性和维护性，从头开始创建代码很可能是最糟糕的。您将必须自己完成所有工作，并且必须修复所有可能导致自己无法解决的问题。 (老实说，我喜欢尝试自己创建数据结构，因为尽管有明显的缺点，但我仍然可以了解很多复杂的细节。)

除非您需要为特定用例在列表中添加其他功能，否则不需要继承。如果您不需要更改任何内容，那么充其量您基本上只是在使用标准列表，而在最坏的情况下，您可能只是在做额外的工作。

仅使用常规列表的优点是已经为您制作了该列表，并且由其他程序员维护。因此，这可能是最好的。

但是，C++有一个队列和堆栈模板，这可能是大多数用例的最佳选择，因此，如果您不需要任何特殊的东西，我会使用它。

希望这对您有帮助。