Динамические структуры
данных: стеки
Стек
— динамическая структура данных, представляющая из себя упорядоченный набор
элементов, в которой добавление новых элементов и удаление существующих
производится с одного конца, называемого вершиной стека.
По определению, элементы
извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е.
действует принцип "последний пришёл — первый ушёл".
Наиболее наглядным
примером организации стека служит детская пирамидка, где добавление и снятие
колец осуществляется как раз согласно определению стека.
Стек можно организовать
на базе любой структуры данных, где возможно хранение нескольких однотипных
элементов и где можно реализовать определение стека: линейный массив,
типизированный файл, однонаправленный или двунаправленный список. В нашем случае
наиболее подходящим для реализации стека является однонаправленный список,
причём в качестве вершины стека выберем начало этого списка.
Выделим типовые операции
над стеком и его элементами:
добавление элемента в
стек;
удаление элемента из
стека;
проверка, пуст ли стек;
просмотр элемента в
вершине стека без удаления;
очистка стека.
Реализуем эти операции,
используя разработанный ранее модуль для однонаправленных списков (см. материал
"Динамические
структуры данных: списки ").
{ 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]>='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);
}
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";}
} |
Контрольные вопросы и
задания
Какую структуру данных
называют стеком?
На базе каких структур
может быть организован стек?
Приведите из жизни
примеры организации чего-либо по принципу стека.
Используя стек,
напечатайте символы данной строки в обратном порядке.
Список литературы
Для подготовки данной
работы были использованы материалы с сайта
http://www.comp-science.narod.ru/
|