Книга: Основы объектно-ориентированного программирования

Класс стек

Класс стек

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

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

Рис. 11.2.  Реализация стека на базе массива

Массив, названный representation, имеет границы 1 и capacity: реализация использует также целочисленный атрибут count, отмечающий вершину стека. Заметьте, после того, как мы откроем для себя наследование, появится возможность писать классы с отложенной реализацией, что позволит покрывать несколько возможных реализаций, а не одну конкретную. Даже для класса c фиксированной реализацией, например, как здесь на базе массива, мы будем иметь возможность строить его как потомка родительского класса Array. В данный момент никакие методы наследования применяться не будут.

Вот он класс. Остается напомнить, что для массива a операция, присваивающая значение x его i-му элементу, записывается так: a.put(x,i). Получить i-й элемент можно так: a.item(i) или a @ i. Если, как здесь, границы заданы, то i во всех случаях лежит между этими границами: 1<= i <= capacity.

indexing
description: "Стеки: Структуры с политикой доступа Last-In, First-Out %
% Последний пришел - Первый ушел, и с фиксированной емкостью"
class STACK2 [G] creation
make
feature - Initialization (Инициализация)
make (n: INTEGER) is
-- Создать стек, содержащий максимум n элементов
require
positive_capacity: n >= 0
do
capacity := n
create representationlmake (1, capacity)
ensure
capacity_set: capacity = n
array_allocated: representation /= Void
stack_empty: empty
end
feature - Access (Доступ)
capacity: INTEGER
-- Максимальное число элементов стека
count: INTEGER
-- Число элементов стека
item: G is
-- Элемент на вершине стека
require
not_empty: not empty -- i.e. count > 0
do
Result := representation @ count
end
feature -- Status report (Отчет о статусе)
empty: BOOLEAN is
-- Пуст ли стек?
do
Result := (count = 0)
ensure
empty_definition: Result = (count = 0)
end
full: BOOLEAN is
-- Заполнен ли стек?
do
Result := (count = capacity)
ensure
full_definition: Result = (count = capacity)
end
feature -- Element change (Изменение элементов)
put (x: G) is
-- Добавить элемент x на вершину
require
not_full: not full -- т.е. count < capacity в этом представлении
do
count := count + 1
representation.put (count, x)
ensure
not_empty: not empty
added_to_top: item = x
one_more_item: count = old count + 1
in_top_array_entry: representation @ count = x
end
remove is
-- удалить элемент вершины стека
require
not_empty: not empty -- i.e. count > 0
do
count := count - 1
ensure
not_full: not full
one_fewer: count = old count - 1
end
feature {NONE} -- Implementation (Реализация)
representation: ARRAY [G]
-- Массив, используемый для хранения элементов стека
invariant
... Будет добавлен позднее ...
end

Текст класса иллюстрирует простоту работы с утверждениями. Это полный текст, за исключением предложений invariant, задающих инварианты класса, которые будут добавлены позднее в этой лекции. Давайте исследуем различные свойства класса.

Это первый законченный класс этой лекции, не слишком далеко отличающийся от того, что можно найти в профессиональных библиотеках повторно используемых ОО-компонентов, таких как Базовые библиотеки. Одно замечание о структуре класса. Поскольку класс имеет более двух-трех компонентов, возникает необходимость сгруппировать его компоненты подходящим образом. Нотация позволяет реализовать такую возможность введением множества предложений feature. Это свойство группировки компонентов, введенное в предыдущей лекции, использовалось там, как способ задания различного статуса экспорта компонентов. И здесь в последней части класса, помеченной Implementation, это свойство используется для указания защищенности компонента representation. Но преимущества группирования можно использовать и при неизменном статусе экспорта. Его цель - сделать класс простым при чтении и легче управляемым, группируя компоненты по категориям. После каждого ключевого слова feature появляется комментарий, называемый комментарий к предложению Feature (Feature Clause Comment). Он позволяет дать содержательное описание данной категории - роль компонентов, включенных в этот раздел. Категории, используемые в примере, те же, что и при описании класса STACK1 с добавлением раздела Initialization с процедурой создания (конструктором).

Стандартные категории feature и связанные с ними комментарии к предложениям Feature являются частью общих правил организации повторно используемых библиотек классов.

Оглавление книги