Реализовать стек в c

Question

Я хочу сделать стек, который работает с динамическим распределением памяти, но мне нужно знать, о котором он более эффективен:
, чтобы иметь начальный размер, например, 10, а затем я удваиваю его, если я нужно больше.
или у меня может быть начальный размер = 1 и для каждого нового ввода, добавляющего одно место. !?!

int *tmp = malloc(sizeof(int) * 2 * dm->capacity); \* dm->capacity = 10 *\ 
int *tmp = malloc(sizeof(int)); 

Answer 1

Удвоение при необходимости путь более эффективным.

Если выделить новый массив для каждой операции нажимной, то вы делаете объем работы, пропорциональную площади числа элементов стеки (когда вы нажимаете элемент N+1, вы должны скопировать предыдущие N элементов в новый массив).

Если вы при необходимости удваиваете массив, то количество копий, которое вы делаете, пропорционально логарифму N, а для любого нетривиального стека размеров это значительно меньше, как вы знаете.

Answer 2

Это сломанный вопрос. Что «более эффективно» полностью зависит от вашего домена. Если у вас много стеков длин 3 и 4, то выделение 10 спереди и последующее спящее 5 лет будет быстрее, чем начиная с 1 и удвоения. Если у вас много стеков длины 1, то это отходы для распределения 10.

Конечно, когда я говорю «отходы», я имею в виду трату нескольких драгоценных наносекунд, которые вы никогда не сможете вернуть. Предполагая, что вы на «обычном» компьютере и не реализуете C в Game of Life в Conway или что-то необычное, и в этом случае эти выделения могут иметь значение. Итак, профиль и узнайте.

Если вам нужно что-то простое и более эффективное, чем нет, то при необходимости после этого выделите 10 спереди и дважды.

Answer 3

зависит от цели. Обычно удвоение будет более эффективным, но этот подход может растратить значительное пространство (до половины выделенного пространства не используется). У вашего подхода «один за другим» этот недостаток нет. Однако на самом деле неэффективно копировать весь массив при каждом добавлении. Таким образом, если бы эффективность вашего пространства была вашей главной задачей, вам может быть лучше представить ваш стек как связанный список.

Answer 4

Амортизированная стоимость удвоения размера стека при необходимости намного ниже, чем инициализация до 1. Так что да, удвоение лучше. При этом я также рекомендую правильную схему удаления. Что-то вдоль линий освобождения половины стека, когда используется 1/4 текущего стека. Таким образом, добавление и вычитание кромок не разрушают эффективность.