| Информатика. Классификация структур данных. | |
|
|
| |
|
Общее понятие структуры данных.
Понятие структуры данных является настолько фундаментальным, что для него сложно
подобрать простое определение. Задача упрощается, если попробовать сформулировать
это понятие по отношению к типам данным и переменным. Как известно, программа
представляет собой единство алгоритма (процедур, функций) и обрабатываемых ими
данных. Данные, в свою очередь, определяются базовыми и производными типами
данных -"идеальными" представлениями переменных фиксированной размерности
с наборами известных операций над ними и их компонентами. Переменные -это именованные
области памяти, в которые "отображаются" сконструированные типы данных.
В программе всегда можно выделить группы косвенно связанных (по использованию
данных в одних и тех же процедурах и функциях) и непосредственно связанных (по
наличию взаимосвязей через указатели) переменных. Их в первом приближении и
можно считать структурами данных.
Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования мы всегда можем заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.
В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).
Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.
Рис. 1.1. Классификация структур данных
Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.
В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти ( односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.
В языках программирования понятие "структуры данных" тесно связано с понятием "типы данных". Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.
Информация по каждому типу однозначно определяет :
СТРУКТУРА ДАННЫХ - совокупность физически (типы данных) и логически (алгоритм, функции) взаимосвязанных переменных и их значений.
Заметим, что понятие структуры данных имеет отношение не только к переменным,
которые ее составляют, но и к алгоритмам (функциям), которые не только логически
связывают переменные между собой, но и определяют внутренние значения, которые
также должны быть свойственны этой структуре данных. Например, последовательность
положительных значений , размещенная в массиве и имеющая переменную размерность
(структура данных), может иметь нулевой ограничитель. Все операции по формированию
и проверке этого ограничителя реализуются функциями. Таким образом, можно сказать,
что значительная часть структуры данных "зашита" в алгоритмах ее обработки.
Известный нам способ определения переменных через типы данных характеризуется
тем, что, во-первых, количество переменных в программе фиксировано, а во-вторых,
размерность их не может быть изменена во время работы программы. Если взаимосвязи
между этими переменными имеют более-менее постоянный характер, то такие структуры
данных можно назвать статическими.
СТАТИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность фиксированного
количества переменных постоянной размерности с неизменным характером связей
между ними
И наоборот, если один из параметров структуры данных -количество переменных,
их размерность или взаимосвязи между ними меняются во время работы программы,
то такие структуры данных называются динамическими.
ДИНАМИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность переменных, количество, размерность или характер взаимосвязей между которыми меняется во время работы программ.
Динамические структуры данных базируются на двух элементах языка программирования:
Простые структуры данных называют также примитивными или базовыми структурами. Эти структуры служат основой для построения более сложных структур. В языках программирования простые структуры описываются простыми (базовыми) типами. К таким типам относятся: числовые, битовые, логические, символьные, перечисляемые, интервальные, указатели. В дальнейшем изложении мы ориентируемся в основном на язык PASCAL и его реализации в среде MS DOS. Структура простых типов PASCAL приведена на рис 1.2 (через запятую указан размер памяти в байтах, требуемый для размещения данных соответствующего типа). В других языках программирования набор простых типов может несколько отличаться от указанного. Размер же памяти, необходимый для данных того или иного типа, может быть разным не только в разных языках программирования, но и в разных реализациях одного и того же языка.
Рис. 1.2. Структура простых типов PASCAL.
Статические структуры относятся к разряду непримитивных структур, которые, фактически, представляют собой структурированное множество примитивных, базовых, структур. Например, вектор может быть представлен упорядоченным множеством чисел. Поскольку по определению статические структуры отличаются отсутствием изменчивости, память для них выделяется автоматически - как прави- ло, на этапе компиляции или при выполнении - в момент активизации того программного блока, в котором они описаны. Ряд языков программирования (PL/1, ALGOL-60) допускают размещение статических структур в памяти на этапе выполнения по явному требованию программиста, но и в этом случае объем выделенной памяти остается неизменным до уничтожения структуры. Выделение памяти на этапе компиляции является столь удобным свойством статических структур, что в ряде задач программисты используют их даже для представления объектов, обладающих изменчивостью. Например, когда размер массива неизвестен заранее, для него резервируется максимально возможный размер.
Каждую структуру данных характеризуют её логическим и физическим представлениями. Очень часто говоря о той или иной структуре данных, имеют в виду её логическое представление. Физическое представление обычно не соответствует логическому, и кроме того, может существенно различаться в разных программных системах. Нередко физической структуре ставится в соответствие дескриптор, или заголовок, который содержит общие сведения о физической структуре. Дескриптор необходим, например, в том случае, когда граничные значения индексов элементов массива неизвестны на этапе компиляции, и, следовательно, выделение памяти для массива может быть выполнено только на этапе выполнения программы (как в языке PL/1, ALGOL-60). Дескриптор хранится как и сама физическая структура, в памяти и состоит из полей, характер, число и размеры которых зависят от той структуры, которую он описывает и от приня- тых способов ее обработки. В ряде случаев дескриптор является совершенно необходимым, так как выполнение операции доступа к структуре требует обязательного знания каких-то ее параметров, и эти параметры хранятся в дескрипторе. Другие хранимые в дескрипторе параметры не являются совершенно необходимыми, но их использование позволяет сократить время доступа или обеспечить контроль правильности доступа к структуре. Дескриптор структуры данных, поддерживаемый языками программирования, является "невидимым" для программиста; он создается компилятором и компилятор же, формируя объектные коды для доступа к структуре, включает в эти коды команды, обращающиеся к дескриптору.
Статические структуры в языках программирования связаны со структурированными типами. Структурированные типы в языках программирования являются теми средствами интеграции, которые позволяют строить структуры данных сколь угодно большой сложности. К таким типам относятся: массивы, записи (в некоторых языках - структуры) и множества (этот тип реализован не во всех языках).
Полустатические структуры данных.
Полустатические структуры данных характеризуются следующими признаками:
Если полустатическую структуру рассматривать на логическом уровне, то о ней можно сказать, что это последовательность данных, связанная отношениями линейного списка. Доступ к элементу может осуществляться по его порядковому номеру.
Физическое представление полустатических структур данных в памяти - это обычно последовательность слотов в памяти, где каждый следующий элемент расположен в памяти в следующем слоте (т.е. вектор). Физическое представление может иметь также вид однонаправленного связного списка (цепочки), где каждый следующий элемент адресуется указателем находящемся в текущем элементе. В последнем случае ограничения на длину структуры гораздо менее строгие.
Динамические структуры данных.
Динамические структуры по определению характеризуются отсутствием физической смежности элементов структуры в памяти непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки.
Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным. Элемент динамической структуры состоит из двух полей:
Когда связное представление данных используется для решения прикладной задачи, для конечного пользователя "видимым" делается только содержимое информационного поля, а поле связок используется только программистом-разработчиком.
Достоинства связного представления данных - в возможности обеспечения значительной изменчивости структур;
Вместе с тем связное представление не лишено и недостатков, основные из которых:
Последний недостаток является наиболее серьезным и именно им ограничивается применимость связного представления данных. Если в смежном представлении данных для вычисления адреса любого элемента нам во всех случаях достаточно было номера элемента и информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных данных. Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее поиск требуемого элемента выполняется следованием по цепочке указателей от элемента к элементу. Поэтому связное представление практически никогда не применяется в задачах, где логическая структура данных имеет вид вектора или массива - с доступом по номеру элемента, но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, списки, деревья и т.д.).
Оперативная память с точки зрения программиста - это массив элементов. Любой
элемент массива можно прочитать или записать сразу, за одно элементарное действие.
Массив можно рассматривать как простейшую структуру данных. Структуры данных,
в которых возможен непосредственный доступ к произвольным их элементам, называют
структурами данных с прямым, или с произвольным доступом (по-английски random
access). Наряду с массивом, структурой данных с прямым доступом является множество,
которое будет рассмотрено ниже. В других структурах данных непосредственный
доступ возможен лишь к одному или нескольким элементам, для доступа к остальным
элементам надо выполнить дополнительные действия. Такие структуры данных называются
структурами последовательного доступа. Примером структуры последовательного
доступа является магнитофон, на которым записаны песни. В любой момент можно
прослушать лишь очередную песню. Чтобы добраться до других музыкальных фрагментов,
надо перемотать ленту вперед или назад. Кстати, такие магнитофоны, или накопители
на магнитной ленте, очень долго использовались на ЭВМ, хотя сейчас уступили
свое место более надежным и компактным системам (съемным магнитным и оптическим
дискам, флэш-памяти и т.п.). Устройство компьютерного магнитофона было аналогично
устройству обычного бытового магнитофона.
С логической точки зрения, массивом является также важнейшая составляющая компьютера
- магнитный диск. Элементарной единицей чтения и записи для магнитного диска
служит блок. Размер блока зависит от конструкции конкретного диска, обычно он
кратен 512. За одну элементарную операцию можно прочесть или записать один блок
с заданным адресом.
Итак, наиболее важные запоминающие устройства компьютера - оперативная память
и магнитный диск - представляют собой массивы. Массив как бы дан программисту
свыше, так же как математику целые числа. Работа с элементами массива осуществляется
исключительно быстро, все элементы массива доступны без всяких предварительных
действий.
Тем не менее массивов недостаточно для написания эффективных программ. Например,
поиск элемента в массиве, если его элементы не упорядочены, невозможно реализовать
эффективно: нельзя изобрести ничего лучшего, кроме последовательного перебора
элементов. В случае упорядоченного хранения элементов можно использовать эффективный
бинарный поиск, но затруднения возникают при добавлении или удалении элементов
в середине массива и приводят к массовым операциям, т.е. операциям, время выполнения
которых зависит от числа элементов структуры. От этих недостатков удается избавиться,
реализуя множество элементов на базе сбалансированных деревьев или хеш-функции.
Есть и другие причины, по которым необходимо использовать более сложные, чем
массивы, структуры данных. Логика многих задач требует организации определенного
порядка доступа к данным. Например, в случае очереди элементы можно добавлять
только в конец, а забирать только из начала очереди; в стеке доступны лишь элементы
в вершине стека, в списке - элементы до и за указателем.
Наконец, массив имеет ограниченный размер. Увеличение размера массива в случае
необходимости приводит к переписыванию его содержимого в захваченную область
памяти большего размера, т.е. опять же к массовой операции. От этого недостатка
свободны ссылочные реализации структур данных: реализации на основе линейных
списков или на основе деревьев.
Реализация одних структур на базе других.
Реализация структуры данных на основе базовой структуры - это описание ее работы
в терминах базовой структуры. При этом считается, что базовая структура либо
дана изначально, либо уже кем-то реализована. Реализация должна включать в себя
описание идеи реализации (каким образом элементы реализуемой структуры хранятся
в базовой структуре, какие дополнительные переменные используются) и набор подпрограмм,
каждая из которых моделирует некоторое предписание реализуемой структуры при
помощи предписаний базовой структуры.
При рассмотрении любой структуры данных необходимо сначала описать ее с логической
точки зрения, а затем рассмотреть различные способы ее реализации. В качестве
базы реализации в большинстве случаев выступает либо массив, либо динамическая
память (т.е. память, в которой можно захватывать участки требуемого размера
и освобождать ранее захваченные участки, когда они уже больше не нужны).
Простейшие структуры данных. Стек. Очередь.
Наиболее важными из простейших структур данных являются стек и очередь. Эти структуры встречаются в программировании буквально на каждом шагу, в самых разнообразных ситуациях. Особенно интересен стек, который имеет самые неожиданные применения. В свое время при разработке серии ЭВМ IBM 360 в начале 70-х годов XX века фирма IBM совершила драматическую ошибку, не предусмотрев аппаратную реализацию стека. Эта серия содержала много других неудачных решений, но, к сожалению, была скопирована в Советском Союзе под названием ЕС ЭВМ (Единая Серия), а все собственные разработки были приостановлены. Это отбросило советскую промышленность на много лет назад в области разработки копьютеров.
Очередь как структура данных понятна даже людям, не знакомым с программированием.
Очередь содержит элементы, как бы выстроенные друг за другом в цепочку. У очереди
есть начало и конец. Добавлять новые элементы можно только в конец очереди,
забирать элементы можно только из начала. В отличие от обычной очереди, которую
всегда можно при желании покинуть, из середины программистской очереди удалять
элементы нельзя.
Очередь можно представить в виде трубки. В один конец трубки можно добавлять
шарики - элементы очереди, из другого конца они извлекаются. Элементы в середине
очереди, т.е. шарики внутри трубки, недоступны. Конец трубки, в который добавляются
шарики, соответствует концу очереди, конец, из которого они извлекаются - началу
очереди. Таким образом, концы трубки не симметричны, шарики внутри трубки движутся
только в одном направлении.
В принципе, можно было бы разрешить добавлять элементы в оба конца очереди и
забирать их также из обоих концов. Такая структура данных в программировании
тоже существует, ее название - "дек", от англ. Double Ended Queue,
т.е. очередь с двумя концами. Дек применяется значительно реже, чем очередь.
Использование очереди в программировании почти соответствует ее роли в обычной
жизни. Очередь практически всегда связана с обслуживанием запросов, в тех случаях,
когда они не могут быть выполнены мгновенно. Очередь поддерживает также порядок
обслуживания запросов. Рассмотрим, к примеру, что происходит, когда человек
нажимает клавишу на клавиатуре компьютера. Тем самым человек просит компьютер
выполнить некоторое действие. Например, если он просто печатает текст, то действие
должно состоять в добавлении к тесту одного символа и может сопровождаться перерисовкой
области экрана, прокруткой окна, переформатированием абзаца и т.п.
Любая, даже самая простая, операционная система всегда в той или иной степени
многозадачна. Это значит, что в момент нажатия клавиши операционная система
может быть занята какой-либо другой работой. Тем не менее, операционная система
ни в какой ситуации не имеет права проигноровать нажатие на клавишу. Поэтому
происходит прерывание работы компьютера, он запоминает свое состояние и переключается
на обработку нажатия на клавишу. Такая обработка должна быть очень короткой,
чтобы не нарушить выполнение других задач. Команда, отдаваемая нажатием на клавишу,
просто добавляется в конец очереди запросов, ждущих своего выполнения. После
этого прерывание заканчивается, компьютер восстанавливает свое состояние и продолжает
работу, которая была прервана нажатием на клавишу. Запрос, поставленный в очередь,
будет выполнен не сразу, а только когда наступит его черед.
В системе Windows работа оконных приложений основана на сообщениях, которые
посылаются этим приложениям. Например, бывают сообщения о нажатии на клавишу
мыши, о закрытии окна, о необходимости перерисовки области окна, о выборе пункта
меню и т.п. Каждая программа имеет очередь запросов. Когда программа получает
свой квант времени на выполнение, она выбирает очередной запрос из начала очереди
и выполняет его. Таким образом, работа оконного приложения состоит, упрощенно
говоря, в последовательном выполнении запросов из ее очереди. Очередь поддерживается
операционной системой.
Подход к программированию, состоящий не в прямом вызове процедур, а в посылке
сообщений, которые ставятся в очередь запросов, имеет много преимуществ и является
одной из черт объектно-ориентированного программирования. Так, например, если
оконной программе необходимо завершить работу по какой-либо причине, лучше не
вызывать сразу команду завершения, которая опасна, потому что нарушает логику
работы и может привести к потере данных. Вместо этого программа посылает самой
себе сообщение о необходимости завершения работы, которое будет поставлено в
очередь запросов и выполнено после запросов, поступивших ранее.
Реализация очереди на базе массива.
Как уже было сказано, программисту массив дан свыше, все остальные структуры
данных нужно реализовывать на его основе. Конечно, такая реализация может быть
многоэтапной, и не всегда массив выступает в качестве непосредственной базы
реализации. В случае очереди наиболее популярны две реализации: непрерывная
на базе массива, которую называют также реализацией на базе кольцевого буфера,
и ссылочная реализация, или реализация на базе списка. Ссылочные реализации
будут рассмотрены ниже.
При непрерывной реализации очереди в качестве базы выступает массив фиксированной
длины N, таким образом, очередь ограничена и не может содержать более N элементов.
Индексы элементов массива изменяются в пределах от 0 до N - 1. Кроме массива,
реализация очереди хранит три простые переменные: индекс начала очереди, индекс
конца очереди, число элементов очереди. Элементы очереди содержатся в отрезке
массива от индекса начала до индекса конца.
При добавлении нового элемента в конец очереди индекс конца сперва увеличивается
на единицу, затем новый элемент записывается в ячейку массива с этим индексом.
Аналогично, при извлечении элемента из начала очереди содержимое ячейки массива
с индексом начала очереди запоминается в качестве результата операции, затем
индекс начала очереди увеличивается на единицу. Как индекс начала очереди, так
и индекс конца при работе двигаются слева направо. Что поисходит, когда индекс
конца очереди достигает конца массива, т.е. N - 1?
Ключевая идея реализации очереди состоит в том, что массов мысленно как бы зацикливается
в кольцо. Считается, что за последним элементом массива следует его первый элемент
(напомним, что последний элемент имеет индекс N - 1, а первый - индекс 0). При
сдвиге индекса конца очереди вправо в случае, когда он указывает на последний
элемент массива, он переходит на первый элемент. Таким образом, непрерывный
отрезок массива, занимаемый элементами очереди, может переходить через конец
массива на его начало.
Стек - самая популярная и, пожалуй, самая важная структура данных в программировании.
Стек представляет собой запоминающее устройство, из которого элементы извлекаются
в порядке, обратном их добавлению. Это как бы неправильная очередь, в которой
первым обслуживают того, кто встал в нее последним. В программистской литературе
общепринятыми являются аббревиатуры, обозначающие дисциплину работы очереди
и стека. Дисциплина работы очереди обозначается FIFO, что означает первым пришел
- первым уйдешь (First In First Out). Дисциплина работы стека обозначается LIFO,
последним пришел - первым уйдешь (Last In First Out).
Стек можно представить в виде трубки с подпружиненым дном, расположеной вертикально.
Верхний конец трубки открыт, в него можно добавлять, или, как говорят, заталкивать
элементы. Общепринятые английские термины в этом плане очень красочны, операция
добавления элемента в стек обозначается push, в переводе "затолкнуть, запихнуть".
Новый добавляемый элемент проталкивает элементы, помещеные в стек ранее, на
одну позицию вниз. При извлечении элементов из стека они как бы выталкиваются
вверх, по-английски pop ("выстреливают").
Примером стека может служить стог сена, стопка бумаг на столе, стопка тарелок
и т.п. Отсюда произошло название стека, что по-английски означает стопка. Тарелки
снимаются со стопки в порядке, обратном их добавлению. Доступна только верхняя
тарелка, т.е. тарелка на вершине стека. Хорошим примером будет также служить
железнодорожный тупик, в который можно составлять вагоны.
Использование стека в программировании.
Стек применяется довольно часто, причем в самых разных ситуациях. Объединяет
их следующая цель: нужно сохранить некоторую работу, которая еще не выполнена
до конца, при необходимости переключения на другую задачу. Стек используется
для временного сохранения состояния не выполненного до конца задания. После
сохранения состояния компьютер переключается на другую задачу. По окончании
ее выполнения состояние отложенного задания восстанавливается из стека, и копьютер
продолжает прерванную работу.
Почему именно стек используется для сохранения состояния прерванного задания?
Предположим, что компьютер выполняет задачу A. В процессе ее выполнения возникает
необходимость выполнить задачу B. Состояние задачи A запоминается, и компьютер
переходит к выполнению задачи B. Но ведь и при выполнении задачи B компьютер
может переключиться на другую задачу C, и нужно будет сохранить состояние задачи
B, прежде чем перейти к C. Позже, по окончании C будет сперва восстановлено
состояние задачи B, затем, по окончании B, - состояние задачи A. Таким образом,
восстановление происходит в порядке, обратном сохранению, что соответствует
дисциплине работы стека.
Стек позволяет организовать рекурсию, т.е. обращение подпрограммы к самой себе
либо непосредственно, либо через цепочку других вызовов. Пусть, например, подпрограмма
A выполняет алгоритм, зависящий от входного параметра X и, возможно, от состояния
глобальных данных. Для самых простых значений X алгоритм реализуется непосредственно.
В случае более сложных значений X алгоритм реализуется как сведение к применению
того же алгоритма для более простых значений X. При этом подпрограмма A обращается
сама к себе, передавая в качестве параметра более простое значение X. При таком
обращении предыдущее значение параметра X, а также все локальные переменные
подпрограммы A сохраняются в стеке. Далее создается новый набор локальных переменных
и переменная, содержащая новое (более простое) значение параметра X. Вызванная
подпрограмма A работает с новым набором переменных, не разрушая предыдущего
набора. По окончании вызова старый набор локальных переменных и старое состояние
входного параметра X восстанавливаются из стека, и подпрограмма продолжает работу
с того места, где она была прервана.
На самом деле даже не приходится специальным образом сохранять значения локальных
переменных подпрограммы в стеке. Дело в том, что локальные переменные подпрограммы
(т.е. ее внутренние, рабочие переменные, которые создаются в начале ее выполнения
и уничтожаются в конце) размещаются в стеке, реализованном аппаратно на базе
обычной оперативной памяти. В самом начале работы подпрограмма захватывает место
в стеке под свои локальные переменные, этот участок памяти в аппаратном стеке
называют обычно блок локальных переменных или по-английски frame ( "кадр
"). В момент окончания работы подпрограмма освобождает память, удаляя из
стека блок своих локальных переменных.
Кроме локальных переменных, в аппаратном стеке сохраняются адреса возврата при
вызовах подпрограмм. Пусть в некоторой точке программы A вызывается подпрограмма
B. Перед вызовом подпрограммы B адрес инструкции, следующей за инструкцией вызова
B, сохраняется в стеке. Это так называемый адрес возврата в программу A. По
окончании работы подпрограмма B извлекает из стека адрес возврата в программу
A и возвращает управление по этому адресу. Таким образом, компьютер продолжает
выполнение программы A, начиная с инструкции, следующей за инструкцией вызова.
В большинстве процессоров имеются специальные команды, поддерживающие вызов
подпрограммы с предварительным помещением адреса возврата в стек и возврат из
подпрограммы по адресу, извлекаемому из стека. Обычно команда вызова назывется
call, команда возврата - return.
В стек помещаются также параметры подпрограммы или функции перед ее вызовом.
Порядок их помещения в стек зависит от соглашений, принятых в языках высокого
уровня. Так, в языке Си или C++ на вершине стека лежит первый аргумент функции,
под ним второй и так далее. В Паскале все наоборот, на вершине стека лежит последний
аргумент функции. (Поэтому, кстати, в Си возможны функции с переменным числом
аргументов, такие, как printf, а в Паскале нет.)
В Фортране-4, одном из самых старых и самых удачных языков программирования,
аргументы передаются через специальную область памяти, которая может располагаться
не в стеке, поскольку до конца 70-х годов XX века еще существовали компьютеры
вроде IBM 360 или ЕС ЭВМ без аппаратной реализации стека. Адреса возврата также
сохранялись не в стеке, а в фиксированных для каждой подпрограммы ячейках памяти.
Программисты называют такую память статической в том смысле, что статические
переменные занимают всегда одно и то же место в памяти в любой момент работы
программы. При использовании только статической памяти рекурсия невозможна,
поскольку при новом вызове предыдущие значения локальных переменных разрушаются.
В эталонном Фортране-4 использовались только статические переменные, а рекурсия
была запрещена. До сих пор язык Фортран широко используется в научных и инженерных
расчетах, однако, современный стандарт Фортрана-90 уже вводит стековую память,
устраняя недостатки ранних версий языка.
Реализация стека на базе массива.
Реализация стека на базе массива является классикой программирования. Иногда
даже само понятие стека не вполне корректно отождествляется с этой реализацией.
Базой реализации является массив размера N, таким образом, реализуется стек
ограниченного размера, максимальная глубина которого не может превышать N. Индексы
ячеек массива изменяются от 0 до N - 1. Элементы стека хранятся в массиве следующим
образом: элемент на дне стека располагается в начале массива, т.е. в ячейке
с индексом 0. Элемент, расположенный над самым нижним элементом стека, хранится
в ячейке с индексом 1, и так далее. Вершина стека хранится где-то в середине
массива. Индекс элемента на вершине стека хранится в специальной переменной,
которую обычно называют указателем стека (по-английски Stack Pointer или просто
SP).
Когда стек пуст, указатель стека содержит значение минус единица. При добавлении
элемента указатель стека сначала увеличивается на единицу, затем в ячейку массива
с индексом, содержащимся в указателе стека, записывается добавляемый элемент.
При извлечении элемента из стека сперва содержимое ячейки массива с индексом,
содержащимся в указателе стека, запоминается во временной переменной в качестве
результата операции, затем указатель стека уменьшается на единицу.
В приведенной реализации стек растет в сторону увеличения индексов ячеек массива.
Часто используется другой вариант реализации стека на базе вектора, когда дно
стека помещается в последнюю ячейку массива, т.е. в ячейку с индексом N - 1.
Элементы стека занимают непрерывный отрезок массива, начиная с ячейки, индекс
которой хранится в указателе стека, и заканчивая последней ячейкой массива.
В этом варианте стек растет в сторону уменьшения индексов. Если стек пуст, то
указатель стека содержит значение N (которое на единицу больше, чем индекс последней
ячейки массива).
