ления элементов применяется тот же код с одной дополнительной проверкой: перед вставкой элемента выполняется проверка, нет ли в стеке такого элемента. Если есть, операция занесения элемента игнорируется. Это решение не зависит от используемого представления стека - на базе массива, связного списка или чего-нибудь еще. Для реализации принципа удалять старый элемент требуется больший объем работы (см. упр. 4.57).

Суммируя изложенное выше, можно сказать, что один из способов реализации стека без повторяющихся элементов, функционирующего по принципу игнорировать новый элемент , состоит в поддержке двух структур данных. Первая, как и прежде, содержит элементы стека и позволяет отслеживать порядок, в котором были вставлены элементы стека. Вторая структура является массивом, позволяющим отслеживать, какие элементы находятся в стеке; индексами этого массива являются элементы стека. Такое использование массива рассматривается как частный случай реализации таблицы символов, которая обсуждается в разделе 12.2. Когда известно, что элементы представляют собой целые числа в диапазоне от О до М - 1, эту же методику можно применять по отношению к любой обобщенной очереди.

Программа 4.16 Стек индексных элементов, в котором запрещены повторяющиеся элементы

в этой реализации стека магазинного типа предполагается, что класс Item имеет тип int, который возвращает целые числа в диапазоне от О до maxN-1, так что он может поддерживать массив t, где каждому элементу стека соответствует отличное от нуля значение. Этот массив дает возможность функции push быстро проверять, не находится ли уже в стеке ее аргумент, и если так, то не предпринимать никаких действий. В каждом элементе массива t используется только один бит, поэтому при желании можно сэкономить оперативную память, используя вместо целых чисел символы или биты (см. упр. 12.12).

template <class Item> class STACK

private:

Item *8, *t; int N; public:

STACK(int maxN)

s - new Item[maxN] ; t = new Item[maxN] ; for (int i = 0; i <

int empty() const { return N = 0; }

maxN; i++) t[i] = 0;

РИСУНОК 4.11 ОЧЕРЕДЬ FIFO БЕЗ ПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ.

ФУНКЦИОНИРУЮЩАЯ ПО ПРИНЦИПУ УДАЛЯТЬ СТАРЫЙ ЭЛЕМЕНТ

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

void push(Item item) {

if (t[item] == 1) return; s[N++] = item; t[item] = 1;

Item popO { t[s[--N]] = 0; return s[N]; }

Этот частный случай встречается довольно часто. Его наиболее важный пример - когда элементы структуры данных сами являются индексами массива, поэтому такие элементы называются индексными элементами (index items). Обычно имеется набор из М объектов, хранимых в каком-то другом массиве, и как часть более сложного алгоритма, необходимо передавать этот набор объектов через структуру обобщенной очереди. Объекты заносятся в очередь по индексам и обрабатываются при удалении, причем каждый объект должен обрабатываться только один раз. Очередь без повторяющихся элементов, в которой используются индексы массива, позволяет напрямую достичь этой цели.

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

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

Упражнения

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

4.54 Модифицируйте стандартную реализацию стека на базе массива из раздела 4.4 (программа 4.7) таким образом, чтобы в ней были запрещены повторяющиеся элементы по принципу игнорировать новый элемент . Используйте метод грубой силы , заключающийся в сканировании всего стека.

4.55 Модифицируйте стандартную реализацию стека на базе массива из раздела 4.4 (программа 4.7) таким образом, чтобы в ней были запрещены повторяющиеся элементы по принципу удалять старый элемент . Используйте метод грубой силы , заключающийся в сканировании всего стека и перемещении его элементов.

4.56 Выполните упражнения 4.54 и 4.55 для реализации стека на базе связного списка из раздела 4.4 (программа 4.8).

о 4.57 Разработайте реализацию стека магазинного типа, в которой повторяющиеся элементы запрещены по принципу удалять старый элемент . Элементами стека являются целые числа в диапазоне от О до Л/ - 1, а операции push и pop должны иметь постоянное время выполнения. Подсказка: возьмите представление стека на базе двухсвязного списка и воспользуйтесь указателями на узлы этого списка, а не массивом индексных значений.

4.58 Выполните упражнения 4.54 и 4.55 для очереди FIFO.

4.59 Выполните упражнение 4.56 для очереди FIFO.

4.60 Выполните упражнение 4.57 для очереди FIFO.

4.61 Выполните упражнения 4.54 и 4.55 для рандомизированной очереди.

4.62 Напищите клиентскую программу для АТД, полученного в упражнении 4.61, которая использует рандомизированную очередь без повторяющихся элементов.

4.8 АТД первого класса

Интерфейсы и реализации АТД Стек и Очередь FIFO в разделах с 4.2 по 4.7 достигают важной цели: сокрытие от клиентских профамм структур данных, используемых в реализациях. Эти АТД весьма полезны и будут служить в качестве основы для множества других реализаций, рассматриваемых в книге.

Однако, когда такие типы данных используются в программах таким же образом, как и встроенные типы данных, например, int или float, профаммиста могут подстерегать ловушки. В данном разделе мы рассмофим, как конструировать АТД, с которыми программы-клиенты могут работать так же, как и со встроенными типами данных, без нарушения принципа сокрытия деталей реализации от клиентских программ.

Определение 4.4 Тип данных первого класса - это тип данных, который может использоваться в программах таким же образом, как и встроенные типы данных.

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

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