Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2021-04-18 | 118 |
5.00
из
|
Заказать работу |
|
|
Если максимально возможное количество элементов в стеке реально ограничено каким-либо значением, можно предложить самый простой способ реализации — массив. В этом случае для стека выделяется непрерывная область памяти ограниченных размеров. Фактическое количество элементов в стеке в произвольный момент времени может быть намного меньше заданного граничного значения, но ни в коем случае не может быть больше. Поэтому при добавлении элементов в стек обязательно следует предусмотреть обработку аварийной ситуации, связанной с его переполнением.
Рис. 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 для методов обязательно.
Оставим эти усовершенствования для самостоятельных упражнений.
|
|
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!