Как реализовать два стека в одном массиве?

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

Я пытаюсь решить Excercise 10.1-2 из главы 10 «Элементарные структуры данных» из второго издания CLRS. Вот что говорится:

Объясните, как реализовать два стека в одном массиве A [1..n] таким образом, чтобы ни один из стеков не переполнялся, если общее количество элементов в обоих стеках вместе не равно n . Операции PUSH и POP должны выполняться за O (1) раз.

Решение, которое я нашел до сих пор:

Пусть массив A [1..n] реализует два стека: S1 [1..i] и S2 [i..n] .

Для операций PUSH-S1 и PUSH-S2 , если стек заполнен, тогда начните помещать элементы в другой стек (например, если стек S1 заполнен, когда новый элемент пытается быть вставленным, затем вставьте этот элемент в стек S2 и наоборот).

Проблема с этим подходом заключается в том, что я не смогу надежно POP-S1 или POP-S2, поскольку нет способа «запомнить», какой элемент принадлежит какому стеку. Если элементы стека являются парами (ключ, значение) , ключом является номер стека, то для извлечения элемента мне придется искать, в худшем случае, i или (ni) раз - что будет O (n). ) (не стесняйтесь поправлять меня, если я ошибаюсь), что не будет O (1) .

Я уже давно бьюсь над этим вопросом. Я на правильном пути? Может кто-нибудь дать мои возможные указатели для решения этой проблемы?

В общем, как мне «думать» об этих проблемах? Или только действительно умные люди могут решить такие проблемы? Поможет ли мне решение таких проблем (например, получение опыта) стать лучше?

Я жду просветления.

Еще один совет в дополнение к тому, что сказал Ювал: это помогает определенным образом размещать стеки в массивах и соответственно фиксировать направление их роста. Они не должны расти в одном направлении.

Вот несколько советов:

1. Один из стеков должен расти «вверх», а другой «вниз».
2. Нет способа «запомнить», какой элемент принадлежит какому стеку - вам разрешено использовать дополнительные переменные, чтобы помочь вам с такими вещами. (Это имеет больше смысла с решением, предложенным первой подсказкой.)

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

Этот метод эффективно использует доступное пространство. Это не вызывает переполнение, если в arr [] есть свободное место. Идея состоит в том, чтобы начать два стека из двух крайних углов arr []. stack1 начинается с самого левого элемента, первый элемент в stack1 помещается с индексом 0. Stack2 начинается с самого правого угла, первый элемент в stack2 помещается с индексом (n-1). Оба стека растут (или сжимаются) в противоположном направлении. Чтобы проверить переполнение, все, что нам нужно проверить - это пространство между верхними элементами обоих стеков.

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

Некоторые намеки

Сделать массив

Элементы массива с нечетным индексом предназначены для stack1

Элементы массива с четным индексом предназначены для stack2

Теперь вы можете вырастить оба стека слева направо

Просто держите переменные, которые поддерживают верхнюю позицию обоих стеков. Вам не придется искать в массиве.

и если stack1 заполняется, а stack2 пуст, вы можете отслеживать дополнительные элементы stack1 в stack2, поддерживая некоторые переменные