Непрерывная реализация стека с помощью массива

Если максимально возможное количество элементов в стеке реально ограничено каким-либо значением, можно предложить самый простой способ реализации — массив. В этом случае для стека выделяется непрерывная область памяти ограниченных размеров. Фактическое количество элементов в стеке в произвольный момент времени может быть намного меньше заданного граничного значения, но ни в коем случае не может быть больше. Поэтому при добавлении элементов в стек обязательно следует предусмотреть обработку аварийной ситуации, связанной с его переполнением.

Рис. 2.1. поясняет работу со стеком на основе массива из maxlength элементов. Идея проста — достаточно завести дополнительный указатель top на вершину стека (или индекс элемента, который в данный момент является вершиной). Заметим, что в реализации на языке С при работе с массивами удобно использовать указатели, при этом имя массива, на основе которого реализован стек, является указателем на самый первый элемент стека («дно» стека). Нулевое значение указателя top соответствует пустому стеку. В случае использования индексов, а не указателей, признаком пустого стека может быть любое предопределенное значение, например отрицательное число.

Рис.2.1. Представление стека с помощью массива

Алгоритмы для реализации операций удаления и вставки элементов просты и сводятся к изменению значения указателя top на единицу. При этом, конечно, нельзя забыть об обработке аварийных ситуаций, связанных с добавлением элемента в переполненный стек или попыткой извлечения элемента из пустого стека.

При определении структуры stack вначале зададимся максимальным размером массива и определим тип данных для элементов type_of_data, что позволит сделать определение самой структуры вполне универсальным.

const int maxlength=100; // максимальный размер (любой)

typedef char type_of_data; // тип элементов(любой)

struct stack

{ type_of_data data[maxlength]; // массив под стек

type_of_data *top; // указатель на вершину стека

// базовые функции для работы со стеком

stack() {top=NULL;}// конструктор, создание пустого стека

void push (type_of_data x); // поместить значение x в стек

type_of_data gettop();// получить элемент с вершины стека 

void pop(); // извлечь элемент с вершины стека

bool isnull() {return top==NULL;}//проверить, пуст ли стек

// дополнительная функция

void makenull(){stack();} // сделать стек пустым

};

Здесь конструктор stack() используется в качестве базовой функции create для создания пустого стека. Дополнительная функция makenull() обычно включается в состав методов для работы со стеком, но она не является базовой, т. к. может быть реализована через другие функции. В данном случае она легко реализуется явным вызовом конструктора stack().

Приведем реализацию функций push() и pop(). Напомним, что знак:: обозначает принадлежность метода структуре stack().

void stack::push (type_of_data x)

{ if (isnull()) { top=data; *top=x;} //стек был пуст

else

if (top-data<maxlength-1) { top++; *top=x;}

else

{ cerr << "Стек полон\n"; exit(2); // аварийная ситуация

}

}

void stack::pop ()

{ //проверим, не пуст ли стек и обработаем аварийную ситуацию

if (isnull()) {cerr << "Стек пуст \n"; exit(1);}  

if (top==data) makenull(); else top--; // удалили элемент

}

Реализация функции gettop элементарна, однако ее вызов в случае пустого стека приводит к той же аварийной ситуации, что и в функции pop.

Обычно определение структуры и реализацию методов располагают в двух разных файлах, например, stack.h и stack.cpp, которые затем можно подключить к любому проекту на С++. Для использования стека достаточно объявить переменную типа stack, а затем обращаться к методам стека, например:

stack s;

s.push(’a’); // поместили один символ на вершину стека

При использовании других типов данных для элементов стека требуется изменить оператор typedef в определении стека.

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

Чтобы исключить принципиальную возможность подобных действий со стороны программ-клиентов, необходимо явно определить область видимости private для массива data и указателя top. Заметим, что если в приведенном выше определении стека заменить тип struct на class, то программы-клиенты вообще не смогут использовать ни один из методов, поскольку элементы класса по умолчанию имеют область видимости private (в этом принципиальная разница типов class и struct). Поэтому при использовании класса явное определение public для методов обязательно.

Оставим эти усовершенствования для самостоятельных упражнений.