2. Методы формирования свободного списка

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

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

В методе сборки мусора (garbage collection) не требуется при разрыве каждой связки делать проверку элемента и возвращать освободившийся элемент в свободный список. Освободившийся элемент как бы «повисает» до тех пор, пока не будет исчерпан свободный список. И только после этого запускается процедура «сборки мусора», которая отыскивает все освободившиеся к тому времени элементы и включает их в свободный список. Для реализации метода сборки мусора в каждом элементе многосвязной структуры резервируется минимально возможное поле памяти для маркера, который используется на этапе поиска освободившегося элемента. С этой целью процедура маркирует все доступные элементы многосвязной структуры, т. е. такие элементы, к которым направлен хотя бы один указатель. Затем просматривается вся область памяти, отведенная для элементов, и в свободный список включаются все элементы, в которых отсутствует маркер.

Диспетчер кучи Delphi создает список свободных областей (free space list) по мере выполнения процедур «уничтожения» динамических переменных, таких, например, как Dispose.

7. Стеки, очереди, деки и операции в них

   1. Общая характеристика

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

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

Ниже приводится «классическое» описание, основанное на следующих постулатах:

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

2. элементы структуры в каждый текущий момент времени занимают сплошной участок памяти, т. е. структура является последовательной структурой;

3. для операций включения и исключения доступны только концевые элементы структуры, иными словами, внутренние части участка памяти, содержащего «полезные» элементы е₁, е₂, …, е_n, для этих операций недоступны.

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

2. Стек

Стек (stack)  это такой последовательный список е₁, е₂, …, е_n с переменной длиной n, включение в который нового элемента и исключение из него выполняется только с одной стороны. Говорят, что стек функционирует по принципу LIFO (Last In  First Out, т. е. «последним пришел  первым вышел»). Примером стековой организации является винтовочный магазин: патрон, вставленный в него последним, при стрельбе «выйдет» первым.

Логическая структура стека представлена на рисунке 7.1. Элементы стека могут иметь как одинаковые, так и различные размеры. Последний добавленный в стек элемент е_n, называется вершиной стека (top of stack). Важной составляющей структуры стека является указатель, направленный к вершине,  этот указатель называется указателем стека (stack pointer). Элемент, непосредственно примыкающий к нижней границе, называется дном стека (bottom of stack).

Рисунок 7.1 – Логическая структура стека

Для хранения стека в памяти отводится сплошная область памяти, называемая сегментом стека. Граничные адреса этой области памяти являются параметрами физической структуры стека. Физическая структура стека, показанная на рисунке 7.2, обычно дополняется дескриптором.

Важнейшие операции в стеке – включение и исключение. Применительно к стеку операцию включения обычно называют заталкиванием (push) элемента, а операцию исключения  выталкиванием (pop). Процедура заталкивания в стек нового элемента организуется как последовательность следующих действий: указатель стека сначала перемещается «вверх» (по рисунку 7.1) к слоту включаемого элемента, а затем по новому значению указателя помещается содержимое включаемого элемента. При выталкивании из стека сначала извлекается содержимое элемента е_n, а затем указатель стека перемещается «вниз» на длину слота исключаемого элемента. Таким образом указатель стека обслуживает динамику изменения стека.

Рисунок 7.2 – Физическая структура стека

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

Сегмент стека  важная область памяти, которую, наряду с сегментами кода и данных, создает компилятор, реализуя программу в виде исполняемого приложения. При работе в реальном режиме сегмент стека ограничивается 64 Кбайт, тогда как в защищенном режиме этот сегмент может занимать до 4 Гбайт. Сегмент стека можно увеличить или уменьшить до определенного размера, но он есть всегда.

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