Подібно до багатьох завдань, все залежить від того, як ми збираємося підтримувати ці стеки. Якщо нам потрібно виділити певний простір для кожного стека, можна так і зробити. Але в цьому випадку один з стеків може вичерпати ресурси, а інші будуть практично порожніми.
Можна, звичайно, використовувати більш гнучку систему поділу простору, але це значно ускладнює завдання.
Підхід 1. Фіксована поділ
Можна розділити масив на три рівні частини і дозволити стека розвиток в межах обмеженого простору. Зверніть увагу, що далі ми будемо описувати межі діапазонів за допомогою дужок: квадратні дужки [] означають, що граничні значення входять в діапазон, а круглі дужки - значення не входять.
• Стек 1: [0, n / 3).
• Стек 2: [n / 3, 2n / 3).
• Стек 3: [2n / 3, n].
Код для цього рішення наведено нижче:
Якщо у нас є додаткова інформація про призначення стеків, можна модифікувати алгоритм. Наприклад, якщо передбачається, що в стеці 1 буде більше елементів, ніж в стеці 2, можна перерозподілити простір на користь стека 1.
Підхід 2. Гнучке поділ
Другий підхід - гнучке виділення простору для блоків стека. Коли один з стеків перестає поміщатися в вихідному просторі, ми збільшуємо обсяг необхідного ресурсу і при необхідності зрушує елементи.
Крім того, можна створити масив таким чином, щоб останній стек починався в кінці масиву і закінчувався на початку, - «закільцювати» масив.
Втім, на співбесіді вас не змусять писати настільки складний код, тому ми обмежимося спрощеною версією (псевдокодом).
У подібних завданнях важливо зосередитися на написанні чистого і зручного в супроводі коду. Ви повинні використовувати додаткові класи, як ми зробили з StackData, а блоки коду потрібно виділити в окремі методи. Ця рада стане в нагоді не тільки для проходження співбесіди, його можна використовувати і в реальних задачах.