Реализация K стеков в одном алгоритме массива

Question

Как реализовать K стеков в массиве с наилучшим использованием хранилища (стеки должны быть динамическими)?

Answer 1

Что ж, если вы беспокоитесь только об использовании пространства и не заботитесь о том, что операции со стеком могут занять O(N), вы можете использовать первые несколько ячеек массива для управления стеками:

Array[0] - конец стека 0

Array[1] - конец стека 1

...

Array[K-1] = конец стека K

Стек n начинается с Array[n-1] и заканчивается Array[n] (exclusive - [Array[n-1], Array[n]) ).If Array[n-1]==Array[n] стек пуст.Первый стек начинается с K, поэтому сначала Array[0]..Array[K-1] = K

Когда вы вставляете в стек, просто переместите все элементы в стопках под ним и соответственно отрегулируйте указатели.

Itвы получите нужное вам ограничение памяти.

Answer 2

О-о-о-о, если K тоже динамический, вы просто делаете массив элементов K динамическим. Увеличить его просто означает сброс всех стеков. Поэтому, если вы не возражаете против O (N) операций push и pop, K не должно быть константой.

Интересно, получил ли я работу?

Answer 3

Ответ 1: сохраняйте указатели стека K в начале.теперь отметьте первый адрес после этого как адрес 0 (делает жизнь проще), четный стек K (stack_0, stack_2, ...) должен расти вверх;нечетный стек K (stack_1, ..) должен расти вниз при инициализации сегмента массива на K / 2 частей (предполагается, что K четный для простоты).stack0 начинается с адреса 0 stack1 начинается с (arraySize / (k / 2)) и растет вниз stack3 начинается с (arraySize / (k / 2)) и растет вверх

при переносе данных в определенный стек, мы должныубедитесь, что он не переполняется в соседний стек, в противном случае выдается исключение.

массив должен выглядеть следующим образом: [[указатели стека] [stack_0] [stack_1] ... [stack_k]] где stack [0] и stack [1] оба совместно используют одну и ту же область, поэтому они могут сделатьоптимальное использование доступного для них пространства.

возможна дальнейшая оптимизация путем объединения каждого большого стека с небольшим стеком (это можно сделать путем проверки поведения стеков во времени).Также может помочь объединение быстро меняющихся массивов с медленно меняющимися массивами.

Ответ 2: подумав немного об этом, я увидел, что мое первое решение гарантирует использование только array_size / (k / 2) (поскольку, если у нас есть только один массив размером array_size / (k / 2), мыполучит переполнение стека).следующее (совершенно непрактичное) решение может удовлетворить требования: мы выделяем начало массива для наших k-указателей стека и с этого момента игнорируем эту область.В остальной части массива мы смотрим на каждую ячейку как на структуру [data, previous, next].

push (stack_i, data) -> получить sp_i из области указателей стека.затем перейдите по этому адресу, заполните указатель «next», чтобы он указывал на следующую пустую ячейку в массиве (мы могли бы связать все пустые места в другом стеке, так что это o (1)).в ячейке "next" сохраните наши данные и заполните указатель "prev".обновить sp_i

pop (stack_i) -> получить sp_i.получить "данные" из этой ячейки."prev" из этой ячейки - наш новый sp_i.переместите старую (теперь пустую) ячейку в пустой список.