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

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

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

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

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

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

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

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

Стек

Стек (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 Гбайт. Сегмент стека можно увеличить или уменьшить до определенного размера, но он есть всегда.

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