Collections: Queue — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Реализация)
 
(не показано 5 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
[[Категория:Collections]]
 
== Интерфейс ==
 
== Интерфейс ==
 
<source lang="Delphi">
 
<source lang="Delphi">
Строка 29: Строка 30:
 
               // узла с одним полем связи
 
               // узла с одним полем связи
  
 +
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>
  
 
== См. также ==
 
== См. также ==
[[Unit Collections | Collections]]:
+
[[Unit Collections | Collections]] (полный текст модуля):
  
*[[Unit Collections: Stack | Stack]]
+
* [[Unit Collections: Stack | Stack]]
*[[Unit Collections: DynArray | DynArray]]
+
* [[Unit Collections: DynArray | DynArray]]
*[[Unit Collections: SimpleSet | SimpleSet]]
+
* [[Unit Collections: SimpleSet | SimpleSet]]
*[[Unit Collections: AssocArray | AssocArray]]
+
* [[Unit Collections: AssocArray | AssocArray]]
 +
* [[Unit Collections: LinkedList | LinkedList]]

Текущая версия на 11:52, 9 мая 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 (полный текст модуля):