Стек. От абстрактного, универсального класса к конкретным версиям

Возьмем классическую задачу определения стека. Следуя схеме, определим абстрактный универсальный класс, описывающий всевозможные представления стеков:

/// <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

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

public class OneLinkStack<T> : GenStack<T>

Во-вторых, если потомок является клиентом некоторого класса, то и этот класс, возможно, также должен быть универсальным, как в нашем случае происходит с классом GenLinkable<T>:

GenLinkable<T> last; //ссылка на стек (элемент стека)

В-третьих, тип T встречается в тексте потомка всюду, где речь идет о типе элементов, добавляемых в стек, как, например:

public override void put(T elem)

По ходу дела нам понадобился класс, задающий представление элементов стека в списковом представлении. Объявим его:

public class GenLinkable<T>

{

public T Item;

public GenLinkable<T> Next;

public GenLinkable()

{ Item = default(T); Next = null; }

}

Класс устроен достаточно просто, у него два поля: одно для хранения элементов, помещаемых в стек и имеющее тип T, другое - указатель на следующий элемент. Обратите внимание на конструктор класса, в котором для инициализации элемента используется новая конструкция default(T), которая возвращает значение, устанавливаемое по умолчанию для типа T.

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

public class ArrayUpStack<T> : GenStack<T>

{

int SizeOfStack;

T[] stack;

int top;

/// <summary>

/// конструктор

/// </summary>

/// <param name="size">размер стека</param>

public ArrayUpStack(int size)

{ SizeOfStack = size; stack = new T[SizeOfStack]; top = 0; }

/// <summary>

/// require: (top < SizeOfStack)

/// </summary>

/// <param name="x"> элемент, помещаемый в стек</param>

public override void put(T x)

{ stack[top] = x; top++; }

public override void remove()

{ top--; }

public override T item()

{ return (stack[top-1]); }

public override bool empty()

{ return (top == 0); }

}//class ArrayUpStack

Созданные в результате наследования классы-потомки перестали быть абстрактными, но все еще остаются универсальными. На третьем этапе порождаются конкретные экземпляры потомков - универсальных классов, в этот момент и происходит конкретизация типов, и два экземпляра одного универсального класса могут работать с данными различных типов. Этот процесс создания экземпляров с подстановкой конкретных типов называют родовым порождением экземпляров. Вот как в тестирующей процедуре создаются экземпляры созданных нами классов:

public void TestStacks()

{

OneLinkStack<int> stack1 = new OneLinkStack<int>();

OneLinkStack<string> stack2 = new OneLinkStack<string>();

ArrayUpStack<double> stack3 = new ArrayUpStack

<double>(10);

stack1.put(11); stack1.put(22);

int x1 = stack1.item(), x2 = stack1.item();

if ((x1 == x2) && (x1 == 22)) Console.WriteLine("OK!");

stack1.remove(); x2 = stack1.item();

if ((x1 != x2) && (x2 == 11)) Console.WriteLine("OK!");

stack1.remove(); x2 = (stack1.empty())? 77 : stack1.item();

if ((x1 != x2) && (x2 == 77)) Console.WriteLine("OK!");

stack2.put("first"); stack2.put("second");

stack2.remove(); string s = stack2.item();

if (!stack2.empty()) Console.WriteLine(s);

stack3.put(3.33); stack3.put(Math.Sqrt(Math.PI));

double res = stack3.item();

stack3.remove(); res += stack3.item();

Console.WriteLine("res= {0}", res);

}

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

Рис. 22.3. Три разных стека, порожденных абстрактным универсальным классом

Дополним наше рассмотрение еще одним примером работы с вариацией стеков, в том числе хранящим объекты класса Person:

public void TestPerson()

{

OneLinkStack<int> stack1 = new OneLinkStack<int>();

OneLinkStack<string> stack2 = new OneLinkStack<string>();

ArrayUpStack<double> stack3 = new ArrayUpStack

<double>(10);

ArrayUpStack<Person> stack4 = new ArrayUpStack<Person>(7);

stack2.put("Петров"); stack2.put("Васильев");

stack2.put("Шустов");

stack1.put(27); stack1.put(45); stack1.put(53);

stack3.put(21550.5); stack3.put(12345.7);

stack3.put(32458.8);

stack4.put(new Person(stack2.item(), stack1.item(),

stack3.item()));

stack1.remove(); stack2.remove(); stack3.remove();

stack4.put(new Person(stack2.item(), stack1.item(),

stack3.item()));

stack1.remove(); stack2.remove(); stack3.remove();

stack4.put(new Person(stack2.item(), stack1.item(),

stack3.item()));

Person pers = stack4.item(); pers.PrintPerson();

stack4.remove(); pers = stack4.item(); pers.PrintPerson();

stack4.remove(); pers = stack4.item(); pers.PrintPerson();

stack4.remove(); if (stack4.empty()) Console.WriteLine("OK!");

}

Результаты работы этой процедуры приведены на рис. 22.4.

Рис. 22.4. Работа со стеками