Основы программирования — второй семестр 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 Peek: integer;
  function IsEmpty: boolean;
end;

Воспользуемся им в клиентской программе

Задача. Вычисление постфиксного выражения. Пусть в строке a хранится выражение в обратной польской бесскобочной нотации, например:

a='598+46**7+*' 

Каждый символ представляет собой или число из одной цифры или знак операции. Требуется найти значение выражения.

Алгоритм. Если считано число, то поместим его на стек. Если считан знак операции, то применим данную операцию к двум последним операндам, лежащим на стеке, и запишем на стек вместо них полученное значение. По окончании работы алгоритма стек должен содержать единственное значение - ответ.

Для указанной строчки алгоритм выполнит со стеком следующие операции:

5 9 8 
+ 
5 17
5 17 4 6 
* 
5 17 24
* 
5 408
5 408 7 
+ 
5 415 
*
2075

Пусть класс Стек определен в модуле Collections. Код клиентской программы:

uses Collections;
var 
  a: string;
  s: Stack := new Stack;
begin
  read(a);
  for var i:=1 to Length(a) do
    case a[i] of
      '0'..'9': s.Push(StrToInt(a[i]));
      '+': s.Push(s.Pop+s.Pop);
      '*': s.Push(s.Pop*s.Pop);
    end;
  writeln(s.Pop);
  Assert(s.IsEmpty);
end.

Заметим, что клиентская программа ничего не знает, как устроен стек внутри - она пользуется стеком лишь как абстрактным типом данных