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