Collections: Queue — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) (→Реализация) |
Juliet (обсуждение | вклад) |
||
Строка 29: | Строка 29: | ||
// узла с одним полем связи | // узла с одним полем связи | ||
+ | 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 | 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; | ||
</source> | </source> | ||
== Примеры использования == | == Примеры использования == | ||
+ | <source lang="Delphi"> | ||
+ | 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. | ||
+ | </source> | ||
== См. также == | == См. также == |
Версия 19:57, 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.