На этом шаге мы рассмотрим основные операции, выполняемые над очередью.
Формирование очереди
Опишем предикат, который позволяет вводить последовательно все элементы в очередь. Пусть vvod (N, L) - предикат, реализующий формирование очереди, N - количество элементов очереди, L - заполняемая очередь.
Предикат, выполняющий формирование очереди, выглядит следующим образом:
vvod (0, []). vvod (N, L):- readint (X), N1=N-1, vvod (N1, LL), L = [X|LL].
Первое предложение является граничным условием, т.е. оно говорит, что необходимо прекратить ввод в том случае, когда список пуст и количество элементов очереди равно нулю.
Второе предложение задает ввод головы списка: вводится очередной компонент очереди, количество элементов уменьшается на единицу и происходит рекурсивный вызов предиката, формирующего хвост списка.
Когда выполнится граничное условие, из стека последовательно извлекаются введенные элементы в обратном порядке и добавляются в конец очереди.
Добавление компоненты в конец очереди
Опишем предикат, который позволяет добавлять элементы в конец очереди. Пусть add_in_end (S1, S2, S3) - предикат, реализующий добавление компоненты, S1 - очередь, к которой добавляем, S2 - список, содержащий добавляемый элемент (перед вызовом предиката необходимо добавляемый элемент поместить в список S2), S3 - очередь с добавленным элементом.
Предикат, выполняющий добавление компоненты, выглядит следующим образом:
add_in_end ([], S, S).
add_in_end ([X|S1], S2, [X| S3]):-
add_in_end (S1, S2, S3).
Первое предложение является граничным условием: когда первый список пуст, то второй и третий списки представляют собой один и тот же список.
Если первый список не пуст, то его можно разделить на голову и хвост. Затем рекурсивно вызываем предикат добавления элемента, взяв в качестве первого аргумента хвост списка.
Когда выполнится граничное условие, в третьем списке будет содержаться только один элемент - тот, который нужно было добавить. Затем из стека в обратном порядке последовательно извлекаются элементы, каждый из которых был головой первого списка. При этом только что извлеченный элемент становится первым также в третьей очереди и т. д.
Удаление первой компоненты очереди
Удаление компоненты происходит очень просто: очередь разбивается на голову и хвост, а затем в качестве новой очереди берется только хвост.
Spisok = [_|S1].
Spisok - очередь из которой удаляем, S1 - новая очередь.
На следующем шаге мы начнем рассматривать программу, реализующую основные операции над очередью.
