Здесь есть много компромиссов, и я не думаю, что есть «правильный» ответ на этот вопрос.
Если вы реализуете стек, используя связанный список с указателем хвоста, тогда худшийрегистром времени для push, pop или peek является O (1).Однако каждый элемент будет иметь некоторые дополнительные издержки, связанные с ним (а именно, указатель), что означает, что для структуры всегда есть O (n) служебных данных.Кроме того, в зависимости от скорости вашего распределителя памяти, стоимость выделения новых узлов для стека может быть заметной.Кроме того, если вы будете постоянно извлекать все элементы из стека, вы можете столкнуться с падением производительности из-за плохой локальности, поскольку нет гарантии, что ячейки связанного списка будут храниться в памяти непрерывно.
ЕслиВы реализуете стек с помощью динамического массива, затем время выполнения амортизируемое для push или pop равно O (1), а стоимость просмотра в худшем случае равна O (1).Это означает, что если вы заботитесь о стоимости какой-либо отдельной операции в стеке, это может быть не лучшим подходом.Тем не менее, распределение происходит нечасто, поэтому общая стоимость добавления или удаления n элементов, вероятно, будет быстрее, чем соответствующая стоимость в подходе на основе связанного списка.Кроме того, накладные расходы памяти при таком подходе обычно лучше, чем накладные расходы памяти в связанном списке.Если ваш динамический массив просто хранит указатели на элементы, то в худшем случае происходит перегрузка памяти, когда половина элементов заполнена, и в этом случае имеется n дополнительных указателей (так же, как в случае, когда вы использовали связанныйlist), и в лучшем случае, когда динамический массив заполнен, пустых ячеек нет, а дополнительные издержки составляют O (1).Если, с другой стороны, ваш динамический массив напрямую содержит элементы, в худшем случае затраты памяти могут быть хуже.Наконец, поскольку элементы хранятся смежно, существует лучшая локальность, если вы хотите непрерывно выталкивать или выталкивать элементы из стека, поскольку все элементы находятся в памяти рядом друг с другом.
Короче говоря:
- Подход со связанным списком имеет гарантии O (1) в худшем случае для каждой операции;динамический массив имеет амортизированные гарантии O (1).
- Локальность связанного списка не так хороша, как локальность динамического массива.
- Вероятна общая нагрузка на динамический массивбыть меньше, чем общая нагрузка связанного списка, при условии, что оба указателя хранилища на их элементы.
- Суммарные накладные расходы динамического массива, вероятно, будут больше, чем у связанного списка, если элементы хранятся непосредственно.
Ни одна из этих структур явно не "лучше", чем другая.Это действительно зависит от вашего варианта использования.Лучший способ выяснить, что быстрее, - это рассчитать время и посмотреть, что работает лучше.
Надеюсь, это поможет!