Collections: Queue

Интерфейс

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 (полный текст модуля):

• Stack
• DynArray
• SimpleSet
• AssocArray
• LinkedList