В последующем изложении нам потребуется общее понятие списка, или списковой структуры. Списком называется линейно-упорядоченная последовательность элементов данных Е(1), Е(2),..., Е(n), где n > 0, причем каждый элемент характеризуется одним и тем же набором полей. Определенный таким образом список называют также линейным списком вследствие линейной упорядоченности его элементов. Упорядоченность элементов списка может задаваться неявно путем последовательного расположения его элементов как в логической структуре, так и в памяти машины. Такой список будем называть последовательным. С другой стороны, упорядоченность элементов может задаваться с помощью специальных указателей, или связок, располагаемых в элементах и дающих возможность для каждого элемента определить его предшественника или последователя или того и другого. Такие списки называются связными списками и будут рассматриваться ниже.
Ясно, что при n = const и соответствующем выборе элемента данных последовательный список сводится к вектору, массиву, записи или таблице. Например, вектор — такой последовательный список, в котором каждый элемент — скаляр одного и того же типа.
|
|
Если допустить изменение длины списка n, то на основе последовательного списка можно получить структуры данных, не удовлетворяющие свойству постоянства. Такие структуры называются полустатическими. Наиболее известные примеры полустатических структур — стеки, очереди и деки. Они характеризуются ограниченным доступом.
Стек — такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка. Применяются и другие названия стека — магазин и очередь, функционирующая по принципу LIFO (Last In — Firs1 Out — «последним пришел—первым исключается»).
Важнейшие операции доступа к стеку — включение элементов и исключение элементов — осуществляются с вершины стека, причем в каждый момент для исключения доступен элемент, находящийся на вершине стека. Вершина стека адресуется с помощью специального указателя. Для включения нового элемента в стек указатель сначала перемещается «вверх» на длину слота, или ячейки, а затем по значению указателя в стек помещается информация о новом элементе. При исключении элемента из стека сначала прочитывается информация об исключаемом элементе по значению указателя, а затем указатель смещается «вниз» на один слот. Стек считается пустым, если указатель смещен «вниз» на длину одной ячейки относительно конца стека. Используется также такая схема, в которой указатель адресует первую свободную ячейку стека.
|
|
Другие операции над стеком, кроме включения и исключения элементов, — очистка стека и проверка объема стека (т. е. проверка числа элементов в стеке).
Для хранения стека в памяти машины отводится сплошная область памяти, достаточно большая, чтобы в ней можно было поместить некоторое максимальное число элементов. Граничные адреса этой области являются параметрами физической структуры стека. Если в процессе заполнения стека указатель, перемещаясь «вверх», выходит за границу первоначально отведенной области памяти, то происходит переполнение стека, в результате чего становится невозможным включение в стек нового элемента. При отсутствии переполнения некоторая часть области памяти, отведенной для стека, свободна для включения новых элементов. Таким образом, хотя длина стека может изменяться в процессе его использования, эти изменения не должны выходить за пределы фиксированного участка памяти. Поэтому стек — полустатическая структура данных.
Физическая структура стека дополняется обычно дескриптором, в котором содержатся кроме указателя имя стека, границы физической структуры в памяти, а также описание элемента.
Очередь — такой последовательный список с переменной длиной, включение элементов в который происходит с одной стороны, а исключение элементов — с другой стороны списка, она функционирует по принципу FIFO (Fist In — Fist Out, т. е. «первым пришел — первым исключается»). Та сторона очереди, с которой осуществляется добавление элементов, называется хвостом, или концом, очереди, другая — головой. Для индикации хвоста и головы организуются два указателя.
Основные операции над очередью — включение элемента и исключение элемента. При включении новый элемент заносится в слот, адресуемый указателем хвоста очереди, после чего этот указатель должен быть «передвинут» к следующему (пустому) слоту. При исключении из очереди извлекается элемент, адресуемый указателем головы очереди, и после этого указатель перемещается к следующему слоту. Возможны и другие операции над очередью, например, проверка текущей длины и очистка.
В процессе включения элементов неизбежно наступит состояние переполнения очереди, т.е. выход указателя хвоста очереди за пределы отведенного для слотов участка памяти. Такой недостаток можно устранить, если после достижения указателем слота с максимальным адресом переводить этот указатель на слот с начальным адресом, если он пуст. Организованная таким образом очередь называется кольцевой
Особым типом списка является дек. Дек (от англ. deque — double — ended queue, т. е. очередь с двумя концами) — это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частные случаи дека — дек с ограниченным входом и дек с ограниченным выходом.
Логическая и физическая структуры дека аналогичны логической и физической структурам обычной очереди. Однако применительно к деку целесообразно вместо хвоста и головы говорить о левом конце и правом конце. Важнейшие операции над деком, как и над простой очередью, — включение и исключение элементов. Эти операции представляют собой обобщения и развитие операций включения и исключения элементов, применяемых к очереди. Одним из параметров операций доступа к нему должен быть признак того конца (левого или правого), с которого должна выполняться соответствующая операция.