русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Реализация стека


Дата добавления: 2013-12-23; просмотров: 770; Нарушение авторских прав


Откат

Стеки

Стек это список, у которого операции добавления и удаления элементов разрешены только на одном конце. Стек можно представить как стопку элементов, в которую можно сверху добавить или взять элемент. Вершиной стека называется тот конец где возможно добавление или удаление элементов. Другой конец стека называют основанием.

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

Под термином «откат» подразумевается поиск выхода из ситуации путем выполнения действий, которые привели нас туда, в обратном порядке. Стек используется во всех процессах, где выход производится в порядке, обратном входу. Выполненные действия помещаются в стек, а затем, при выполнении их в обратном порядке, извлекаются оттуда.

Для реализации стека резервируют подряд расположенные ячейки памяти. Размер свободной области памяти, выделенной для размещения стека, ограничивает его размеры (количество элементов, умноженное на размер каждого элемента, если они однотипны).

Начало области памяти (адрес ее первой ячейки) считается основанием стека. Добавляемые элементы размещаются друг за другом от основания к вершине, то есть от начала области и вплоть до ее конца (до области, занятой другими данными).

Полная система стека предполагает наличие процедур для записи и удаления элементов стека, а также для проверки перед этими операциями, не пуст ли стек или не наполнен ли он до конца области памяти.

Если стек наполнен до конца выделенной для него области памяти, то можно перейти в другую область памяти (создание еще одного стека) и затем положить в основание нового стека указатель на предыдущий (на его вершину). Таким образом при обратном извлечении элементов, дойдя до основания последнего стека, найдем указатель и перейдем в вершину предыдущего стека.



Указатель стека содержит адрес его вершины. После операции добавления он увеличивается на число ячеек, соответствующее размеру (типу) добавленной переменной. После операции удаления он уменьшается.

Для того чтобы поместить в стек новую запись, указатель стека изменяется и указывает на свободное место над вершиной стека. Туда и помещается новая запись.

При считывании из стека указатель сначала указывает на вершину стека, а после считывания уменьшается и указывает на нижележащий еще не считанный элемент. Таким образом, считанный элемент стека более не доступен и не считается находящимся в стеке.

При обращении к стеку, программа обращается в ячейку памяти, где хранится указатель на стек. Указатель содержит адрес первой ячейки стека (адрес его вершины).



<== предыдущая лекция | следующая лекция ==>
Поддержка абстрактного списка | Реализация очереди


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.