- •Введение
- •Структура программы на языке Си
- •Директивы препроцессора
- •Константы
- •Переменные
- •Арифметические выражения
- •Операция присваивания
- •Ввод информации с клавиатуры и вывод на экран
- •Логические выражения
- •Операторы управления
- •Оператор условного перехода if
- •Оператор выбора варианта
- •Перечисляемый тип данных
- •Циклы
- •Оператор цикла while
- •Оператор цикла do-while
- •Оператор цикла for
- •Локальные и глобальные переменные
- •Переменные с индексами (массивы)
- •Примеры обработки одномерных массивов
- •Многомерные массивы
- •Массивы и указатели
- •Арифметические и логические операции с указателями
- •Обработка массивов с помощью указателей
- •Обработка массивов переменной размерности
- •Обработка матриц переменной размерности
- •Обработка текстовой информации
- •Стандартные строки языка С++
- •Пример 1. Определение длины строки.
- •Пример 2. Копирование одной строки в другую
- •Пример 3. Исключение из строки символа.
- •Пример 4. Вставка в строку символа
- •Пример 5. Проверка правильности расстановки скобок.
- •Строки типа string
- •Массивы указателей
- •Указатели на функции
- •Сводная таблица форм объявления указателей
- •Преобразование типов
- •Ссылки
- •Структуры
- •Объединения
- •Файлы
- •Чтение файла в матрицу
- •Чтение файла в структуру
- •Функции для обработки произвольных полей структур
- •Связные списки
- •Контейнерные классы
- •Стеки
- •Рекурсия
- •Вопросы для самопроверки
- •Литература
156
Стеки
Стеком называется линейный список, для которого определены только две операции:
1.Вставка перед первым элементом.
2.Исключение первого элемента
Организовать стек можно следующими способами:
Смоделировать стек с помощью массива (например, массива структур). В этом случае операция инкремента (наращивания) индекса массива позволяет обратиться к следующему элементу массива (погружение в стек), а операция декремента (уменьшения) индекса обеспечивает обращение к предыдущему элементу стека (извлечение из стека). Поскольку размер массива может быть только фиксированным, то при погружении в стек должна выполняться проверка на переполнение стека, а при извлечении из стека значение индекса 0 свидетельствует о последнем элементе в стеке. Разновидность этого способа реализована аппаратными средствами в персональных компьютерах (для хранения индекса массива (являющегося просто областью оперативной памяти) выделен специальный регистр SP).
Организовать однонаправленный связный список с ограничением операций вставкой и исключением элементов в начале списка.
Выделять память для погружения элементов в стек и освобождать память при извлечении элементов из стека вручную. Для такой организации потребуется создание массива, в котором будут храниться указатели на области памяти, входящие в стек.
Использовать адаптер «стек» последовательного контейнера.
Использовать рекурсию.