Стек. От абстрактного, универсального класса к конкретным версиям
Возьмем классическую задачу определения стека. Следуя схеме, определим абстрактный универсальный класс, описывающий всевозможные представления стеков:
/// <summary> /// Абстрактный класс GenStack<T> задает контейнер с /// доступом LIFO: /// Функции: /// конструктор new: -> GenStack<T> /// запросы: /// item: GenStack -> T /// empty: GenStack -> Boolean /// процедуры: /// put: GenStack*T -> GenStack /// remove: GenStack -> GenStack /// Аксиомы: /// remove(put(s,x)) = s /// item(put(s,x)) = x /// empty(new)= true /// empty(put(s,x)) = false /// </summary> abstract public class GenStack<T> { /// <summary> /// require: not empty(); /// </summary> /// <returns>элемент вершины(последний пришедший)</returns> abstract public T item(); /// <summary> /// require: not empty(); /// ensure: удален элемент вершины(последний пришедший) /// </summary> abstract public void remove(); /// <summary> /// require: true; ensure: elem находится в вершине стека /// </summary> /// <param name="elem"></param> abstract public void put(T t); /// <summary> /// require: true; /// </summary> /// <returns>true если стек пуст, иначе false </returns> abstract public bool empty(); }// class GenStack
В приведенном примере программного текста чуть-чуть. Это объявление абстрактного универсального класса:
abstract public class GenStack<T>
и четыре строки с объявлением сигнатуры его методов. Основной текст задает описание спецификации класса и его методов. Заметьте, здесь спецификации заданы достаточно формально с использованием аксиом, характеризующих смысл операций, которые выполняются над стеком.
Не хочется вдаваться в математические подробности, отмечу лишь, что, если задать последовательность операций над стеком, то аксиомы позволяют точно определить состояние стека в результате выполнения этих операций. Как неоднократно отмечалось с первых лекций курса, XML-отчет, построенный по этому проекту, будет содержать в читаемой форме все спецификации нашего класса. Отмечу еще, что все потомки класса должны удовлетворять этим спецификациям, хотя могут добавлять и собственные ограничения.
Наш класс является универсальным - стек может хранить элементы любого типа, и конкретизация типа будет производиться в момент создания экземпляра стека.
Наш класс является абстрактным - не задана ни реализация методов, ни то, как стек будет представлен. Эти вопросы будут решать потомки класса.
Перейдем теперь ко второму этапу и построим потомков класса, каждый из которых задает некоторое представление стека и соответствующую этому представлению реализацию методов. Из всех возможных представлений ограничимся двумя. В первом из них стек будет представлен линейной односвязной списковой структурой. Во втором - он строится на массиве фиксированного размера, задавая стек ограниченной емкости. Вот как выглядит первый потомок абстрактного класса:
/// <summary> /// Стек, построенный на односвязных элементах списка GenLinkable<T> /// </summary> public class OneLinkStack<T> : GenStack<T> { public OneLinkStack() { last = null; } GenLinkable<T> last; //ссылка на стек (вершину стека) public override T item() { return (last.Item); }//item public override bool empty() { return (last == null); }//empty public override void put(T elem) { GenLinkable<T> newitem = new GenLinkable<T>(); newitem.Item = elem; newitem.Next = last; last = newitem; }//put public override void remove() { last = last.Next; }//remove }//class OneLinkStack
