Использование операций

Использование операций

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

Обычно для стеков рассматриваются следующие операции:

[x]. Команда вталкивания некоторого элемента на вершину стека. Назовем эту операцию put.

[x]. Команда удаления верхнего элемента стека. Назовем ее remove.

[x]. Запрос элемента, находящегося на вершине стека (если стек не пуст). Назовем его item.

[x]. Запрос на проверку пустоты стека. (Он позволит клиентам заранее проверить возможность операций remove и item.)

Кроме того, нам понадобится операция-конструктор для создания пустого стека. Назовем ее make.

Две вещи заслуживают более подробных объяснений далее в этой лекции. Во-первых, могут показаться необычными имена операций, Давайте пока считать, что put означает push, remove означает pop, а item означает top. Во-вторых, операции разбиты на три категории: конструкторы, создающие объекты, запросы, возвращающие информацию об объектах, и команды, которые могут изменять объекты. Эта классификация также требует дополнительных объяснений.

При традиционном взгляде на структуры данных мы рассматривали бы понятие стека, заданное с помощью некоторого объявления данных, соответствующего одному из вышеуказанных представлений, например для представления МАССИВ_ВВЕРХ. В стиле Паскаля это выглядит как

count: INTEGER

representation: array [1 .. capacity] of STACK_ELEMENT_TYPE

где константа capacity - это максимальное число элементов в стеке. Тогда put, remove, item, empty и make будут подпрограммами, которые работают на структурах, определенных этим объявлением объектов.

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