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

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

Начальное формирование стека

    Опишем предикат, который позволяет последовательно вводить элементы в стек. Пусть 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 - новый стек.

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




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