Динамические структуры данных: стеки
Динамические
структуры данных: стеки
Стек — динамическая структура данных, представляющая из себя
упорядоченный набор элементов, в которой добавление новых элементов и удаление
существующих производится с одного конца, называемого вершиной стека.
По определению,
элементы извлекаются из стека в порядке, обратном их добавлению в эту
структуру, т.е. действует принцип "последний пришёл — первый ушёл".
Наиболее
наглядным примером организации стека служит детская пирамидка, где добавление и
снятие колец осуществляется как раз согласно определению стека.
Стек можно
организовать на базе любой структуры данных, где возможно хранение нескольких
однотипных элементов и где можно реализовать определение стека: линейный
массив, типизированный файл, однонаправленный или двунаправленный список. В
нашем случае наиболее подходящим для реализации стека является однонаправленный
список, причём в качестве вершины стека выберем начало этого списка.
Выделим типовые
операции над стеком и его элементами:
добавление
элемента в стек;
удаление
элемента из стека;
проверка, пуст
ли стек;
просмотр
элемента в вершине стека без удаления;
очистка стека.
Реализуем эти
операции, используя разработанный ранее модуль для однонаправленных списков
(см. материал "Динамические
структуры данных: списки
").
|
{
Turbo Pascal, файл
STACK.PAS }
Unit
Stack;
Interface
Uses Spisok;
Procedure V_Stack(Var Versh : U; X : BT);
Procedure Iz_Stack(Var Versh : U; Var X :
BT);
Function Pust(Versh : U) : Boolean;
Function V_Vershine(Versh : U) : BT;
Procedure Ochistka(Var Versh : U);
Implementation
Procedure V_Stack;
Begin
V_Nachalo(Versh, X)
End;
Procedure Iz_Stack;
Begin
Iz_Nachala(Versh, X)
End;
Function Pust;
Begin
Pust := Versh = Nil
End;
Function V_Vershine;
Begin
V_Vershine := Versh^.Inf
End;
Procedure Ochistka;
Begin
Spisok.Ochistka(Versh)
End;
Begin
End.
Похожие работы на - Динамические структуры данных: стеки
|