На этом шаге мы рассмотрим основные операции выполняемые над деком.
Добавление компоненты в начало
Добавить элемент в начало дека - это вставить его в самое начало так, чтобы он стал новой головой. Если 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 происходит следующим образом. Разделяем исходный список на голову и хвост, рекурсивно вызываем предикат удаления, взяв в качестве второго аргумента хвост списка.
Когда выполнится граничное условие, т.е. удалится элемент, нужно к оставшемуся хвосту дека добавить элементы, стоящие до удаленного компонента. Для этого из стека в обратном порядке последовательно извлекаются элементы, каждый из которых был головой первого списка. При этом только что извлеченный элемент становится первым также в третьем аргументе и т.д.
На следующем шаге мы приведем программу, реализующую основные операции над деком.
