Как реализовать три стека, используя один массив

Question

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

Для реализации 2 стеков в массиве, это довольно очевидно: 1-й стек увеличивается от LEFT до RIGHT, а 2-й стек - от RIGHT до LEFT; и когда пересечет stackTopIndex, это сигнализирует о переполнении.

Заранее спасибо за ваш проницательный ответ.

Answer 1

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

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

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

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

Answer 2

См. Кнут, Искусство компьютерного программирования, том 1 , раздел 2.2.2.под названием «Последовательное распределение».Обсуждается распределение нескольких очередей / стеков в одном массиве, алгоритмы, связанные с переполнением и т. Д.

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

Разбить массив на любые 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% космических отходов.

Answer 6

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

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

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

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

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

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

Answer 7

Предположим, у вас есть только целочисленный индекс. если он обрабатывается с использованием FILO (First In Last Out) и не ссылается на отдельного человека, а использует только массив в качестве данных. Использование 6 пробелов в качестве ссылки на стек должно помочь:

[ head-1, last-1, head-2, last-2, head-3, last-3, данные, данные, ..., данные]

Вы можете просто использовать 4 пробела, потому что head-1 = 0 и last-3 = длина массива. При использовании FIFO (First In First Out) вам необходимо выполнить повторную индексацию.

Примечание: я работаю над улучшением своего английского.

Answer 8

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

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

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

Answer 9

1. Создайте HashMap с ключами к начальной и конечной позициям, например <"B1", 0>, <"E1", n / 3>

2. для каждого Push (значения) добавьте условие, чтобы проверить, предшествует ли положение Bx Ex или есть какой-то другой «By» между ними. - давайте назовем это условие (2)

3. с учетом вышеуказанных условий, если выше (2) верно // если B1 и E1 в порядке {если (S1.Push ()), то E1 ++; else // условие переполнения, {начать толкать в конце E2 или E3 (в зависимости от того, что есть пробел) и обновить E1 до E2-- или E3--; } }

   если выше (2) ложно {если (S1.Push ()), то E1 -; else // условие переполнения, {начать толкать в конце E2 или E3 (в зависимости от того, что есть пробел) и обновить E1 до E2-- или E3--; } }

Answer 10

Довольно глупое, но эффективное решение может быть:

• Хранить первые элементы стека в i*3 позициях: 0,3,6, ...
• Хранить элементы второго стека в позициях i*3+1: 1,4,7 ...
• И третьи элементы стека в i*3+2 позициях.

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