Основы программирования — второй семестр 08-09; Михалкович С.С.; V часть

Что известно о классах к настоящему моменту:

1. Класс - тип данных
2. Класс, как и запись, содержит поля и методы
3. Переменная типа класс и переменная типа запись по-разному хранятся в памяти (ссылочная и размерная организация данных)
4. Для создания объекта класса и связывания его с переменной класса вызывается специальная функция-метод, называемая конструктором
5. Можно создавать шаблоны классов, параметризованные одним или несколькими типами

Абстрактные типы данных

Класс является реализацией более общей концепции абстрактного типа данных (АТД).

До сих пор мы сталкивались с конкретными типами данных, простыми или составными (массивы, записи, списки). Каждый тип данных характеризуется:

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

Абстрактный тип данных - это тип данных, доступ к которым осуществляется только через некоторый набор действий (операций, подпрограмм). Этот набор действий называется интерфейсом абстрактного типа данных. По существу, абстрактный тип данных - это интерфейс, набор операций. То, как эти данные хранятся, АТД не определяет.

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

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

АТД стек

Стек - это набор данных, устроенный по принципу LIFO (Last In First Out) - последним пришел - первым вышел.

Стек следует представлять как стопку предметов, положенных один на другой. В каждый момент можно положить предмет на вершину стека, посмотреть предмет на вершине стека, снять предмет с вершины и проверить, пуст ли стек. Причем, если предмет последним положили на вершину стопки, то он будет снят первым - отсюда и название LIFO.

Хорошим примером стека является колода карт и магазин автомата.

Опишем операции со стеком

1. Положить значение на вершину стека (Push, втолкнуть значение в стек)
2. Вернуть значение на вершине стека (Peek)
3. Взять значение с вершины стека и вернуть его (Pop, вытолкнуть значение из стека)
4. Пуст ли стек (IsEmpty)

Опишем интерфейс стека в виде класса:

type Stack = class

 procedure Push(i: integer);
 function Pop: integer;
 function Top: integer;
 function IsEmpty: boolean;

end;