Collections: Stack — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) |
Juliet (обсуждение | вклад) |
||
(не показано 5 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
+ | [[Категория:Collections]] | ||
== Интерфейс == | == Интерфейс == | ||
<source lang="Delphi"> | <source lang="Delphi"> | ||
− | type Stack< | + | 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 (полный текст модуля):