Стек, реализованный с помощью динамического массива

Question

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

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

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

(с) для некоторого фиксированного к, мы создаем новый массив размера п + 2^к и копировать данные в новое пространство для средней стоимости O (1) на нажимной операции.

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

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

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

Answer 1

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

Answer 2

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

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

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

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

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

e) Если какое-либо из приведенных выше обоснований, это тривиально ложно. И наоборот.