Фактически, в нашем распоряжении оказываются 2 стека: первый, тот же самый, - стек данных, а второй - стек свободных элементов, включающий все элементы вектора, не вошедшие в стек данных. Указатель top связан с вершинами обоих стеков, его изменение противоположным образом отражается на объеме каждого из них: когда один растет в размере, - другой, наоборот, уменьшается. Соответственно, в приведенном ранее описании следовало бы теперь указать, что при top=0 пуст стек данных, а при top=N пуст стек свободных элементов. При такой интерпретации нам нужно контролировать возникновение двух, не сочетающихся, состояний: пуст стек_1 и пуст стек_2. С точки зрения стековой идеологии, этот подход представляется более естественным, поскольку ситуация переполнения стека данных, которую допускать-то нельзя, вообще исключена благодаря "обычному" контролю пустоты стека свободных элементов.

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

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

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

Итак, имеется 3 стержня, - назовем их левым, средним и правым, - на них можно нанизывать диски. Любой диск, а всего их 64 штуки, разрешено надевать либо на свободный стержень, либо на стержень, верхний диск которого имеет больший диаметр, чем укладываемый. Шаг алгоритма состоит в том, что какой-нибудь диск переносится с одного стержня на другой. В начальном положении все диски нанизаны на левый стержень и, по условиям задачи, необходимо перенести их на правый стержень.

Поскольку операция снятия диска со стержня применима только к верхнему диску, а операция надевания диска осуществляется тоже только сверху, то вполне очевидно, что мы имеем дело с тремя стеками.

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

Рис. 1.

Шаг алгоритма состоит из двух последовательных стековых операций:

Pop (i) и Push (j), где i, j Î {left, middle, right} & i ¹ j, и в исходном состоянии i = left.

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

Для N=2 последовательность шагов такова:

Для N=3:

Каково же количество шагов M алгоритма в общем случае?

Учитывая, что при N=1 диск переносится за один шаг (M=1), при N=2 имеем M=3, а при N=1 - уже M=7, то можно предположить, что между исходным числом дисков и необходимым количеством шагов имеется зависимость вида

M=2N-1.

Если последнее задание вызывает у вас затруднения, - познакомьтесь с приводимым ниже алгоритмом и попробуйте вновь вернуться к программе. А идея состоит в том, что:

• из N дисков со стержня left нужно N-1 верхних перенести на стержень middle;

• по завершении самый большой диск оставался на стержне left; переносим его на стержень right;

• осталось перенести N-1диск (а это мы уже умеем) со стержня middle на стержень right.

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