4 Полустатические структуры

4.1 Стек, очередь и дек как полустатические структуры

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

постоянством структуры в течение всего времени её существования;

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

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

Поэтому перечисленные структуры называем статическими структурами.

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

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

Линейным списком называется упорядоченная последовательность элементов данных х(1), х(2), ..., х(n), где n ≥ 0. При этом каждый элемент содержит одинаковое количество полей.

Структурные свойства линейного списка ограничиваются лишь линейным (одномерным) относительным положением элементов. Так, если n > 0, то х(1) – первый элемент. Если 1 < k < n, то элементу х(k) предшеству­ет элемент х(k-1), а за х(k) следует х(k+1). Х(n) – последний элемент.

Упорядоченность элементов списка может задаваться неявно путем их последовательного расположения как в логической структуре, так и в памяти ЭВМ. Это последовательный список.

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

Если n = const, то линейный список сводится к массиву, записи или таблице.

Если же допустить изменение n, то получим структуру данных, не удовлетворяющую свойству постоянст­ва. Такие структуры называются полустатическими.

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

К таким операциям относятся:

1. доступ к элементу с номером k;

2. включение нового элемента перед элементом с номером k;

3. удаление элемента с номером k;

4. объединение последовательно двух списков в один слиянием;

5. разбиение списка на два и более;

6. нахождение в списке элемента с заданным значением поля. Наиболее простые операции получаются при k = 1 или k = n.

Очень часто встречаются линейные списки, в которых включение, исключение, доступ к значениям произ­водятся только к первому или последнему элементам. Это и есть стеки, очереди и деки.

Стек (stack) - линейный последовательный список, в котором доступ, включение и исключение элементов выполняется только с одного конца: k = n , т.е. доступен только последний элемент. Дисциплина обслуживания элементов стека выражается аббревиатурой

LIFO (Last – In – First – Out) –

"последний пришел – первым вышел"

Примером стека может служить винтовочный патронный магазин (отсюда второе название стека – мага­зин, а также железнодорожный разъезд для сортировки вагонов (сортировочный тупик).

Вход Выход

Рис. 5

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

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

Логическая структура стека выглядит следующим образом

Верхняя граница стека ►

Свободные слоты

\

Указатель стека

Вершина стека

En

En-i

Нижняя граница стека »

Еъ

Е₂

Ei

Рис. 6

Здесь E₁, E₂, ..., E_n – элементы стека, каждый из которых может содержать одно или несколько полей дан­ных. Важнейшие операции над элементами стека (включение и исключение) производятся с его вершины, при­чем в каждый момент для исключения доступен только элемент E_n .

Вершина стека адресуется с помощью специального указателя.

Включение нового элемента в стек производится следующим образом. Вначале указатель перемещается "вверх" на длину слота или ячейки, а затем по значению указателя в стек помещается информация о новом эле­менте.

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

Стек считается пустым, если указатель смещен вниз на длину одной ячейки относительно низа стека.

Кроме включения и исключения элементов над стеком возможны другие операции: очистка стека и про­верка объема стека (т.е. числа элементов в нем).

Физическая структура стека.

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

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

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

Дескриптор

Имя стека

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

Указатель

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

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

Физическая структура

Рис. 7 Очередь – линейный последовательный список, в котором все включения производятся в конце списка (в хвосте очереди), а исключения – в начале (в голове очереди).

Дисциплина обслуживания в очереди выражается принципом

FIFO (First – In – First – Out) –

"первым пришел – первым вышел".

По железнодорожной аналогии – линейный участок пути с одним направлением.

Вход

Выход

4

Рис. 8

Для индикации хвоста и головы очереди организуются два указателя. Схема простейшей очереди:

Ai А₂

Ашах

_{t t}

f Г

Рис. 9

занятые слоты

Выделяется конечная последовательность ячеек или слотов. A₁, A₂, ..., A_max – адреса, f - указатель

головного элемента очереди, r - адресует первый свободный слот, следующий за хвостовым.

Основные операции над очередью – включение и исключение элемента.

При включении новый элемент заносится в слот, адресуемый указателем r, после чего указатель необхо­димо передвинуть к следующему пустому слоту (на схеме – вправо).

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

Другие возможные операции: проверка текущей длины и очистка.

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

Этого можно избежать, если после A_max переводить r на слот с адресом A₁. Организованная таким образом очередь называется кольцевой. Она работает по схеме:

Ai A2

Amax I

RF

Рис. 10

В такой очереди возможно любое из соотношений f < r,

f = r, (пустая очередь) f > r.

Дек (от англ. deque –double ended queue) – линейный последовательный список с двумя концами, в кото­ром как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Дек – более общая структура среди трех. Является сочетанием очереди и стека. Структуру дека имитирует, например, схема железнодорожного разъезда

Частными случаями являются:

1. дек с ограниченным входом;

2. дек с ограниченным выходом.

В первом случае закрыт верхний участок пути, во втором случае – нижний. Логическая и физическая структуры дека аналогичны логической и физической структурам очереди. Но

вместо хвоста и головы для дека принято говорить о левом и правом конце.

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