Можно ли реализовать три стека в одном массиве с O (1) push / pop?

Два стека могут быть эффективно реализованы с использованием одного массива фиксированного размера: стек № 1 начинается с левого конца и увеличивается вправо, а стек № 2 начинается с правого конца и увеличивается влево. Возможно ли то же самое для трех стеков?

Более конкретно, возможно ли реализовать три стека при следующих условиях:

У вас есть массив фиксированного размера, который может содержать N объектов.
Пока сумма трех размеров стека <N, push () не должна завершиться ошибкой.
Операции push () и pop () должны занимать O (1) времени.
В дополнение к массиву вы можете использовать только O (1) дополнительное пространство.

Вот примеры решений, которые не удовлетворяют этим требованиям:

Разбиение массива на 3 фиксированные части и использование каждой части для стека (нарушает 2).
Аналогично вышеописанному, но с подвижными границами между стопками (нарушает 3).
Простые реализации на основе связанного списка (нарушает 4).

Я приму нетривиальные алгоритмы или доказательства невозможности, даже если они точно не удовлетворяют всем условиям (1) - (4), например, алгоритм, где push / pop берет O (1) амортизированное время, или где дополнительная память меньше, чем O (N), например, O (log N). Или доказательство невозможности, которое показывает, что, например, доступ менее чем к 5 элементам массива за push / pop невозможен.

ds.data-structures lower-bounds user1020406
источник

Я не знаю, считаете ли вы это нарушением требования 4, но если каждый «объект» в вашем массиве N объектов может включать в себя дополнительное поле, такое как целочисленный индекс, тогда вы можете реализовать «связанные списки» внутри своего массива. , Вы можете хранить индекс вершины каждого из 3 стеков, используя 3 внешние переменные, и каждый «объект» может указывать на предыдущий элемент в своем стеке.

Ави Тал

Под «объектами» я понимал вещи, которые push () принимает, а pop () возвращает. С точки зрения реализации стека, это просто непрозрачные сгустки данных (например, объект может быть 32-разрядным целым числом). Реализация стека не должна каким-либо образом изменять эти объекты.

user1020406

Считайте, что вы сначала делаете последовательность

N

$N$ Push-операции, а затем только поп-операции. Что-нибудь известно об этой версии проблемы?

Дмитрий Урбанович

Было бы

O (\sqrt{N})

$O(\sqrt{N})$ Вас устраивает дополнительное пространство?

Дмитрий Урбанович

Re: «N толкает, а затем N всплывает» версия: я не знаю, но даже идентификация этого как интересной подзадачи полезна, потому что даже там не ясно, возможно ли решение O (1). См. Ответ @ Alexei и ветку комментариев для верхней границы. Что касается

O (\sqrt{N})

$O(\sqrt N)$ Решение, да, я приму. Я новичок в публикации вопросов на stackexchange, поэтому я не уверен, как обращаться со случаями, когда со временем могут быть предоставлены лучшие и лучшие решения. Один из подходов, который я видел, состоял в том, чтобы подождать день или около того, прежде чем принять ответ, в случае, если что-то получится лучше, поэтому я сделаю это.

user1020406

Ответы:

Фредман и Голдсмит показали в «Трех стеках» (Журнал Алгоритмов, 1994), что $\Theta(n^\varepsilon)$ биты потраченного впустую пространства достижимы. Это также минимум, необходимый для массивов размером не менее 16 кв. Я описал простой алгоритм траты $\Theta(\sqrt{n})$ Слова пробела в моем StackOverflow ответят на этот вопрос . Как отметил @ dmitri-urbanowicz в комментариях, это в основном просто обрабатывает массив как $\sqrt{n}$ блоки размера $\sqrt{n}$ где каждый блок используется ровно для одного стека и содержит единственный указатель на следующий блок в этом стеке.

jbapple
источник

Пусть N будет длиной основного массива. Я могу представить стеки как связанные списки больших чанков, так что общее количество чанков не превышает O (log2 (N)). Поместите третий стек между первыми двумя по индексу N / 2. Итак, у нас есть 3 занятых зоны и 2 свободных. Когда стек не может принять следующий элемент, это означает, что одна свободная область исчерпана. Если другой исчерпан, то вся память исчерпана. В противном случае есть еще одна свободная зона размером не более N / 2. Продолжайте переполненный стек в эту свободную область. так что вся конфигурация напоминает первоначальную компоновку стеков. Поскольку свободной памяти сейчас не больше половины начальной, таких операций связывания будет не более log2 (N). Каждая операция связывания требует фиксированного объема памяти для сохранения предыдущего состояния стека. Так,

Алексей Кайгородов
источник

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

Эмиль Йержабек

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

Алексей Кайгородов

Поппинг - действительно проблема здесь, но конструкция Алексея обеспечивает хорошую верхнюю границу для версии проблемы, о которой Дмитрий спрашивал в комментариях: что, если мы потребуем, чтобы все толчки происходили до всех всплывающих окон? Интересно, возможно ли в этом случае что-либо лучше, чем O (log N).

user1020406