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

1. Постоянство структуры в течение всего времени ее существования.

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

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

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

ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ

Общее понятие списковой структуры

Списковой структурой, или списком, называется линейно - упорядоченная последовательность элементов данных Е(1), Е(2), ... , Е(n), где n>0, причем каждый элемент характеризуется одним и тем же набором полей. Такой список называют также линейным списком вследствие линейной упорядоченности его элементов. Упорядоченность элементов списка может задаваться неявно путем последовательного расположения его элементов как в логической структуре, так и в памяти машины. Такой список будем называть последовательным. С другой стороны, упорядоченность элементов может задаваться с помощью специальных указателей, или связок, располагаемых в элементах и дающих возможность для каждого элемента определить его предшественника или пользователя, или того и другого. Такие списки называются связными списками.

Ясно, что при n=const и соответствующем выборе элемента данных последовательный список сводится к вектору, массиву, записи или таблице. Например, вектор - такой последовательный список, в котором каждый элемент - скаляр одного и того же типа. Если допустить изменение длины списка n, то на основе последовательного списка можно получить структуры данных, не удовлетворяющие свойству постоянства. Такие структуры называются полустатическими. Наиболее известные примеры полустатических структур - стеки, очереди и деки. Они характеризуются ограниченным доступом.

Стеки

Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка. Стек функционирует по принципу LIFO (Last - In - First - Out - "последним пришел - первым исключается"). Наиболее известные примеры стека - винтовочный патронный магазин и железнодорожный разъезд для сортировки вагонов.

Логическая структура стека представлена на рис. 3.1. На этом рисунке Е1, Е2, ... Еn - обозначения элементов стека, каждый из которых может содержать одно или несколько полей данных.

Верхняя граница стека	®		ü ú ý þ
		. . .		Свободные слоты
				Указатель стека
Адрес верхнего элемента Вершина стека	®
		. . .
Нижняя граница стека	®
Рис.3.1 - Логическая структура стека

Важнейшие операции доступа к стеку - включение элементов и исключение элементов - осуществляются с вершины стека, причем в каждый момент для исключения доступен элемент Еn, находящийся на вершине стека. Вершина стека адресуется с помощью специального указателя. Для включения нового элемента в стек указатель сначала перемещается "вверх" на длину слота, или ячейки, а затем по значению указателя в стек помещается информация о новом элементе. При исключении элемента из стека сначала прочитывается информация об исключаемом элементе по значению указателя, а затем указатель смещается "вниз" на один слот. Стек считается пустым, если указатель смещен "вниз" на длину одной ячейки относительно низа стека. Используется также такая схема, в которой указатель адресует первую свободную ячейку списка.

Другие операции над стеком, кроме включения и исключения элементов, - очистка стека и проверка объема стека (т.е. проверка числа элементов в стеке).

Для хранения стека в памяти машины отводится сплошная область памяти, достаточно большая, чтобы в ней можно было поместить некоторое максимальное число элементов. Граничные адреса этой области являются параметрами физической структуры стека. Если в процессе заполнения стека указатель, перемещаясь "вверх", выходит за границу первоначально отведенной области памяти, то происходит переполнение стека, в результате чего становится невозможным включение в стек нового элемента. При отсутствии переполнения некоторая часть области памяти, отведенной для стека, свободна для включения новых элементов, как показано на рис. 3.1. Таким образом, хотя длина стека может изменяться в процессе его использования, эти изменения не должны выходить за пределы фиксированного участка памяти. Поэтому стек - полустатическая структура данных.

Физическая структура стека дополняется обычно дескриптором, в котором содержатся кроме указателя имя стека, границы физической структуры в памяти, а также описание элемента. На рис. 3.2 приведен пример физической структуры стека, причем символ ST в первом поле дескриптора является кодом стека.

ST

Имя стека

Адрес верхней границы

·

Указатель

·

·

Адрес нижней границы

Описание элемента

Слоты для элементов стека

Рис. 3.2 - Схема физической структуры стека

Очереди

Очередь - такой последовательный список с переменной длиной включение элементов в который происходит с одной стороны, а исключение элементов - с другой стороны списка, она функционирует по принципу FIFO (Fist - In - Fist - Out, т.е. "первым пришел - последним исключается"). Та сторона очереди, с которой осуществляется добавление элементов, называется хвостом или концом, очереди, другая - головой. Для индикации хвоста и головы организуются два указателя.

На рис. 3.3 приведена схема простейшей очереди. Для этой очереди выделена конечная последовательность ячеек или слотов, из которых в каждый момент времени элементами очереди заняты лишь часть последовательных слотов. Занятые слоты на рисунке помечены. Слоты имеют адреса . Каждый элемент очереди представляет собой в общем случае запись с одинаковой организацией для всех элементов. Идентификаторы Р1 и Р2 - указатели, причем Р1 - указатель головного элемента очереди, а Р2 - адресует первый свободный слот, следующий за хвостовым элементом.

Основные операции над очередью - включение элемента и исключение элемента. При включении новый элемент заносится в слот, адресуемый указателем Р2, после чего этот указатель должен быть "передвинут" к следующему (пустому) слоту. При исключении из очереди извлекается элемент, адресуемый указателем Р1, и после этого указатель Р1 перемещается к следующему слоту. Возможны и другие операции над очередью.

Из рис.3.3 ясно, что в процессе включения элементов неизбежно наступит переполнение очереди. Это произойдет независимо от того, исключаются ли элементы из очереди или не исключаются, так как состояние переполнения для простейшей очереди означает лишь выход указателя Р2 за пределы отведенного для слотов участка памяти. Такой недостаток схемы, представленной на рис.3.3, можно устранить, если после достижения указателем слота с адресом  переводить этот указатель на слот с адресом , если он пуст. Организованная таким образом очередь называется кольцевой, в ней возможно любое из соотношений Р1<Р2, Р1=Р2 и Р1>Р2, причем второе из этих соотношений соответствует пустой очереди.

Пример схемы кольцевой очереди показан на рис.3.4, на котором занятые слоты помечены. Стрелка обозначает факт продолжения или "зацикливания" очереди.

На рис. 3.5 показана схема физической структуры очереди. Имя и другая информация об очереди хранятся в дескрипторе, причем буква Q в первом поле дескриптора является признаком (кодом) очереди.

Деки

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

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