Абстракция стека

В качестве простого примера, который демонстрирует использование пакета для реализации абстрактного типа данных, рассмотрим стек.

Следует заметить, что клинтам этого пакета абсолютно безразлично каким образом выполнена внутренняя реализация стека, то есть клиенты не нуждаются в информации о том, что стек реализован с помошью массива или связанного списка.

Шаблоном подобной абстракции может служить следующее:

package Stacks is

Max : constant := 10;

subtype Count is Integer range 0..Max; subtype Index is range 1..Max;

type List is array(Index) of Integer;

type Stack is

record

Values : List; Top : Count; end record;

Overflow : exception; Underflow : exception;

procedure Push(Item : in out Stack; Value : in Integer); procedure Pop(Item : in out Stack; Value : out Integer);

function Full(Item : Stack) return Boolean; function Empty(Item : Stack) return Boolean;

-- возвращает пустой проинициализированный стек function Init return Stack;

end Stacks;

Однако, в данном случае детали реализации достаточно очевидны, то есть кроме того, что клиенту пакета доступно то, что пакет предоставляет в качестве сервиса, клиенту пакета также доступно и то, как этот сервис реализован.

Такую ситуацию можно достаточно просто изменить переместив все, в чем клиент не будет нуждаться, в приватную секцию спецификации пакета:

package Stacks is

type Stack is private; -- неполное описание типа Stack. -- это делает информацию о деталях реализации недоступной.

Overflow : exception; Underflow : exception;

procedure Push(Item : in out Stack; Value : in Integer); procedure Pop(Item : in out Stack; Value : out Integer);

function Full(Item : Stack) return Boolean; function Empty(Item : Stack) return Boolean;

-- возвращает пустой проинициализированный стек function Init return Stack;

private

-- полное описание типа, вместе с другими приватными деталями. Max : constant := 10; subtype Count is Integer range 0..Max; subtype Index is range 1..Max;

type List is array(Index) of Integer;

type Stack is record

Values : List; Top : Count; end record; end Stacks;

<

Следует заметить, что хотя программист использующий такую абстракцию, имеет возможность увидеть все детали реализации (при наличии исходных текстов кода), он не может написать свою собственную программу, которая будет использовать эту информацию.

Также очевидно, что такое разделение вынуждает лучше понять, что для абстракции важно, а что нет.

В качестве альтернативы, можно изменить приватную секцию в соответствии с реализацией стека на связанном списке:

package Stacks is

type Stack is private; -- неполное описание типа Stack. -- это делает информацию о деталях реализации недоступной.

Overflow : exception; Underflow : exception;

procedure Push(Item : in out Stack; Value : in Integer); procedure Pop(Item : in out Stack; Value : out Integer);

function Full(Item : Stack) return Boolean; function Empty(Item : Stack) return Boolean;

-- возвращает пустой проинициализированный стек function Init return Stack;

private

type Stack;

type Ptr is access Stack;

type Stack is

record

Value : Integer; Next : Ptr; end record; end Stacks;

Программа-клиент может использовать оба варианта пакета следующим образом:

with Stacks; use Stacks;

procedure Demo is

A : Stack := Init; B : Stack := Init; Temp : Integer;

begin

for I in 1..10 loop

Push(A, I); end loop;

while not Empty(A) loop

Pop(A, Temp); Push(B, Temp); end loop; end Demo;

Примечательно, что оба варианта реализации стека достаточно отличаются один от другого.

Таким образом, показанные выше примеры наглядно демонстрируют использование идеи возможности подстановки различной реализации, или, более точно, использование программой-клиентом только того, что предоставляет публичный интерфейс.

Напомним, что этот принцип очень важен при построении надежных систем.

Рассмотрим еще один пример использования рассмотренной абстракции стека:

with Stacks; use Stacks;

procedure Not_Quite_Right is

A, B : Stack

begin

Push(A, 1); Push(A, 2);

B := A; end Not_Quite_Right;

Не трудно заметить, что при копировании реализация стека с использованием массива будет работать корректно, а реализация стека с использованием связанного списка скопирует только указатель на "голову" списка, после чего A и B будут указывать на один и тот же связанный список.

Действительно, поскольку внимание текущего обсуждения больше посвящено теме абстракции данных, показанная выше реализация стека на связанном списке максимально упрощена.

Для того чтобы избавиться от подобных "сюрпризов" в практической реализации стека на связанном списке необходимо использовать средства, которые предоставляют контролируемые типы Ады.

Содержание раздела