Collections — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) (→Nodes) |
Juliet (обсуждение | вклад) (→Collections) |
||
Строка 350: | Строка 350: | ||
== Collections == | == Collections == | ||
− | <source lang="Delphi"></source> | + | <xh4> I </xh4> |
+ | <source lang="Delphi"> | ||
+ | /// Модуль содержит шаблоны классов | ||
+ | /// Stack — стек | ||
+ | /// Queue — очередь | ||
+ | unit Collections; | ||
+ | |||
+ | |||
+ | // ========================================================================================= INTERFACE ========================================================================================= \\ | ||
+ | interface | ||
+ | |||
+ | uses Nodes; | ||
+ | |||
+ | type | ||
+ | |||
+ | // --------------------------------------------------------STACK-------------------------------------------------------\\ | ||
+ | /// Шаблон класса Stack [Стек] | ||
+ | Stack<DataType> = class | ||
+ | |||
+ | private | ||
+ | /// Вершина стека | ||
+ | fTop: SingleNode<DataType> := nil; // field Top | ||
+ | |||
+ | public | ||
+ | /// Конструктор | ||
+ | constructor Create; | ||
+ | |||
+ | /// Кладет элемент x на вершину стека | ||
+ | procedure Push(x: DataType); | ||
+ | |||
+ | /// Возвращает элемент типа DataType, снимая его с вершины стека | ||
+ | function Pop: DataType; | ||
+ | /// Возвращает значение элемента на вершине стека | ||
+ | function Top: DataType; | ||
+ | |||
+ | /// Возвращает истину, если стек пуст | ||
+ | function IsEmpty: boolean; | ||
+ | |||
+ | end; | ||
+ | //- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\ | ||
+ | |||
+ | |||
+ | // --------------------------------------------------------QUEUE-------------------------------------------------------\\ | ||
+ | /// Шаблон класса 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; | ||
+ | //- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\ | ||
+ | |||
+ | |||
+ | // ====================================================================================== IMPLEMENTATION ======================================================================================= \\ | ||
+ | implementation | ||
+ | |||
+ | // --------------------------------------------------------STACK-------------------------------------------------------\\ | ||
+ | {Конструктор} | ||
+ | constructor Stack<DataType>.Create; | ||
+ | begin | ||
+ | fTop := nil; | ||
+ | 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; | ||
+ | //- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\ | ||
+ | |||
+ | |||
+ | // --------------------------------------------------------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 of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\ | ||
+ | |||
+ | end. | ||
+ | </source> | ||
+ | |||
+ | <xh4> II </xh4> | ||
+ | <source lang="Delphi"> | ||
+ | /// Модуль содержит шаблоны классов | ||
+ | /// Stack — стек | ||
+ | /// Queue — очередь | ||
+ | unit Collections; | ||
+ | |||
+ | |||
+ | // ========================================================================================= INTERFACE ========================================================================================= \\ | ||
+ | interface | ||
+ | |||
+ | uses Nodes; | ||
+ | |||
+ | type | ||
+ | |||
+ | // --------------------------------------------------------STACK-------------------------------------------------------\\ | ||
+ | /// Шаблон класса Stack [Стек] | ||
+ | Stack<DataType> = class | ||
+ | |||
+ | private | ||
+ | /// Вершина стека | ||
+ | fTop: SingleNode<DataType> := nil; // field Top | ||
+ | |||
+ | public | ||
+ | /// Конструктор | ||
+ | constructor Create; | ||
+ | |||
+ | /// Кладет элемент x на вершину стека | ||
+ | procedure Push(x: DataType); | ||
+ | |||
+ | /// Возвращает элемент типа DataType, снимая его с вершины стека | ||
+ | function Pop: DataType; | ||
+ | /// Возвращает значение элемента на вершине стека | ||
+ | function Top: DataType; | ||
+ | |||
+ | /// Возвращает истину, если стек пуст | ||
+ | function IsEmpty: boolean; | ||
+ | |||
+ | end; | ||
+ | //- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\ | ||
+ | |||
+ | |||
+ | // --------------------------------------------------------QUEUE-------------------------------------------------------\\ | ||
+ | /// Шаблон класса 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; | ||
+ | //- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\ | ||
+ | |||
+ | |||
+ | // ====================================================================================== IMPLEMENTATION ======================================================================================= \\ | ||
+ | implementation | ||
+ | |||
+ | // --------------------------------------------------------STACK-------------------------------------------------------\\ | ||
+ | {Конструктор} | ||
+ | constructor Stack<DataType>.Create; | ||
+ | begin | ||
+ | fTop := nil; | ||
+ | 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; | ||
+ | SetNext(fTop); // элемент снимается с вершины стека | ||
+ | // (т.е. вершиной становится следующий элемент) | ||
+ | end; | ||
+ | |||
+ | {Возвращает значение элемента на вершине стека} | ||
+ | function Stack<DataType>.Top: DataType; | ||
+ | begin | ||
+ | Assert(not IsEmpty); | ||
+ | |||
+ | result := fTop.data; | ||
+ | end; | ||
+ | |||
+ | |||
+ | {Возвращает истину, если стек пуст} | ||
+ | function Stack<DataType>.IsEmpty: boolean; | ||
+ | begin | ||
+ | result := (fTop = nil); | ||
+ | end; | ||
+ | //- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\ | ||
+ | |||
+ | |||
+ | // --------------------------------------------------------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); | ||
+ | SetNext(tail); // элемент убирается из хвоста очереди | ||
+ | // (т.е. хвостом становится следующий элемент) | ||
+ | end; | ||
+ | end; | ||
+ | |||
+ | |||
+ | {Возвращает элемент типа DataType, убирая его из головы очереди} | ||
+ | function Queue<DataType>.Dequeue: DataType; | ||
+ | begin | ||
+ | Assert(not IsEmpty); | ||
+ | result := head.data; | ||
+ | |||
+ | SetNext(head); // элемент убирается из головы очереди | ||
+ | // (т.е. головой становится следующий элемент) | ||
+ | if head = nil then | ||
+ | tail := nil; | ||
+ | end; | ||
+ | |||
+ | |||
+ | {Возвращает истину, если очередь пуста} | ||
+ | function Queue<DataType>.IsEmpty: boolean; | ||
+ | begin | ||
+ | result := (head = nil); | ||
+ | Assert(tail = nil); | ||
+ | end; | ||
+ | //- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\ | ||
+ | |||
+ | end. | ||
+ | </source> |
Версия 14:19, 16 апреля 2009
Вспомогательные модули
Nodes
<xh4> I </xh4>
/// Модуль содержит шаблоны классов
/// 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;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
// -----------------------------------------------------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;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
implementation
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
{Конструктор
pData — значение узла
pNext — cсылка на следующий элемент}
constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>);
begin
data := pData;
next := pNext;
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
// -----------------------------------------------------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 of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
end.
<xh4> II </xh4>
/// Модуль содержит шаблоны классов
/// SingleNode — узла с одним полем связи
/// DoubleNode — узла с двумя полями связи
unit Nodes;
// ========================================================================================= INTERFACE ========================================================================================= \\
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;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
/// Установка узла с одним полем связи sNode на следующий элемент
procedure SetNext<DataType>(var sNode: SingleNode<DataType>);
// -----------------------------------------------------DOUBLE_NODE----------------------------------------------------\\
type
/// Узел с двумя полями связи
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;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
/// Установка узла с двумя полями связи dNode на следующий элемент
procedure SetNext<DataType>(var dNode: DoubleNode<DataType>);
/// Установка узла с двумя полями связи dNode на предыдущий элемент
procedure SetPrev<DataType>(var dNode: DoubleNode<DataType>);
// ====================================================================================== IMPLEMENTATION ======================================================================================= \\
implementation
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
{Конструктор
pData — значение узла
pNext — cсылка на следующий элемент}
constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>);
begin
data := pData;
next := pNext;
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
{Установка узла с одним полем связи sNode на следующий элемент}
procedure SetNext<DataType>(var sNode: SingleNode<DataType>);
begin
Assert(sNode <> nil);
sNode := sNode.next
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 of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
{Установка узла с двумя полями связи dNode на следующий элемент}
procedure SetNext<DataType>(var dNode: DoubleNode<DataType>);
begin
Assert(dNode <> nil);
dNode := dNode.next;
end;
{Установка узла с двумя полями связи dNode на предыдущий элемент}
procedure SetPrev<DataType>(var dNode: DoubleNode<DataType>);
begin
Assert(dNode <> nil);
dNode := dNode.prev;
end;
end.
<xh4> III </xh4>
/// Модуль содержит шаблоны классов
/// SingleNode — узла с одним полем связи
/// DoubleNode — узла с двумя полями связи
unit Nodes;
// ========================================================================================= INTERFACE ========================================================================================= \\
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;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
/// Установка узла с одним полем связи sNode на следующий элемент.
/// Если не удалось, возвращает ложь.
function SetNext<DataType>(var sNode: SingleNode<DataType>): boolean;
// -----------------------------------------------------DOUBLE_NODE----------------------------------------------------\\
type
/// Узел с двумя полями связи
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;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
/// Установка узла с двумя полями связи dNode на следующий элемент.
/// Если не удалось, возвращает ложь.
function SetNext<DataType>(var dNode: DoubleNode<DataType>): boolean;
/// Установка узла с двумя полями связи dNode на предыдущий элемент.
/// Если не удалось, возвращает ложь.
function SetPrev<DataType>(var dNode: DoubleNode<DataType>): boolean;
// ====================================================================================== IMPLEMENTATION ======================================================================================= \\
implementation
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
{Конструктор
pData — значение узла
pNext — cсылка на следующий элемент}
constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>);
begin
data := pData;
next := pNext;
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
{Установка узла с одним полем связи sNode на следующий элемент.
Если не удалось, возвращает ложь.}
function SetNext<DataType>(var sNode: SingleNode<DataType>): boolean;
begin
if sNode = nil then
result := false
else
begin
sNode := sNode.next;
result := true;
end;
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 of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
{Установка узла с двумя полями связи dNode на следующий элемент.
Если не удалось, возвращает ложь.}
function SetNext<DataType>(var dNode: DoubleNode<DataType>): boolean;
begin
if dNode = nil then
result := false
else
begin
dNode := dNode.next;
result := true;
end;
end;
{Установка узла с двумя полями связи dNode на предыдущий элемент.
Если не удалось, возвращает ложь.}
function SetPrev<DataType>(var dNode: DoubleNode<DataType>): boolean;
begin
if dNode = nil then
result := false
else
begin
dNode := dNode.prev;
result := true;
end;
end;
end.
Collections
<xh4> I </xh4>
/// Модуль содержит шаблоны классов
/// Stack — стек
/// Queue — очередь
unit Collections;
// ========================================================================================= INTERFACE ========================================================================================= \\
interface
uses Nodes;
type
// --------------------------------------------------------STACK-------------------------------------------------------\\
/// Шаблон класса Stack [Стек]
Stack<DataType> = class
private
/// Вершина стека
fTop: SingleNode<DataType> := nil; // field Top
public
/// Конструктор
constructor Create;
/// Кладет элемент x на вершину стека
procedure Push(x: DataType);
/// Возвращает элемент типа DataType, снимая его с вершины стека
function Pop: DataType;
/// Возвращает значение элемента на вершине стека
function Top: DataType;
/// Возвращает истину, если стек пуст
function IsEmpty: boolean;
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
// --------------------------------------------------------QUEUE-------------------------------------------------------\\
/// Шаблон класса 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;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
// ====================================================================================== IMPLEMENTATION ======================================================================================= \\
implementation
// --------------------------------------------------------STACK-------------------------------------------------------\\
{Конструктор}
constructor Stack<DataType>.Create;
begin
fTop := nil;
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;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
// --------------------------------------------------------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 of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
end.
<xh4> II </xh4>
/// Модуль содержит шаблоны классов
/// Stack — стек
/// Queue — очередь
unit Collections;
// ========================================================================================= INTERFACE ========================================================================================= \\
interface
uses Nodes;
type
// --------------------------------------------------------STACK-------------------------------------------------------\\
/// Шаблон класса Stack [Стек]
Stack<DataType> = class
private
/// Вершина стека
fTop: SingleNode<DataType> := nil; // field Top
public
/// Конструктор
constructor Create;
/// Кладет элемент x на вершину стека
procedure Push(x: DataType);
/// Возвращает элемент типа DataType, снимая его с вершины стека
function Pop: DataType;
/// Возвращает значение элемента на вершине стека
function Top: DataType;
/// Возвращает истину, если стек пуст
function IsEmpty: boolean;
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
// --------------------------------------------------------QUEUE-------------------------------------------------------\\
/// Шаблон класса 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;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
// ====================================================================================== IMPLEMENTATION ======================================================================================= \\
implementation
// --------------------------------------------------------STACK-------------------------------------------------------\\
{Конструктор}
constructor Stack<DataType>.Create;
begin
fTop := nil;
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;
SetNext(fTop); // элемент снимается с вершины стека
// (т.е. вершиной становится следующий элемент)
end;
{Возвращает значение элемента на вершине стека}
function Stack<DataType>.Top: DataType;
begin
Assert(not IsEmpty);
result := fTop.data;
end;
{Возвращает истину, если стек пуст}
function Stack<DataType>.IsEmpty: boolean;
begin
result := (fTop = nil);
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
// --------------------------------------------------------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);
SetNext(tail); // элемент убирается из хвоста очереди
// (т.е. хвостом становится следующий элемент)
end;
end;
{Возвращает элемент типа DataType, убирая его из головы очереди}
function Queue<DataType>.Dequeue: DataType;
begin
Assert(not IsEmpty);
result := head.data;
SetNext(head); // элемент убирается из головы очереди
// (т.е. головой становится следующий элемент)
if head = nil then
tail := nil;
end;
{Возвращает истину, если очередь пуста}
function Queue<DataType>.IsEmpty: boolean;
begin
result := (head = nil);
Assert(tail = nil);
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
end.