Collections: Stack

Интерфейс

type Stack<DataType> = class
  /// Создает пустой стек
  constructor Create;
 
  /// Кладет элемент x на вершину стека
  procedure Push(x: DataType);

  /// Возвращает значение элемента на вершине, снимая его со стека
  function Pop: DataType;

  /// Возвращает значение элемента на вершине стека, не снимая его
  function Top: DataType;
 
  /// Возвращает истину, если стек пуст
  function IsEmpty: boolean; 
    
  /// Выводит содержимое стека на консоль
  procedure Println();
end;

Реализация

interface
 
uses Nodes;   // для использования типа SingleNode<DataType> — 
              // узла с одним полем связи

type
  /// Шаблон класса Stack [Стек]
  Stack<DataType> = class
  private 
    /// Вершина стека
    fTop: SingleNode<DataType> := nil; 
 
  public 
    // ---------------------------- Стандартные методы ---------------------------
    /// Создает пустой стек
    constructor Create;
 
    /// <summary>
    /// Кладет элемент на вершину стека
    /// </summary>
    /// <param name="x">Новый элемент</param>
    procedure Push(x: DataType);
    /// Возвращает значение элемента на вершине, снимая его со стека
    function Pop: DataType;
    /// Возвращает значение элемента на вершине стека, не снимая его
    function Top: DataType;
 
    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean; 

    // ---------------------------------- Вывод ----------------------------------
    /// Выводит содержимое стека на консоль
    procedure Println();
  end;

implementation

// ---------------------------- Стандартные методы ---------------------------
{Создает пустой стек}
constructor Stack<DataType>.Create;
begin
  fTop := nil;
end;
 
{Кладет элемент x на вершину стека} 
procedure Stack<DataType>.Push(x: DataType);
begin
  fTop := new SingleNode<DataType>(x, fTop);
end;
 
{Возвращает значение элемента на вершине, снимая его со стека}
function Stack<DataType>.Pop: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка снятия элемента с пустого стека!');
 
  result := fTop.data;
  fTop := fTop.next;  // элемент снимается с вершины стека
                      // (т.е. вершиной становится следующий элемент)
end;
 
{Возвращает значение элемента на вершине стека, не снимая его}
function Stack<DataType>.Top: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка получения элемента с пустого стека!');
 
  result := fTop.data;
end;
 
{Возвращает истину, если стек пуст}
function Stack<DataType>.IsEmpty: boolean;
begin
  result := (fTop = nil);
end;
 
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое стека на консоль}
procedure Stack<DataType>.Println();
begin
  if not IsEmpty then
  begin
    var curElem := fTop;
 
    while curElem <> nil do
    begin
      write(curElem.data, ' ');
      curElem := curElem.next;
    end;
  end;
  writeln();
end;

Примеры использования

uses Collections;

begin
  // Создание нового объекта стека
  var s := new Stack<integer>;
  
  // Проверка стека на пустоту
  writeln('Стек пуст: ', s.IsEmpty);
  writeln();
  
  // Добавление нового элемента на вершину стеку
  s.Push(5);
  writeln('Стек пуст: ', s.IsEmpty);
  s.Push(7);
  // Вывод элемента на вершине стека
  writeln('Вершина стека = ', s.Top);
  writeln();
  
  s.Push(-11);
  // Вывод элемента на вершине стека и снятие его со стека
  writeln('Вершина стека = ', s.Pop);
  writeln('Вершина стека после снятия предыдущей = ', s.Top);
  writeln();
  
  s.Push(105); s.Push(-69);
  writeln('Содержимое всего стека:');
  s.Println;
  writeln();
  
  // Снятие всех элементов со стека
  while not s.IsEmpty do
    write(s.Pop, ' ');
  writeln(NewLine);
  
  // Обработка исключения при попытке чтения элемента 
  // на вершине пустого стека
  try
    s.Top;
  except
    on e: Exception do
      writeln(e);
  end;
end.

См. также

Collections:

• Queue
• DynArray
• SimpleSet
• AssocArray