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