Структуры и алгоритмы обработки данных. Ключарев А.А - 42 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

42
Стек как динамическую структуру данных легко организовать на ос-
нове линейного списка. Поскольку работа всегда идет с заголовком сте-
ка, т. е. не требуется осуществлять просмотр элементов, удаление и
вставку элементов в середину или конец списка, то достаточно исполь-
зовать экономичный по памяти линейный однонаправленный список.
Для такого списка достаточно хранить указатель вершины стека, кото-
рый указывает на первый элемент списка. Если стек пуст, то списка не
существует и указатель принимает значение nil.
Поскольку стек, по своей сути, является структурой с изменяемым
количеством элементов, то основное внимание уделим динамической
реализации стека. Как уже говорилось выше, для такой реализации це-
лесообразно использовать линейный однонаправленный список. Поэтому
при описании динамической реализации будем использовать определе-
ния и операции, приведенные в 1.2.6.1.
Описание элементов стека аналогично описанию элементов линей-
ного однонаправленного списка, где DataType является типом эле-
ментов стека. Поэтому здесь приводить его не будем.
Основные операции, производимые со стеком:
– записать (положить в стек);
– прочитать (снять со стека);
– очистить стек;
– проверка пустоты стека.
Реализацию этих операций приведем в виде соответствующих про-
цедур, которые, в свою очередь, используют процедуры операций с ли-
нейным однонаправленным списком:
procedure PushStack(NewElem: TypeData;
var ptrStack: PElement);
{Запись элемента в стек (положить в стек)}
begin
InsFirst_LineSingleList(NewElem, ptrStack);
end;
procedure PopStack(var NewElem: TypeData,
ptrStack: PElement);
{Чтение элемента из стека (снять со стека)}
begin
if ptrStack <> nil then begin
NewElem := ptrStack^.Data;
Del_LineSingleList(ptrStack, ptrStack); {удаляем вершину}

Страницы