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

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

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

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

Стек — такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка. Применяются и другие названия стека — магазин и очередь, функционирующая по принципу LIFO (Last In — Firs1 Out — «последним пришел—первым исключается»).

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

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

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

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

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

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

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

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

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