Нульсвязные списки

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

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

В языке Паскаль нет средств, позволяющих описывать переменные типа нульсвязных списков. Их приходится моделировать односвязными списками с запретом перемещения по указателям звеньев. Работа с нульсвязными списками выполняется, только используя специальные процедуры и функции. Обычно достаточно использовать функцию проверки, не пуст ли список, и две процедуры: добавления элемента к списку и выбора элемента из списка (с удалением выбираемого звена).

Рассмотрим варианты нульсвязных списков.

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

Формирование вершины стека можно произвести следующим образом:

Var

S:P1;

Begin

new(S);

. . .

Очередь – нульсвязный список с правилом обслуживания FIFO ( First In – First Out – первым пришел – первым ушел).

Для работы с очередью необходимы такие же процедуры, как и для стека. При создании пустой очереди указателям N и K присваивается значение nil. Процедурам добавления в очередь и выбора из очереди приходится передавать указатели на оба конца, так как при создании первого звена, его адрес необходимо занести в оба указателя, а при удалении последнего звена очереди, обоим указателям надо присвоить значение nil.

Дек – это нульсвязный список, в котором добавление и выбор элементов возможен с любого конца. Его можно рассматривать как двусторонний стек или двустороннюю очередь. Название (deque) расшифровывается как double-ended queue – очередь с двумя концами.

Проще всего дек моделировать двусвязным линейным списком, по которому запрещено перемещаться. Формально для него приходится составлять две процедуры добавления и две процедуры удаления элементов, находящихся на первом и втором концах дека. На практике процедуры добавления можно объединить в одну, используя дополнительный признак – к какому концу добавляется элемент. Хотя оба конца дека равноправны, для определенности одну сторону будем называть началом, обозначая указателем NK, а вторую – концом, с обозначением KN.