> 4.7 Дайте определение класса Item и перегрузите операции == и << так, чтобы их можно было использовать в программе обработки игральных карт.

4.8 Перепишите программу 3.1 так, чтобы в ней использовался класс обобщенных объектов Item. Ваша программа должна работать для любого типа объектов класса Item, которые могут выводиться при помощи операции , генерироваться случайным образом с использованием статической функции-члена rand() и для которых определены операции + и /.

4.2 АТД для стека магазинного типа

Самый важный тип данных из тех, в которых определены операции вставить и удалить для коллекций объектов, называется стеком магазинного типа

Стек работает отчасти подобно ящику для входящей корреспонденции весьма занятого профессора: работа скапливается стопкой, и каждый раз, когда у профессора появляется возможность просмотреть какую-нибудь работу, он берет ее сверху. Работа студента вполне может застрять на дне стопки на день или два, однако, скорее всего, добросовестный профессор к концу недели управится со всей стопкой и освободит ящик. Далее несложно будет заметить, что работа компьютерных программ организована именно таким образом, и это вполне естественно. Они часто откладывают некоторые задачи и выполняют в это время другие; более того, зачастую им требуется в первую очередь вернуться к той задаче, которая была отложена последней. Таким образом, стеки магазинного типа являются фундаментальной структурой данных для множества алгоритмов.

Определение 4.2 Стек магазинного типа - это ЛТД, который включает две основные операции: вставить, или затолкнуть (push) новый элемент и удалить, или вытолкнуть (pop) элемент, вставленный последним.

Когда мы говорим об АТД стека магазинного типа, мы ссылаемся на описание операций затолкнуть и вытолкнуть, которые должны быть определены достаточно хорошо для того, чтобы клиентская программа могла их использовать, а также на некоторую реализацию этих операций, функционирующую в соответствии с правилом удаления элементов такого стека: последним пришел, первым ушел (last-in, first-out, сокращенно LIFO).

Программа 4.4 Интерфейс абарактного типа данных аека

Используя то же самое общепринятое правило, что и в программе 4.3, мы определяем АТД стека через объявление общедоступных функций. При этом предполагается, что представление стека и любой другой код, зависящий от реализации, являются приватными, чтобы можно было изменять реализации, не изменяя код клиентских программ. Кроме того, в этом интерфейсе применяется шаблон, что позволяет программам-клиентам использовать стеки, содержащие объекты любых классов (см. программы 4.5 и 4.6), а в реализациях использовать ключевое слово Item в качестве обозначения типа объектов стека (см. программы 4.7 и 4.8). Аргумент конструктора STACK задает максимальное количество элементов, которые можно поместить в стек.

template <с1а88 It m> class STACK {

private:

программный код, зависящий от реализации

public: STACK(int); int empty О const; void push(Item item); Item popO ;

На рис. 4.1 показано, как изменяется содержимое стека в процессе выполнения серии операций затолкнуть и вытолкнуть. Каждая операция затолкнуть увеличивает размер стека на 1, а каждая операция вытолкнуть уменьшает размер стека на 1. На рисунке элементы стека перечисляются в порядке их помеше-ния в стек, поэтому ясно, что самый правый элемент списка - это элемент, который находится на верхушке стека и будет извлечен из стека, если следующей операцией будет операция вытолкнуть. В реа;[изации элементы можно организовывать любым требуемым способом, однако при этом у программ-клиентов должна сохранятся иллюзия, что элементы организованны именно таким образом.

Как упоминалось в предыдущем разделе, для того чтобы можно было писать программы, использующие абстракцию стека, сначала необходимо определить интерфейс. С этой целью, как принято, объявляется совокупность общедоступных функций-членов, которые будут использоваться в реализациях класса (см. программу 4.4). Все остальные члены класса делаются приватными (private) и тем самым обеспечивается, что эти функции будут единственной связью между клиентскими программами и реализациями. В главах 1 и 3 мы уже видели достоинства определения абстрактных операций, на которых основаны требуемые вычисления. Сейчас мы рассматриваем механизм, позволяющий записывать программы, в которых применяются эти абстрактные операции. Для реализации такой абстракции, для сокрытия структуры данных и реализации от программы-клиента используется механизм классов. В разделе 4.3 рассматриваются примеры клиентских программ, использующих абстракцию стека, а в разделе 4.4 - соответствующие реализации.

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

РИСУНОК 4.1 ПРИМЕР СТЕКА МАГАЗИННОГО ТИПА (ОЧЕРЕДИ, ФУНКЦИОНИРУЮЩЕЙ ПО ПРИНЦИПУ LIFO)

Этот список отображает результаты выполнения последовательности операций. Левый столбец представляет собой выполняемые операции (сверху вниз), где буква означает операцию затолкнуть, а звездочка - операцию вытолкнуть. В каждой строке отображается выполняемая операция, буква, извлекаемая при операции выталкивания, и содержимое стека после операции (от первой занесенной буквы до последней - слева направо).

Объявление STACK<int> save(N)

определяет, что элементы стека save должны быть типа int (и что максимальное количество элементов, которое может вмещать стек, равно N). Программа-клиент может создавать стеки, содержащие объекты типа float или char или любого другого типа (даже типа STACK); для этого необходимо просто изменить параметр шаблона в угловых скобках. Мы можем считать, что в реализации указанный класс замещает класс Item везде, где он встречается.

В абстрактном типе данных назначение интерфейса состоит в том, чтобы служить в качестве соглашения между программой-клиентом и реализацией. Объявления функций обеспечивают соответствие между вызовами в клиентской программе и определениями функций в реализации. Но с другой стороны, интерфейс не содержит никакой информации о том, как должны быть реализованы функции, или хотя бы как они должны функционировать. Как мы можем объяснить клиентской программе, что такое стек? Для простых структур, подобных стеку, можно было бы открыть код, но ясно, что в общем случае такое решение не может являться эффективным. Чаще всего профаммисты прибегают к описаниям на английском языке и помещают их в документацию на программу.

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

Чтобы подчеркнуть, что наша спецификация абстрактного типа данных стек предоставляет достаточно информации для написания осмысленной клиентской профаммы, перед исследованием реализаций рассмотрим в разделе 4.3 две клиентские профаммы, использующие стеки магазинного типа.

Упражнения

> 4.9 В последовательности

EAS*Y*QUE***ST***IO*N***

буква означает операцию затолкнуть, а звездочка - операцию вытолкнуть. Дайте последовательность значений, возвращаемых операциями вытолкнуть.

4.10 Используя те же правила, что и в упражнении 4.9, вставьте звездочки в последовательность EASY таким образом, чтобы последовательность значений, возвращаемых операциями вытолкнуть, была следующей: (i) EASY; (ii) YSAE; (iii) ASYE; (iv) AYES; или в каждом случае докажите, что такая последовательность не возможна.