41385d94

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


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

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

  • Команда вталкивания некоторого элемента на вершину стека. Назовем эту операцию put.
  • Команда удаления верхнего элемента стека. Назовем ее remove.
  • Запрос элемента, находящегося на вершине стека (если стек не пуст). Назовем его item.
  • Запрос на проверку пустоты стека. (Он позволит клиентам заранее проверить возможность операций 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 будут подпрограммами, которые работают на структурах, определенных этим объявлением объектов.

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



    Содержание раздела