4.4 Реализации АТД стека

в данном разделе рассматриваются две реализации АТД стека: в одной используются массивы, в другой - связные списки. Эти реализации получаются в результате простого применения базовых инструментальных средств, рассмотренных в главе 3. Мы полагаем, что они различаются только своей производительностью (быстродействием).

Программа 4.7 Реализация стека магазинного типа на базе массива

В этой реализации N элементов стека хранятся как элементы массива: s[0], ... , s[N-1], начиная с первого занесенного элемента и завершая последним. Верхушкой стека (позицией, в которую будет заноситься следующий элемент стека) является позиция s[N]. Максимальное количество элементов, которое может вмещать стек, программа-клиент передает в виде аргумента в конструктор STACK, размещающий в памяти массив данного размера; однако код не проверяет такие ошибки, как помещение элемента в переполненный стек (или выталкивание элемента из пустого стека).

template <class Item> class STACK {

private:

Item *s; int N; public:

STACK(int maxN)

{ s = new Item[maxN] ; N = 0; } int empty 0 const

{ return N == 0; } void push (Item item)

{ s[N++] = item; } Item popO

{ return St-N] ; }

Если для представления стека применяется массив, то все функции, объявленные в программе 4.4, реализуются очень просто, что видно из программы 4.7. Элементы заносятся в массив в точности так, как показано на рис. 4.1, при этом отслеживается индекс верхушки стека. Выполнение операции затолкнуть означает запоминание элемента в позиции массива, указываемой индексом верхушки стека, а затем увеличение этого индекса на единицу; выполнение операции вытолкнуть означает уменьшение индекса на единицу и извлечение элемента, обозначенного этим индексом. Операция создать (конструктор) осуществляет размещение массива указанного размера, а операция проверить, пуст ли стек проверяет, не равен ли индекс нулю. Скомпилированная вместе с клиентской программой (такой, как программа 4.5 или 4.6), эта реализация обеспечивает рациональный и эффективный стек магазинного типа.

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

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

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

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

bead

L[u;

head

head

NEW head

head

heed

ЧШ1р

Eltl

РИСУНОК 4.5 СТЕК МАГАЗИННОГО ТИПА НА БАЗЕ СВЯЗНОГО СПИСКА

Стек представлен указателем head, который указывает на первый (последний вставленный) элемент. Чтобы вытолкнуть элемент из стека (top), удаляется элемент в начале списка, устанавливая head равным указателю связи из этого элемента. Для заталкивания в стек нового элемента (bottom), он присоединяется в начало списка путем установки его поля связи так, чтобы оно указывало на head, а указателя head - так, чтобы он указывал на новый элемент.

Программа 4.8 Реализация стека магазинного типа на базе связного списка

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

template <class Item> class STACK {

private:

Struct node

{ Item item; node* next; node(Item x, node* t)

{ item = x; next = t; }

typedef node *link; link head; public:

STACK(int)

{ head =0; } int empty 0 const

{ return head ==0; } void push(Item x)

{ head = new node(x, head); } Item popO

{ Item V = head->item; link t = head->next; delete head; head = t; return v; }

Программы 4.7 и 4.8 представляют две различные реализации одно и того же АТД. Можно заменять одну реализацию другой, не делая никаких изменений в клиентских программах, подобных тем, которые рассматривались в разделе 4.3. Они отличаются только производительностью. Реализация на базе массива использует объем памяти, необходимый для размещения максимального числа элементов, которые может вместить стек в процессе вычислений; реализация на базе списка использует объем памяти пропорционально количеству элементов, но при этом всегда расходует дополнительную память для одной связи на каждый элемент, а также дополнительное время на распределение памяти при каждой операции затолкнуть и освобождение памяти при каждой операции вытолкнуть. Если требуется стек больших размеров, который обычно заполняется практически полностью, по-видимому, предпочтение стоит отдать реализации на базе массива. Если же размер стека варьируется в широких пределах и присутствуют другие структуры данных, которым требуется память, не используемая во время, когда в стеке находится несколько элементов, предпочтение следует отдать реализации на базе связного списка.

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