Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Оснащения врачебно-сестринской бригады.
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2021-04-18 | 116 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!