Страница 335 из 371
/// 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 Т 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>
Во-вторых, если потомок является клиентом некоторого класса, то и этот класс, возможно, также должен быть универсальным, как в нашем случае происходит с классом GenLinkabie<T>:
GenLinkable<T> last; //ссылка на стек (элемент стека)
В-третьих, тип т встречается в тексте потомка всюду, где речь идет о типе элементов, добавляемых в стек, как, например:
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">paзмер стека</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> stackl = new OneLinkStack<int> ();
OneLinkStack<string> stack2 = new OneLinkStack<string>();
ArrayUpStack<double> stack3 = new ArrayUpStack
<double>(10);
stack1.put (11); stackl.put (22);
int x1 = stackl.item(), x2 = stackl.item();
if ((x1 == x2) && (xl == 22)) Console.WriteLine("OK!");
stack1.remove(); x2 = stack1.item();
if ((x1!= x2) && (x2 == 11)) Console.WriteLine("OK!");
stack1.remove(); x2 = (stack1.empty())? 77: stackl.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 показаны результаты работы этой процедуры.