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



Класс стек


Поставляемый с утверждениями класс 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 -- т.е.


Содержание  Назад  Вперед