Collections — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) |
Juliet (обсуждение | вклад) |
||
Строка 2: | Строка 2: | ||
== Вспомогательные модули == | == Вспомогательные модули == | ||
=== Nodes === | === Nodes === | ||
− | |||
<source lang="Delphi"> | <source lang="Delphi"> | ||
/// Модуль содержит шаблоны классов | /// Модуль содержит шаблоны классов | ||
Строка 13: | Строка 12: | ||
type | type | ||
− | // | + | //-------------------------------------------SINGLE_NODE------------------------------------------- |
/// Узел с одним полем связи | /// Узел с одним полем связи | ||
SingleNode<DataType> = class | SingleNode<DataType> = class | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
/// Значение узла | /// Значение узла | ||
− | data: DataType; | + | data : DataType; |
/// Ссылка на следующий элемент | /// Ссылка на следующий элемент | ||
− | next: | + | next : SingleNode<DataType>; |
− | |||
− | |||
− | |||
/// <summary> | /// <summary> | ||
Строка 143: | Строка 25: | ||
/// <param name="pData">Значение узла</param> | /// <param name="pData">Значение узла</param> | ||
/// <param name="pNext">Ссылка на следующий элемент</param> | /// <param name="pNext">Ссылка на следующий элемент</param> | ||
− | + | constructor Create(pData : DataType; pNext : SingleNode<DataType>); | |
− | constructor Create(pData: DataType; | ||
− | |||
end; | end; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | // -------------------------------------------DOUBLE_NODE------------------------------------------ | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
/// Узел с двумя полями связи | /// Узел с двумя полями связи | ||
DoubleNode<DataType> = class | DoubleNode<DataType> = class | ||
− | |||
/// Значение узла | /// Значение узла | ||
− | data: DataType; | + | data : DataType; |
/// Ссылка на следующий элемент | /// Ссылка на следующий элемент | ||
− | next: DoubleNode<DataType>; | + | next : DoubleNode<DataType>; |
/// Ссылка на предыдущий элемент | /// Ссылка на предыдущий элемент | ||
− | prev: DoubleNode<DataType>; | + | prev : DoubleNode<DataType>; |
− | |||
/// <summary> | /// <summary> | ||
Строка 265: | Строка 44: | ||
/// <param name="pNext">Ссылка на следующий элемент</param> | /// <param name="pNext">Ссылка на следующий элемент</param> | ||
/// <param name="pPrev">Ссылка на предыдущий элемент</param> | /// <param name="pPrev">Ссылка на предыдущий элемент</param> | ||
− | constructor Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>); | + | constructor Create(pData : DataType; pPrev, pNext : DoubleNode<DataType>); |
− | |||
end; | end; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
implementation | implementation | ||
− | // | + | //-------------------------------------------SINGLE_NODE------------------------------------------- |
{Конструктор | {Конструктор | ||
pData — значение узла | pData — значение узла | ||
pNext — cсылка на следующий элемент} | pNext — cсылка на следующий элемент} | ||
− | constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>); | + | constructor SingleNode<DataType>.Create(pData : DataType; pNext : SingleNode<DataType>); |
begin | begin | ||
data := pData; | data := pData; | ||
next := pNext; | next := pNext; | ||
end; | end; | ||
− | |||
− | + | // -------------------------------------------DOUBLE_NODE------------------------------------------ | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | // | ||
{Конструктор | {Конструктор | ||
pData — значение узла | pData — значение узла | ||
pNext — cсылка на следующий элемент | pNext — cсылка на следующий элемент | ||
pPrev — ссылка на предыдущий элемент} | pPrev — ссылка на предыдущий элемент} | ||
− | constructor DoubleNode<DataType>.Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>); | + | constructor DoubleNode<DataType>.Create(pData : DataType; pPrev, pNext : DoubleNode<DataType>); |
begin | begin | ||
data := pData; | data := pData; | ||
next := pNext; | next := pNext; | ||
next := pNext; | next := pNext; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
end; | end; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
end. | end. | ||
Строка 351: | Строка 75: | ||
== Collections == | == Collections == | ||
− | |||
<source lang="Delphi"> | <source lang="Delphi"> | ||
/// Модуль содержит шаблоны классов | /// Модуль содержит шаблоны классов | ||
Строка 359: | Строка 82: | ||
− | // | + | // ===================================================================== INTERFACE ===================================================================== |
interface | interface | ||
uses Nodes; // для использования типа SingleNode<DataType> — | uses Nodes; // для использования типа SingleNode<DataType> — | ||
// узла с одним полем связи | // узла с одним полем связи | ||
+ | |||
+ | const | ||
+ | /// Ширина поля вывода | ||
+ | PRINT_FIELD_WIDTH = 5; | ||
+ | /// Разделитель при выводе элементов | ||
+ | DELIMETR = ' '; | ||
+ | /// Количество элементов, выводимых в одной строке при выводе | ||
+ | ELEMS_IN_LINE = 5; | ||
+ | |||
+ | // ----------------------------------------------STACK--------------------------------------------- | ||
+ | const | ||
+ | /// Сообщение о пустоте стека | ||
+ | EMPTY_STACK = 'Стек пуст'; | ||
type | type | ||
− | |||
− | |||
/// Шаблон класса Stack [Стек] | /// Шаблон класса Stack [Стек] | ||
Stack<DataType> = class | Stack<DataType> = class | ||
− | |||
private | private | ||
/// Вершина стека | /// Вершина стека | ||
− | fTop: SingleNode<DataType> := nil; // field Top | + | fTop : SingleNode<DataType> := nil; // field Top |
− | |||
public | public | ||
− | + | // ---------------------------- Стандартные методы --------------------------- | |
+ | /// Стандартный конструктор | ||
constructor Create; | constructor Create; | ||
+ | /// Конструктор. | ||
+ | /// Создает стек, заполненный элементами, переданными в качестве параметров | ||
+ | constructor Create(params datas : array of DataType); | ||
+ | {/// <summary> | ||
+ | /// Конструктор. | ||
+ | /// Создает стек, заполненный случайными данными | ||
+ | /// </summary> | ||
+ | /// <param name="count">Количество элементов</param> | ||
+ | /// <param name="GenerateRandom">Функция, генерирующая случайный объект</param> | ||
+ | constructor Create(count : integer; GenerateRandom : function : DataType);} | ||
/// Кладет элемент x на вершину стека | /// Кладет элемент x на вершину стека | ||
− | procedure Push(x: DataType); | + | procedure Push(x : DataType); |
− | |||
/// Возвращает элемент типа DataType, снимая его с вершины стека | /// Возвращает элемент типа DataType, снимая его с вершины стека | ||
− | function Pop: DataType; | + | function Pop : DataType; |
/// Возвращает значение элемента на вершине стека | /// Возвращает значение элемента на вершине стека | ||
− | function Top: DataType; | + | function Top : DataType; |
− | |||
/// Возвращает истину, если стек пуст | /// Возвращает истину, если стек пуст | ||
− | function IsEmpty: boolean; | + | function IsEmpty : boolean; |
− | + | // ----------------------------- Вывод содержимого --------------------------- | |
+ | /// <summary> | ||
+ | /// Выводит подряд содержимое стека | ||
+ | /// </summary> | ||
+ | /// <param name="delim">Разделитель между элементами в строке</param> | ||
+ | /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param> | ||
+ | procedure Print(delim : string := DELIMETR; elemsInLine : integer := ELEMS_IN_LINE); | ||
+ | /// Выводит содержимое стека в каждой строке | ||
+ | procedure Println; | ||
end; | end; | ||
− | |||
− | + | // ----------------------------------------------QUEUE--------------------------------------------- | |
− | // | + | type |
/// Шаблон класса Queue [Очередь] | /// Шаблон класса Queue [Очередь] | ||
Queue<DataType> = class | Queue<DataType> = class | ||
− | |||
private | private | ||
/// Голова очереди | /// Голова очереди | ||
− | head: SingleNode<DataType>; | + | head : SingleNode<DataType>; |
/// Хвост очереди | /// Хвост очереди | ||
− | tail: SingleNode<DataType>; | + | tail : SingleNode<DataType>; |
− | |||
public | public | ||
− | /// | + | // ---------------------------- Стандартные методы --------------------------- |
+ | /// Стандартный конструктор | ||
constructor Create; | constructor Create; | ||
− | |||
/// Добавляет элемент x в хвост очереди | /// Добавляет элемент x в хвост очереди | ||
− | procedure Enqueue(x: DataType); | + | procedure Enqueue(x : DataType); |
− | |||
/// Возвращает элемент типа DataType, убирая его из головы очереди | /// Возвращает элемент типа DataType, убирая его из головы очереди | ||
− | function Dequeue: DataType; | + | function Dequeue : DataType; |
− | |||
/// Возвращает истину, если очередь пуста | /// Возвращает истину, если очередь пуста | ||
− | function IsEmpty: boolean; | + | function IsEmpty : boolean; |
− | |||
end; | end; | ||
− | |||
− | // | + | // ================================================================= IMPLEMENTATION =================================================================== |
implementation | implementation | ||
− | // -------------------------------------------------------- | + | // ----------------------------------------------STACK--------------------------------------------- |
− | { | + | |
+ | // ---------------------------- Стандартные методы --------------------------- | ||
+ | {Стандартный конструктор} | ||
constructor Stack<DataType>.Create; | constructor Stack<DataType>.Create; | ||
begin | begin | ||
fTop := nil; | fTop := nil; | ||
end; | end; | ||
+ | {Конструктор. | ||
+ | Создает стек, заполненный элементами, переданными в качестве параметров} | ||
+ | constructor Stack<DataType>.Create(params datas : array of DataType); | ||
+ | begin | ||
+ | fTop := nil; | ||
+ | for var i := 0 to datas.Length - 1 do | ||
+ | Push(datas[i]); | ||
+ | end; | ||
+ | {Конструктор. | ||
+ | Создает стек, заполненный случайными данными | ||
+ | count — количество элементов | ||
+ | GenerateRandom — функция, генерирующая случайный объект} | ||
+ | {constructor Stack<DataType>.Create(count : integer; GenerateRandom : function : DataType); | ||
+ | begin | ||
+ | fTop := nil; | ||
+ | for var i := 1 to count do | ||
+ | Push(GenerateRandom); | ||
+ | end;} | ||
{Кладет элемент x на вершину стека} | {Кладет элемент x на вершину стека} | ||
− | procedure Stack<DataType>.Push(x: DataType); | + | procedure Stack<DataType>.Push(x : DataType); |
begin | begin | ||
fTop := new SingleNode<DataType>(x, fTop); | fTop := new SingleNode<DataType>(x, fTop); | ||
end; | end; | ||
− | |||
{Возвращает элемент типа DataType, снимая его с вершины стека} | {Возвращает элемент типа DataType, снимая его с вершины стека} | ||
− | function Stack<DataType>.Pop: DataType; | + | function Stack<DataType>.Pop : DataType; |
begin | begin | ||
Assert(not IsEmpty); | Assert(not IsEmpty); | ||
− | |||
result := fTop.data; | result := fTop.data; | ||
fTop := fTop.next; // элемент снимается с вершины стека | fTop := fTop.next; // элемент снимается с вершины стека | ||
Строка 449: | Строка 209: | ||
{Возвращает значение элемента на вершине стека} | {Возвращает значение элемента на вершине стека} | ||
− | function Stack<DataType>.Top: DataType; | + | function Stack<DataType>.Top : DataType; |
begin | begin | ||
Assert(not IsEmpty); | Assert(not IsEmpty); | ||
− | |||
result := fTop.data; | result := fTop.data; | ||
end; | end; | ||
− | |||
{Возвращает истину, если стек пуст} | {Возвращает истину, если стек пуст} | ||
− | function Stack<DataType>.IsEmpty: boolean; | + | function Stack<DataType>.IsEmpty : boolean; |
begin | begin | ||
result := (fTop = nil); | result := (fTop = nil); | ||
end; | end; | ||
− | |||
− | + | // ----------------------------- Вывод содержимого --------------------------- | |
− | // -------------------------------------------------------- | + | {Выводит подряд содержимое стека |
− | + | delim — разделитель между элементами в строке | |
+ | elemsInLine — количество элементов, выводимых в одной строке} | ||
+ | procedure Stack<DataType>.Print(delim : string; elemsInLine : integer); | ||
begin | begin | ||
− | + | if IsEmpty then | |
− | + | writeln(EMPTY_STACK) | |
+ | else | ||
+ | begin | ||
+ | var elemsInd := 1; // индекс элемента стека | ||
+ | // нужен для вывода по строкам | ||
+ | var curElem := fTop; | ||
+ | while curElem <> nil do | ||
+ | begin | ||
+ | if (elemsInd mod elemsInLine) <> 0 then | ||
+ | write(curElem.data:PRINT_FIELD_WIDTH, delim) | ||
+ | else // вывели требуемое количество элементов в строке | ||
+ | writeln(curElem.data:PRINT_FIELD_WIDTH, delim); | ||
+ | |||
+ | curElem := curElem.next; | ||
+ | elemsInd += 1; | ||
+ | end; | ||
+ | end; | ||
end; | end; | ||
− | { | + | {Выводит содержимое стека в каждой строке} |
− | procedure | + | procedure Stack<DataType>.Println; |
begin | begin | ||
if IsEmpty then | if IsEmpty then | ||
+ | writeln(EMPTY_STACK) | ||
+ | else | ||
begin | begin | ||
− | + | var curElem := fTop; | |
− | + | while curElem <> nil do | |
− | + | begin | |
− | + | writeln(curElem.data:PRINT_FIELD_WIDTH); | |
− | + | curElem := curElem.next;; | |
− | + | end; | |
− | |||
− | |||
end; | end; | ||
end; | end; | ||
+ | // ----------------------------------------------QUEUE--------------------------------------------- | ||
− | + | // ---------------------------- Стандартные методы --------------------------- | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{Конструктор} | {Конструктор} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
constructor Queue<DataType>.Create; | constructor Queue<DataType>.Create; | ||
begin | begin | ||
Строка 635: | Строка 274: | ||
{Добавляет элемент x в хвост очереди} | {Добавляет элемент x в хвост очереди} | ||
− | procedure Queue<DataType>.Enqueue(x: DataType); | + | procedure Queue<DataType>.Enqueue(x : DataType); |
begin | begin | ||
if IsEmpty then | if IsEmpty then | ||
Строка 645: | Строка 284: | ||
begin | begin | ||
tail.next := new SingleNode<DataType>(x, nil); | tail.next := new SingleNode<DataType>(x, nil); | ||
− | + | tail := tail.next; // элемент убирается из хвоста очереди | |
− | + | // (т.е. хвостом становится следующий элемент) | |
end; | end; | ||
end; | end; | ||
− | |||
{Возвращает элемент типа DataType, убирая его из головы очереди} | {Возвращает элемент типа DataType, убирая его из головы очереди} | ||
− | function Queue<DataType>.Dequeue: DataType; | + | function Queue<DataType>.Dequeue : DataType; |
begin | begin | ||
Assert(not IsEmpty); | Assert(not IsEmpty); | ||
result := head.data; | result := head.data; | ||
− | + | head := head.next; // элемент убирается из головы очереди | |
− | + | // (т.е. головой становится следующий элемент) | |
if head = nil then | if head = nil then | ||
tail := nil; | tail := nil; | ||
end; | end; | ||
− | |||
{Возвращает истину, если очередь пуста} | {Возвращает истину, если очередь пуста} | ||
− | function Queue<DataType>.IsEmpty: boolean; | + | function Queue<DataType>.IsEmpty : boolean; |
begin | begin | ||
result := (head = nil); | result := (head = nil); | ||
Assert(tail = nil); | Assert(tail = nil); | ||
end; | end; | ||
− | |||
end. | end. | ||
</source> | </source> |
Версия 19:56, 16 апреля 2009
Содержание
Вспомогательные модули
Nodes
/// Модуль содержит шаблоны классов
/// SingleNode — узла с одним полем связи
/// DoubleNode — узла с двумя полями связи
unit Nodes;
interface
type
//-------------------------------------------SINGLE_NODE-------------------------------------------
/// Узел с одним полем связи
SingleNode<DataType> = class
/// Значение узла
data : DataType;
/// Ссылка на следующий элемент
next : SingleNode<DataType>;
/// <summary>
/// Конструктор
/// </summary>
/// <param name="pData">Значение узла</param>
/// <param name="pNext">Ссылка на следующий элемент</param>
constructor Create(pData : DataType; pNext : SingleNode<DataType>);
end;
// -------------------------------------------DOUBLE_NODE------------------------------------------
/// Узел с двумя полями связи
DoubleNode<DataType> = class
/// Значение узла
data : DataType;
/// Ссылка на следующий элемент
next : DoubleNode<DataType>;
/// Ссылка на предыдущий элемент
prev : DoubleNode<DataType>;
/// <summary>
/// Конструктор
/// </summary>
/// <param name="pData">Значение узла</param>
/// <param name="pNext">Ссылка на следующий элемент</param>
/// <param name="pPrev">Ссылка на предыдущий элемент</param>
constructor Create(pData : DataType; pPrev, pNext : DoubleNode<DataType>);
end;
implementation
//-------------------------------------------SINGLE_NODE-------------------------------------------
{Конструктор
pData — значение узла
pNext — cсылка на следующий элемент}
constructor SingleNode<DataType>.Create(pData : DataType; pNext : SingleNode<DataType>);
begin
data := pData;
next := pNext;
end;
// -------------------------------------------DOUBLE_NODE------------------------------------------
{Конструктор
pData — значение узла
pNext — cсылка на следующий элемент
pPrev — ссылка на предыдущий элемент}
constructor DoubleNode<DataType>.Create(pData : DataType; pPrev, pNext : DoubleNode<DataType>);
begin
data := pData;
next := pNext;
next := pNext;
end;
end.
Collections
/// Модуль содержит шаблоны классов
/// Stack — стек
/// Queue — очередь
unit Collections;
// ===================================================================== INTERFACE =====================================================================
interface
uses Nodes; // для использования типа SingleNode<DataType> —
// узла с одним полем связи
const
/// Ширина поля вывода
PRINT_FIELD_WIDTH = 5;
/// Разделитель при выводе элементов
DELIMETR = ' ';
/// Количество элементов, выводимых в одной строке при выводе
ELEMS_IN_LINE = 5;
// ----------------------------------------------STACK---------------------------------------------
const
/// Сообщение о пустоте стека
EMPTY_STACK = 'Стек пуст';
type
/// Шаблон класса Stack [Стек]
Stack<DataType> = class
private
/// Вершина стека
fTop : SingleNode<DataType> := nil; // field Top
public
// ---------------------------- Стандартные методы ---------------------------
/// Стандартный конструктор
constructor Create;
/// Конструктор.
/// Создает стек, заполненный элементами, переданными в качестве параметров
constructor Create(params datas : array of DataType);
{/// <summary>
/// Конструктор.
/// Создает стек, заполненный случайными данными
/// </summary>
/// <param name="count">Количество элементов</param>
/// <param name="GenerateRandom">Функция, генерирующая случайный объект</param>
constructor Create(count : integer; GenerateRandom : function : DataType);}
/// Кладет элемент x на вершину стека
procedure Push(x : DataType);
/// Возвращает элемент типа DataType, снимая его с вершины стека
function Pop : DataType;
/// Возвращает значение элемента на вершине стека
function Top : DataType;
/// Возвращает истину, если стек пуст
function IsEmpty : boolean;
// ----------------------------- Вывод содержимого ---------------------------
/// <summary>
/// Выводит подряд содержимое стека
/// </summary>
/// <param name="delim">Разделитель между элементами в строке</param>
/// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
procedure Print(delim : string := DELIMETR; elemsInLine : integer := ELEMS_IN_LINE);
/// Выводит содержимое стека в каждой строке
procedure Println;
end;
// ----------------------------------------------QUEUE---------------------------------------------
type
/// Шаблон класса Queue [Очередь]
Queue<DataType> = class
private
/// Голова очереди
head : SingleNode<DataType>;
/// Хвост очереди
tail : SingleNode<DataType>;
public
// ---------------------------- Стандартные методы ---------------------------
/// Стандартный конструктор
constructor Create;
/// Добавляет элемент x в хвост очереди
procedure Enqueue(x : DataType);
/// Возвращает элемент типа DataType, убирая его из головы очереди
function Dequeue : DataType;
/// Возвращает истину, если очередь пуста
function IsEmpty : boolean;
end;
// ================================================================= IMPLEMENTATION ===================================================================
implementation
// ----------------------------------------------STACK---------------------------------------------
// ---------------------------- Стандартные методы ---------------------------
{Стандартный конструктор}
constructor Stack<DataType>.Create;
begin
fTop := nil;
end;
{Конструктор.
Создает стек, заполненный элементами, переданными в качестве параметров}
constructor Stack<DataType>.Create(params datas : array of DataType);
begin
fTop := nil;
for var i := 0 to datas.Length - 1 do
Push(datas[i]);
end;
{Конструктор.
Создает стек, заполненный случайными данными
count — количество элементов
GenerateRandom — функция, генерирующая случайный объект}
{constructor Stack<DataType>.Create(count : integer; GenerateRandom : function : DataType);
begin
fTop := nil;
for var i := 1 to count do
Push(GenerateRandom);
end;}
{Кладет элемент x на вершину стека}
procedure Stack<DataType>.Push(x : DataType);
begin
fTop := new SingleNode<DataType>(x, fTop);
end;
{Возвращает элемент типа DataType, снимая его с вершины стека}
function Stack<DataType>.Pop : DataType;
begin
Assert(not IsEmpty);
result := fTop.data;
fTop := fTop.next; // элемент снимается с вершины стека
// (т.е. вершиной становится следующий элемент)
end;
{Возвращает значение элемента на вершине стека}
function Stack<DataType>.Top : DataType;
begin
Assert(not IsEmpty);
result := fTop.data;
end;
{Возвращает истину, если стек пуст}
function Stack<DataType>.IsEmpty : boolean;
begin
result := (fTop = nil);
end;
// ----------------------------- Вывод содержимого ---------------------------
{Выводит подряд содержимое стека
delim — разделитель между элементами в строке
elemsInLine — количество элементов, выводимых в одной строке}
procedure Stack<DataType>.Print(delim : string; elemsInLine : integer);
begin
if IsEmpty then
writeln(EMPTY_STACK)
else
begin
var elemsInd := 1; // индекс элемента стека
// нужен для вывода по строкам
var curElem := fTop;
while curElem <> nil do
begin
if (elemsInd mod elemsInLine) <> 0 then
write(curElem.data:PRINT_FIELD_WIDTH, delim)
else // вывели требуемое количество элементов в строке
writeln(curElem.data:PRINT_FIELD_WIDTH, delim);
curElem := curElem.next;
elemsInd += 1;
end;
end;
end;
{Выводит содержимое стека в каждой строке}
procedure Stack<DataType>.Println;
begin
if IsEmpty then
writeln(EMPTY_STACK)
else
begin
var curElem := fTop;
while curElem <> nil do
begin
writeln(curElem.data:PRINT_FIELD_WIDTH);
curElem := curElem.next;;
end;
end;
end;
// ----------------------------------------------QUEUE---------------------------------------------
// ---------------------------- Стандартные методы ---------------------------
{Конструктор}
constructor Queue<DataType>.Create;
begin
head := nil;
tail := nil;
end;
{Добавляет элемент x в хвост очереди}
procedure Queue<DataType>.Enqueue(x : DataType);
begin
if IsEmpty then
begin
head := new SingleNode<DataType>(x, nil);
tail := head;
end
else // if not IsEmpty
begin
tail.next := new SingleNode<DataType>(x, nil);
tail := tail.next; // элемент убирается из хвоста очереди
// (т.е. хвостом становится следующий элемент)
end;
end;
{Возвращает элемент типа DataType, убирая его из головы очереди}
function Queue<DataType>.Dequeue : DataType;
begin
Assert(not IsEmpty);
result := head.data;
head := head.next; // элемент убирается из головы очереди
// (т.е. головой становится следующий элемент)
if head = nil then
tail := nil;
end;
{Возвращает истину, если очередь пуста}
function Queue<DataType>.IsEmpty : boolean;
begin
result := (head = nil);
Assert(tail = nil);
end;
end.