Реализация стеков с помощью (односвязных) списков

Любой односвязный список может рассматриваться в виде стека. Однако список по сравнению со стеком в виде одномерного массива имеет преимущества, так как заранее не эадан его размер.

Стековые операции, применимые к спискам.

1). Чтобы добавить элемент в стек, надо в алгоритме вставки в начало списка заменить указатель Lst на указатель S (операция Push(S, x)).

P = GetNode

Info(P) = x

Ptr(P) = S

S = P

return

2). Проверка стека на пустоту (Empty (S))

if S = Nil

then print “Стек пуст”

Stop

endif

return

3) Выборка элемента из стека (POP(S))

Empty(S)

P = S

X = Info(P)

S = Ptr(P)

FreeNode(P)

return

12. Смысл и организация операций создания и удаления элемента динамической структуры. Понятие свободного списка и пула свободных эл-ов. Ути­лизация освободившихся элементов

Для более эффективного использования памяти компью­тера (для исключения мусора, то есть неиспользуемых эле­ментов) при работе его со списками создается свободный список, имеющий тот же формат полей, что и у функцио­нальных списков.

Если у функциональных списков разный формат, то надо создавать свободный список каждого функционального списка.

Количество элементов в свободном списке должно быть определено задачей, которую решает программа. Как правило, свободный список создается в памяти машины как стек, При этом создание (GetNode) нового элемента эквивалент» выборке элемента свободного стека, а операция FreeNode добавлению в свободный стек освободившегося элемента.

Пусть нам необходимо создать пустой список по тип; стека (рис. 3.6) с указателем начала списка - AVAIL. Разработаем процедуры, которые позволят нам создавать пусто элемент списка и освобождать элемент из списка.

AVAIL