Как реализовать три стека с помощью единого массива

Вы можете реализовать три стека с связанным списком :

• Вам нужен указатель, указывающий на следующий бесплатный элемент. Еще три указателя возвращают последний элемент каждого стека (или ноль, если стек пуст).
• Когда в стек добавляется еще один элемент, он должен использовать первый свободный элемент и установить свободный указатель на следующий свободный элемент (в противном случае возникнет ошибка переполнения). Его собственный указатель должен указывать на новый элемент, оттуда обратно к следующему элементу в стеке.
• Когда из стека удаляется элемент, он возвращается обратно в список свободных элементов. Собственный указатель стека будет перенаправлен на следующий элемент стека.

Связанный список может быть реализован в массиве.

Насколько это (пространство) эффективно?
Нет проблем создать связанный список, используя две ячейки массива для каждого элемента списка (значение + указатель). В зависимости от спецификации вы даже можете поместить указатель и значение в один элемент массива (например, массив длинный, значение и указатель - только int).
Сравните это с решением kgiannakakis ... где вы теряете до 50% (только в худшем случае). Но я думаю, что мое решение немного чище (и, возможно, более академично , что не должно быть недостатком для вопроса на собеседовании ^^).

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

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

Это, безусловно, будет быстро кодировать и понимать. Каковы наши целевые показатели эффективности?

первый стек растет на 3n, второй стек растет на 3n+1, третий растет на 3n+2

для n={0...N}

Это интересная головоломка, и у меня нет реального ответа, но, думая немного нестандартно...

это может зависеть от того, из чего состоит каждый элемент в стеке. Если это три стека флагов true/false, то можно использовать первые три бита целочисленных элементов. Т.е. бит 0 - значение для первого стека, бит 1 - значение для второго стека, бит 2 - значение для третьего стека. Затем каждый стек может расти независимо, пока весь массив не будет заполнен для этого стека. Это еще лучше, так как другие стеки также могут продолжать расти, даже когда первый стек заполнен.

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

Разделить массив на 3 части (независимо от того, разделите ли вы его последовательно или с чередованием). Если один стек превышает 1/3 массива, вы начинаете заполнять концы остальных двух стеков от конца.

aaa bbb ccc
1   2   3
145 2   3
145 2 6 3
145 2 6 3 7
145 286 3 7
145 286 397

Худший случай - когда два стека увеличиваются до 1/3 границы, и тогда у вас остается 30% бесполезного пространства.

Еще один подход (в качестве дополнения к связанному списку) - использовать карту стеков. В этом случае вам придется использовать дополнительные биты log (3 ^ n) / log (2) для построения карты распределения данных в вашем массиве длины n. Каждая из трехзначных частей карты говорит, какой стек владеет следующим элементом. Бывший. a.push (1); b.push (2); c.push (3); a.push (4); a.push (5); предоставит вам изображение

aacba
54321

соответствующее значение карты вычисляется, когда элементы помещаются в стек (со смещением содержимого массива)

map0 = any
map1 = map0*3 + 0
map2 = map1*3 + 1
map3 = map2*3 + 2
map4 = map3*3 + 0
map5 = map4*3 + 0 = any*3^5 + 45

и длина стеков 3,1,1
Как только вы захотите выполнить c.pop () , вам нужно будет реорганизовать свои элементы, найдя фактическое положение c.top () в исходном массиве, пройдя по ячейке- карта (т.е.разделить на 3, а мод на 3 не равно 2), а затем сдвинуть все содержимое в массиве назад, чтобы закрыть эту дыру. Во время прогулки по карте ячеек вам нужно будет сохранить всю пройденную вами позицию ( mapX ), а после прохождения той, которая указывает на стек «c», вам придется еще раз разделить на 3 и умножьте его на 3 ^ (количество переданных позиций - 1) и добавьте mapX , чтобы получить новое значение ячейки-карты.
Накладные расходы для этого фиксированы и зависят от размера элемента стека ( bits_per_value ):
(журнал (3 n) / журнал (2)) / (n журнал (bits_per_value) / log (2)) = log (3 n) / (nlog (bits_per_value)) = log ( 3) / журнал (бит_на_значение)
Таким образом, для bits_per_value = 32 это будет 31,7% накладных расходов на пространство, а с ростом bits_per_value оно будет убывать (т.е. для 64 бит будет 26,4%).

Первая стопка растет слева направо.

Вторая стопка растет справа налево.

Третья стопка начинается с середины. Для простоты предположим, что массив нечетного размера. Тогда третий стек растет следующим образом:

* * * * * * * * * * *
      5 3 1 2 4

Первому и второму стекам разрешено расти максимум на половину размера массива. Третий стек может расти максимум до заполнения всего массива.

Худший сценарий - когда один из первых двух массивов вырастает на 50% массива. Тогда происходит 50%-ная трата массива. Для оптимизации эффективности третий массив должен быть выбран таким образом, чтобы он рос быстрее двух других.

См. Knuth, The Art of Computer Programming, Volume 1, Раздел 2.2.2. под названием "Последовательное распределение". Обсуждается выделение нескольких очередей/стеков в одном массиве, с алгоритмами борьбы с переполнениями и т.д.

Мы можем использовать длинный битовый массив, представляющий, какому стеку принадлежит i-я ячейка массива. Мы можем принимать значения по модулю 3 (00 - пусто, 01 - A, 10 - B, 11 - C). Для массива размером N потребуется N / 2 бит или N / 4 байта дополнительной памяти.

Например, для 1024 длинных элементов int (4096 байт) потребуется всего 256 байт или 6%.

Эта карта битового массива может быть помещена в тот же массив в начале или в конце, просто уменьшив размер данного массива на постоянную 6%!