Полустатические структуры данных

В разделе 1 пособия мы уже давали определение списка. Вспомним его. Списком называется линейно-упорядоченная последовательность элементов данных Ei, Е2,Е„, где п>0.

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

Полустатические структуры данных характеризуются следующими признаками:

  • - они имеют переменную длину и простые процедуры ее изменения;
  • - изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.

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

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

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

Наиболее часто встречающиеся полустатические структуры данных - стеки, очереди и деки.

Стек

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

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

Доступ к информации в стеке реализуется по принципу «Последним пришёл, первым ушёл», то есть LIFO (Last in, First out).

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

Известные примеры стека - винтовочный патронный магазин и железнодорожный разъезд для сортировки вагонов (рис. 4).

Железнодорожный разъезд

Рис. 4. Железнодорожный разъезд

Рассмотрим использование железнодорожного разъезда для сортировки вагонов на следующем примере.

Представьте себе, что четыре железнодорожных вагона находятся на входной стороне пути (рис. 4) и перенумерованы соответственно 1, 2, 3 и 4. Предположим, что мы выполняем следующую последовательность операций:

  • 1. Вагон 1 в стек;
  • 2. Вагон 2 в стек;
  • 3. Вагон 2 на выход;
  • 4. Вагон 3 в стек;
  • 5. Вагон 4 в стек;
  • 6. Вагон 4 на выход;
  • 7. Вагон 3 на выход;
  • 8. Вагон 1 на выход.

В результате этих операций первоначальный порядок вагонов, 1234, изменился на 2431.

По способу реализации различают статические и динамические стеки.

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

Динамические стеки обычно программируются в виде односвязных списков в динамической памяти. Достоинства - размер заранее не определяется и может занимать всю свободную память ЭВМ. Недостаток - сложность и низкая скорость их обработки.

В данном разделе будет рассмотрен только статический способ реализации стека.

Логическую структуру стека рассмотрим с помощью рисунка 5. На рисунке Ei, Ег, Еп - элементы стека, каждый из которых может содержать одно или несколько полей.

Логическая структура стека

Рис. 5. Логическая структура стека

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

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

Для стека характерны следующие операции:

  • • включение элемента;
  • • исключение элемента;
  • • неразрушающее чтение элемента из вершины стека;
  • • проверка пустоты;
  • • проверка переполнения;
  • • очистка стека;
  • • определение текущего числа элементов в стеке.

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

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

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

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

В указателе U хранится информация о позиции верхнего элемента в стеке. Если стек пуст, U = 0. Если стек содержит единственный элемент - U = 1 и т.д.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >