Динамические структуры данных стеки
СОДЕРЖАНИЕ: Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.Динамические структуры данных: стеки
Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип последний пришёл — первый ушёл.
Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.
Стек можно организовать на базе любой структуры данных, где возможно хранение нескольких однотипных элементов и где можно реализовать определение стека: линейный массив, типизированный файл, однонаправленный или двунаправленный список. В нашем случае наиболее подходящим для реализации стека является однонаправленный список, причём в качестве вершины стека выберем начало этого списка.
Выделим типовые операции над стеком и его элементами:
добавление элемента в стек;
удаление элемента из стека;
проверка, пуст ли стек;
просмотр элемента в вершине стека без удаления;
очистка стека.
Реализуем эти операции, используя разработанный ранее модуль для однонаправленных списков (см. материал Динамические структуры данных: списки).
{ 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); NS := Nil; While Not Eof(T) Do Begin ReadLn(T, S); I := 1; While I = Length(S) Do Begin If S[I] In [0..9] Then Begin N := I; While S[I] In [0..9] Do I := I + 1; Val(Copy(S, N, I - N), X, Code); V_Stack(NS, X); End Else If S[I] In Znak Then Begin Iz_Stack(NS, X); Iz_Stack(NS, Y); Case S[I] Of + : X := X + Y; - : X := Y - X; * : X := X * Y; / : X := Y Div X End; V_Stack(NS, X) End; I := I + 1 End; Iz_Stack(NS, X); WriteLn(S, = , X); End End. |
/* C++, файл ST2.CPP */ #include STACK.CPP #include string.h #include stdio.h void main(void) { char S[255]; FILE *T; int I; BT X, Y; Zveno *NS; clrscr(); cout Введите имя файла: ; cin S; T=fopen(S, r); NS = NULL; while (!feof(T)) { fgets(S, 255, T); I = 0; while (I = strlen(S)-1) { if (S[I]=0S[I]=9) { X=0; while(S[I]=0S[I]=9) {X=X*10+(S[I]-0); I++;} NS=V_Stack(NS, X); } else if (S[I]==+||S[I]==-||S[I]==/||S[I]==*) { X=V_Vershine(NS); NS=Iz_Stack(NS); Y=V_Vershine(NS); NS=Iz_Stack(NS); switch (S[I]) { case + : X += Y; break; case - : X = Y - X; break; case * : X *= Y; break; case / : X = Y / X; break;} NS=V_Stack(NS, X); } I++; } X=V_Vershine(NS); NS=Iz_Stack(NS); cout S = X \n;} } |
Контрольные вопросы и задания
Какую структуру данных называют стеком?
На базе каких структур может быть организован стек?
Приведите из жизни примеры организации чего-либо по принципу стека.
Используя стек, напечатайте символы данной строки в обратном порядке.