Collections: Queue — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) (→См. также) |
Juliet (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
+ | [[Категория:Unit Collections]] | ||
== Интерфейс == | == Интерфейс == | ||
<source lang="Delphi"> | <source lang="Delphi"> |
Версия 20:09, 30 апреля 2009
Интерфейс
type Queue<DataType> = class
/// Создает пустую очередь
constructor Create;
/// Добавляет элемент x в хвост очереди
procedure Enqueue(x: DataType);
/// Возвращает значение элемента в голове, удаляя его из очереди
function Dequeue: DataType;
/// Возвращает значение элемента в голове очереди, не удаляя его
function Top: DataType;
/// Возвращает истину, если очередь пуста
function IsEmpty: boolean;
/// Выводит содержимое очереди на консоль
procedure Println();
end;
Реализация
interface
uses Nodes; // для использования типа SingleNode<DataType> —
// узла с одним полем связи
type
/// Шаблон класса Queue [Очередь]
Queue<DataType> = class
private
/// Голова очереди
head: SingleNode<DataType>;
/// Хвост очереди
tail: SingleNode<DataType>;
public
// ---------------------------- Стандартные методы ---------------------------
/// Создает пустую очередь
constructor Create;
/// <summary>
/// Добавляет элемент в хвост очереди
/// </summary>
/// <param name="x">Добавляемый элемент</param>
procedure Enqueue(x: DataType);
/// Возвращает значение элемента в голове, удаляя его из очереди
function Dequeue: DataType;
/// Возвращает значение элемента в голове очереди, не удаляя его
function Top: DataType;
/// Возвращает истину, если очередь пуста
function IsEmpty: boolean;
// ---------------------------------- Вывод ----------------------------------
/// Выводит содержимое очереди на консоль
procedure Println();
end;
implementation
// ---------------------------- Стандартные методы ---------------------------
{Создает пустую очередь}
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
begin
tail.next := new SingleNode<DataType>(x, nil);
tail := tail.next; // элемент удаляется из хвоста очереди
// (т.е. хвостом становится следующий элемент)
end;
end;
{Возвращает значение элемента в голове, удаляя его из очереди}
function Queue<DataType>.Dequeue: DataType;
begin
if IsEmpty then
raise new Exception('Попытка удаления элемента из пустой очереди!');
result := head.data;
head := head.next; // элемент удаляется из головы очереди
// (т.е. головой становится следующий элемент)
if head = nil then
tail := nil;
end;
{Возвращает значение элемента в голове очереди, не удаляя его}
function Queue<DataType>.Top: DataType;
begin
if IsEmpty then
raise new Exception('Попытка получения элемента из пустой очереди!');
result := head.data;
end;
{Возвращает истину, если очередь пуста}
function Queue<DataType>.IsEmpty: boolean;
begin
result := (head = nil);
if result then
Assert(tail = nil);
end;
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое очереди на консоль}
procedure Queue<DataType>.Println();
begin
if not IsEmpty then
begin
var curElem := head;
while curElem <> nil do
begin
write(curElem.data, ' ');
curElem := curElem.next;
end;
end;
writeln();
end;
Примеры использования
uses Collections;
begin
// Создание нового объекта очереди
var q := new Queue<integer>;
// Проверка очереди на пустоту
writeln('Очередь пуста: ', q.IsEmpty);
writeln();
// Добавление элемента в хвост очереди
q.Enqueue(-8);
writeln('Очередь пуста: ', q.IsEmpty);
q.Enqueue(43);
// Вывод головы очереди
writeln('Голова очереди = ', q.Top);
writeln();
q.Enqueue(-15);
// Вывод головы и удаление её из очереди
writeln('Голова очереди = ', q.Dequeue);
writeln('Голова очереди после убирания предыдущей = ', q.Top);
writeln();
q.Enqueue(11); q.Enqueue(136);
// Вывод содержимого очереди
writeln('Содержимое всей очереди:');
q.Println;
writeln();
// Удаление всех элементов из очереди
while not q.IsEmpty do
write(q.Dequeue, ' ');
writeln(NewLine);
// Обработка исключения при попытке чтения элемента
// в голове пустой очереди
try
q.Top;
except
on e: Exception do
writeln(e);
end;
end.
См. также
Collections (полный текст модуля):