Реферат: Динамические структуры данных: стеки

Стек — динамическая структура данных, представляющая из себяупорядоченный набор элементов, в которой добавление новых элементов и удалениесуществующих производится с одного конца, называемого вершиной стека.

Поопределению, элементы извлекаются из стека в порядке, обратном их добавлению вэту структуру, т.е. действует принцип «последний пришёл — первыйушёл».

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

Стекможно организовать на базе любой структуры данных, где возможно хранениенескольких однотипных элементов и где можно реализовать определение стека:линейный массив, типизированный файл, однонаправленный или двунаправленныйсписок. В нашем случае наиболее подходящим для реализации стека являетсяоднонаправленный список, причём в качестве вершины стека выберем начало этогосписка.

Выделимтиповые операции над стеком и его элементами:

добавлениеэлемента в стек;

удалениеэлемента из стека;

проверка,пуст ли стек;

просмотрэлемента в вершине стека без удаления;

очисткастека.

Реализуемэти операции, используя разработанный ранее модуль для однонаправленных списков(см. материал «Динамические структуры данных: списки»).

{ 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.

/* C++, файл STACK.CPP */

#include «SPIS.CPP»

Zveno *V_Stack(Zveno *Versh, BT X)

{

return V_Nachalo(Versh, X);

}

Zveno *Iz_Stack(Zveno *Versh)

{

return Iz_Nachala(Versh);

}

int SPust(Zveno *Versh)

{

return !Versh;

}

BT V_Vershine(Zveno *Versh)

{

return Versh->Inf;

}

Zveno *Chistka(Zveno *Versh)

{

while (!Pust(Versh)) Versh=Iz_Stack(Versh);

return Versh;

}

Используяразработанные здесь библиотеки, решим задачу.

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

Алгоритмрешения. Выражение просматривается слева направо. Если встречается число, тоего значение (как целое) заносится в стек, а если встечается знак операции, тоиз стека извлекаются два последних элемента (это операнды данной операции), надними выполняется операция и ее результат записывается в стек. В конце в стекеостается только одно число — значение всего выражения.

{ Turbo Pascal, файл ST2.PAS }

Program St2;

Uses Spisok, Stack;

Const Znak = ['+', '-', '*', '/'];

Var S, S1: String;

T: Text;

I, N: Byte;

X, Y: BT; Code: Integer;

NS: U;

Begin

Write('Введите имя файла: '); ReadLn(S1);

Assign(T, S1); ReSet(T);