Интернет-журнал "Домашняя лаборатория", 2007 №9 - Журнал «Домашняя лаборатория»

реализация методов, ни то, как стек будет представлен. Эти вопросы будут решать потомки класса.

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

/// <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 показаны результаты работы этой процедуры.

Рис. 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 (32 458.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. Работа