Я думаю, что этот вопрос кроется в том, что если вы хотите представить два стека одновременно, это можно сделать с помощью одного массива элементов.В типичной реализации массива стека элементы хранятся в массиве с некоторым количеством «свободного пространства», доступного для роста.Когда это пространство исчерпано, размер массива увеличивается (обычно путем удвоения для получения амортизированных вставок O (1)), старые элементы копируются, и рост может продолжаться.
Этот подход работает очень хорошо,но если вы знаете, что у вас будет два стека, это можно сделать немного лучше.В частности, предположим, что у вас есть два стека, в каждом из которых есть «свободное пространство», а одному из стеков не хватает свободного пространства.Если это произойдет, было бы здорово, если бы можно было использовать часть неиспользованного свободного пространства из другого стека для продолжения наращивания первого стека.Это сэкономило бы нам дополнительное выделение / копирование и позволило бы нам более эффективно использовать имеющееся у нас пространство.
Один из способов сделать это, если у вас есть два стека, - это иметь дваони разделяют массив и растут с противоположных сторон внутрь.Например, если у меня есть один стек с элементами 1 2 3 и другой с элементами 4 5 6, то это может иметь следующее представление в памяти:
[1] [2] [3] [ ] [ ] [6] [5] [4]
Если мы поместим значение в первый стек,скажем, 9, мы увеличиваем стек следующим образом:
[1] [2] [3] [9] [ ] [6] [5] [4]
Если мы помещаем значение во второй стек, скажем, 0, мы увеличиваем его стек как
[1] [2] [3] [9] [0] [6] [5] [4]
Если сейчас нам нужно увеличить любой стек, нажав значение, то мы бы использовали стандартную технику перераспределения, чтобы переместить его в больший массив.Однако преимущество заключается в том, что если один стек в основном пуст, а другой достаточно велик, мы можем очень эффективно использовать нашу память.Например, вот одна из возможных конфигураций стека:
[1] [2] [3] [4] [5] [6] [ ] [0]
Здесь один стек имеет шесть значений, а один стек имеет только одно.Обратите внимание, что мы очень эффективно используем наше пространство, разделяя массив.