Шаг 10.
Динамические структуры данных в языке Prolog.
Основные операции над деком

    На этом шаге мы рассмотрим основные операции выполняемые над деком.

Добавление компоненты в начало

    Добавить элемент в начало дека - это вставить его в самое начало так, чтобы он стал новой головой. Если X - это новый элемент, который добавляют в список L, то предикат добавления элемента в список можно записать таким образом:


add_in_begin (X, L, [X|L]): - !.

Удаление элемента с конца

    Удаление элемента X из списка L можно определить в виде предиката delete_with_end (X, Y, Y1), где X - удаляемый элемент, Y - это список, из которого удаляется элемент, Y1 - новый дек.


delete_with_end (X, [X|L1], L1).
delete_with_end (X, [Z|Y], [Z|Y1]): -
     delete_with_end (X, Y, Y1).

    Если X является головой списка, тогда результатом удаления будет хвост этого списка.

    Если X находится в хвосте списка, тогда удаление X происходит следующим образом. Разделяем исходный список на голову и хвост, рекурсивно вызываем предикат удаления, взяв в качестве второго аргумента хвост списка.

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

    На следующем шаге мы приведем программу, реализующую основные операции над деком.




Предыдущий шаг Содержание Следующий шаг