Рисунок на предыдущей странице иллюстрирует
Рисунок на предыдущей странице иллюстрирует операцию
put(s, x), выполняемую над стеком
s и элементом
x.
Функция remove возвращает новое состояние стека с вытолкнутым верхним элементом, если таковой был. Как и put, эта функция при проектировании и реализации должна превращаться в команду (операцию, изменяющую объект, обычно реализуемую как процедура). Мы увидим далее, как учесть возможность пустого стека, с вершины которого нечего удалять.
Функция item возвращает верхний элемент стека, если таковой имеется.
Функция empty выявляет пустоту стека, ее результатом является логическое значение (истина или ложь). Предполагается, что АТД BOOLEAN, задающий логические значения, определен отдельно.
Функция new создает пустой стек.
В разделе
ФУНКЦИИ эти функции определяются не полностью, вводятся только их
сигнатуры - списки типов их аргументов и результата. Сигнатура функции
put
STACK [G] × G → STACK [G]
показывает, что
put берет в качестве аргумента пару вида <s,x>, в которой
s - экземпляр типа
STACK [G], а
x - экземпляр типа
G, и возвращает в качестве результата экземпляр типа
STACK [G]. Вообще говоря, множество значений функции (его тип указывается в сигнатуре правее стрелки, здесь это
STACK [G]) может само быть декартовым произведением. Это можно использовать при описании операций, возвращающих два или более результатов.
В сигнатуре функций
remove и
item вместо обычной стрелки используется перечеркнутая стрелка
. Это означает, что эти функции применимы не ко всем элементам множества входов. Описание функции
new выглядит просто как
new: STACK
без всякой стрелки в сигнатуре. Фактически, это сокращение для записи
new: → STACK,
определяющей функцию без аргументов. Здесь аргументы не нужны, поскольку
new должна всегда возвращать один и тот же результат - пустой стек. Поэтому для простоты мы убрали здесь стрелку. Результат применения этой функции (т. е. пустой стек) будет записываться
new, как сокращение для new(), обозначающего результат применения
new к пустому списку аргументов.
Начало Назад Вперед
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий