Бертран Мейер - Основы объектно-ориентированного программирования

Существует несколько физических представлений стеков:

Рис. 6.1. Три возможных представления стеков

Этот рисунок иллюстрирует три наиболее популярных представления стеков. Для удобства ссылок дадим каждому из них свое имя:

[x]. МАССИВ_ВВЕРХ : представляет стек посредством массива representation и целого числа count , с диапазоном значений от 0 (для пустого стека) до capacity - размера массива representation , элементы стека хранятся в массиве и индексируются от 1 до count .

[x]. МАССИВ_ВНИЗ : похож на МАССИВ_ВВЕРХ , но элементы помещаются в конец стека, а не в начало. Здесь число, называемое free , является индексом верхней свободной позиции в стеке или 0, если все позиции в массиве заняты и изменяется в диапазоне от capacity для пустого стека до 0 для заполненного. Элементы стека хранятся в массиве и индексируются от capacity до free +1.

[x]. СПИСОЧНОЕ : при списочном представлении каждый элемент стека хранится в ячейке с двумя полями: item , содержащем сам элемент, и previous , содержащем указатель на ячейку с предыдущим элементом. Для этого представления нужен также указатель last на ячейку, содержащую вершину стека.

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

Для представлений с помощью массивов МАССИВ_ВВЕРХ и МАССИВ_ВНИЗ команды увеличивают или уменьшают указатель на вершину ( count или free ) и присваивают x соответствующему элементу массива. Так как эти представления поддерживают стеки с не более чем capacity элементами, то корректные реализации должны содержать защищающие от переполнения тесты соответствующего вида:

if count " capacity then ...

if free " 0 then ...,

(на рисунке они для простоты опущены).

Для представления СПИСОЧНОЕ вталкивание элемента требует четырех действий:

[x].создания новой ячейки n (здесь оно выполняется с помощью процедуры Паскаля new , которая выделяет память для нового объекта);

[x].присваивания x полю item новой ячейки;

[x].присоединения новой ячейки к вершине стека путем присвоения ее полю previous текущего значения указателя last ;

[x].изменения last так, чтобы он ссылался на только что созданную ячейку.

Хотя эти представления встречаются чаще всего, существует и много других представлений стеков. Например, если вам нужны два стека с однотипными элементами и память для их представления ограничена, то можно использовать один массив с двумя метками вершин count как в представлении МАССИВ_ВВЕРХ и free как в МАССИВ_ВНИЗ . При этом один стек будет расти вверх, а другой - вниз. Условием полного заполнения этого представления является равенство count= free .

Преимущество такого представления состоит в уменьшении риска переполнить память: при двух массивах размера n , представляющих стеки способом МАССИВ_ВВЕРХ или МАССИВ_ВНИЗ , память исчерпается, как только любой из стеков достигнет n элементов. А в случае одного массива размера 2n , содержащего два стека лицом к лицу, работа продолжается до тех пор, пока их общая длина не превысит 2n , что менее вероятно, если стеки растут независимо друг от друга. (Для любых переменных p и q , max (p +q) "= max (p) + max (q) ).

Рис. 6.2. Представление двух стеков лицом к лицу

Каждое из этих и другие возможные представления полезны в разных ситуациях. Выбор одного из них в качестве эталона для определения стека был бы типичным примером излишней спецификации. Почему мы должны, например, предпочесть МАССИВ_ВВЕРХ представлению СПИСОЧНОЕ ? Большинство видимых свойств представления МАССИВ_ВВЕРХ - массив, число count , верхняя граница - несущественны для понимания представляемой ими структуры.

Почему так плохо использовать конкретное представление в качестве спецификации?

Можно напомнить результаты изучения Линцем (Lientz) и Свенсоном (Swanson) стоимости сопровождения. Было установлено, что более 17% стоимости ПО приходится на изменения в форматах данных. Ясно, что метод, который ставит анализ и проектирование в зависимость от физического представления структур данных, не обеспечит разработку достаточно гибкого ПО.

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

Как бы стеки не заставили нас забыть, что кроме излюбленных специалистами по информатике примеров имеются структуры данных, тесно связанные с объектами реальной жизни. Вот забавный пример, взятый из почты форума Риски (Risks) (группа новостей Usenet comp.risks), который иллюстрирует опасности взгляда на данные, чересчур сильно зависящего от их конкретных свойств. Некто Даррелл Д. Е. Лонг, которого родители наградили двумя инициалами второго имени, получил кредитную карточку, в которой был указан лишь первый из них "Д". После обращения к менеджеру фирмы TRW ему была прислана другая карточка, в которой был лишь второй инициал "Е". Он пишет:

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

Автор приведенного выше письма, в основном, беспокоился из-за ненужной почты, что неприятно, но не смертельно, архивы форума Риски (Risks) полны случаями вызванной компьютерами неразберихи с гораздо более серьезными последствиями. Уже отмечавшаяся выше "проблема миллениума" является другим примером опасности, возникающей при организации доступа к данным на основе их физического представления, ее последствия обошлись в сотни миллионов долларов.