Стек реализован с динамическим массивом

Question

Предположим, мы реализуем стек, используя динамически распределенный массив.Если массив заполняется, мы сталкиваемся с дилеммой.Из следующих вариантов выберите тот, который лучше всего описывает нашу стратегию обработки заполненного массива.

(a) Мы объявляем новый массив, вдвое больший, чем оригинал, и копируем данные вновое пространство для общей стоимости O (n) по последовательности из n нажатий.

(b) Мы объявляем другой массив и отслеживаем, какой из двух (или более) массивов содержит текущую вершинустека в закрытом члене класса стека.Это стоит нам O (1) за толчок.

(c) Для некоторого фиксированного k мы создаем новый массив размером n + 2 ^ k и копируем данные в новое пространство для средней стоимости O(1) на операцию push.

(d) Мы избегаем реализации стека с использованием динамически выделяемого массива, потому что перераспределять память неэффективно.

(e) Ни один из этих ответовэто разумный ответ.

Я почти уверен, что правильный ответ, но я не понимаю, почему это был бы лучший ответ среди других?Другие даже практичны?Они кажутся мне в порядке.Например, c - это почти то же самое, что `a, нет?Почему удвоение выгоднее, чем постоянное увеличение?А как насчет других вариантов - почему они не работают?

Answer 1

Скажем, ваш стек состоял из 128 элементов, и вам пришлось хранить в нем 4096 элементов. Сколько раз вам пришлось бы изменять размер массива при удвоении или расширении его на постоянные 128 элементов каждый раз?

Answer 2

Это похоже на домашнее задание и, возможно, домашний тест, поэтому я намеренно опущу что-то из своих ответов.

a) Попытка предоставить доказательства для утверждения O(n).Сравните с вашим доказательством для b).

b) Как вы храните набор используемых подмассивов?(Это черепаха до упора.)

c) Попытка предоставить доказательства для утверждения O(1).Сравните с вашим доказательством для а).

г) Все альтернативы имеют свои недостатки.Сравните их.Обратите внимание, что в программировании в реальном времени вы не можете использовать динамически перераспределенный массив, и вы должны использовать что-то вроде связанного списка.Почему?

e) Если что-либо из перечисленного является разумным, это тривиально неверно.И наоборот.