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