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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
 
(не показано 5 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
[[Категория:Collections]]
 
== Интерфейс ==
 
== Интерфейс ==
 
<source lang="Delphi">
 
<source lang="Delphi">
type Stack<T> = class
+
type Stack<DataType> = class
 
   /// Создает пустой стек
 
   /// Создает пустой стек
 
   constructor Create;
 
   constructor Create;
Строка 24: Строка 25:
 
== Реализация ==
 
== Реализация ==
 
<source lang="Delphi">
 
<source lang="Delphi">
 +
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;
 
</source>
 
</source>
  
 
== Примеры использования ==
 
== Примеры использования ==
 +
<source lang="Delphi">
 +
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.
 +
</source>
  
 
== См. также ==
 
== См. также ==
[[Unit Collections | Collections]]:
+
[[Unit Collections | Collections]] (полный текст модуля):
  
*[[Unit Collections: Queue | Queue]]
+
* [[Unit Collections: Queue | Queue]]
*[[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 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 (полный текст модуля):