Динамические структуры данных стеки
Динамические структуры данных: стеки
Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т. е. действует принцип "последний пришёл — первый ушёл".
Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.
или двунаправленный список. В нашем случае наиболее подходящим для реализации стека является однонаправленный список, причём в качестве вершины стека выберем начало этого списка.
Выделим типовые операции над стеком и его элементами:
проверка, пуст ли стек;
просмотр элемента в вершине стека без удаления;
очистка стека.
Реализуем эти операции, используя разработанный ранее модуль для однонаправленных списков (см. материал "Динамические структуры данных: списки").
{ Turbo Pascal, файл STACK. PAS }
Unit Stack;
Interface
Procedure V_Stack(Var Versh : U; X : BT);
Procedure Iz_Stack(Var Versh : U; Var X : BT);
Function Pust(Versh : U) : Boolean;
Implementation
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
End;
Begin
End.
|
/* C++, файл STACK. CPP */
"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)
{
}
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;
Const Znak = ['+', '-', '*', '/'];
Var S, S1 : String;
T : Text;
I, N : Byte;
X, Y : BT; Code : Integer;
Assign(T, S1); ReSet(T);
While Not Eof(T) Do
Begin
ReadLn(T, S); I := 1;
While I <= Length(S) Do
Begin
If S[I] In ['0'.. '9']
Then
N := I;
I := I + 1;
Val(Copy(S, N, I - N), X, Code);
V_Stack(NS, X);
End
Else
If S[I] In Znak
Iz_Stack(NS, Y);
Case S[I] Of
'+' : X := X + Y;
'-' : X := Y - X;
'/' : X := Y Div X
End;
V_Stack(NS, X)
End;
I := I + 1
Iz_Stack(NS, 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))
{
I = 0;
<= strlen(S)-1)
{
if (S[I]>='0'&&S[I]<='9')
{
X=0;
while(S[I]>='0'&&S[I]<='9') {X=X*10+(S[I]-'0'); I++;}
NS=V_Stack(NS, X);
}
{
X=V_Vershine(NS);
NS=Iz_Stack(NS);
Y=V_Vershine(NS);
NS=Iz_Stack(NS);
switch (S[I]) {
case '-' : X = Y - X; break;
case '*' : X *= Y; break;
NS=V_Stack(NS, X);
}
}
X=V_Vershine(NS);
NS=Iz_Stack(NS);
<< S << " => " << X << "\n";}
}
|
Контрольные вопросы и задания
Какую структуру данных называют стеком?
На базе каких структур может быть организован стек?
Приведите из жизни примеры организации чего-либо по принципу стека.
|