Решение задачи с использованием стека. 2.9. Реализация процедуры и функции работы с бинарным деревом.
2.8. Решение задачи с использованием стека:
Стек – это линейный список, в котором добавление новых элементов и удаление существующих производится только с одного конца, называемого вершиной стека.
Стек часто называют структурой LIFO (сокращение LIFO означает Last In – First Out, т.е. последним пришел – первым вышел). Это сокращение помогает запомнить механизм работы стека.
Стек графически:
Рисунок 16.Стек.
При программировании на Паскале стек чаще всего реализуется в виде однонаправленного списка. Каждый элемент структуры содержит указатель на следующий. Однако, к этому виду списка, по определению, неприменима операция обхода элементов. Доступ возможен только к верхнему элементу структуры.
Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.
Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.
Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка.
Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, "нижний" элемент.
Пример.
Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов.
Program STACK;
uses Crt;
type
Alfa= String[10];
PComp= ^Comp;
Comp= Record
sD: Alfa;
pNext: PComp
end;
var
pTop: PComp;
sC: Alfa;
Procedure CreateStack(var pTop: PComp; var sC: Alfa);
begin
New(pTop);
pTop^.pNext:=NIL;
pTop^.sD:=sC
end;
Procedure AddComp(var pTop: PComp; var sC: Alfa);
var pAux: PComp;
begin
NEW(pAux);
pAux^.pNext:=pTop;
pTop:=pAux;
pTop^.sD:=sC
end;
Procedure DelComp(var pTop: PComp; var sC:ALFA);
begin
sC:=pTop^.sD;
pTop:=pTop^.pNext
end;
begin
Clrscr;
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
CreateStack(pTop,sC);
repeat
writeln(' ВВЕДИ СТРОКУ ');
readln(sC);
AddComp(pTop,sC)
until sC='END';
writeln('****** ВЫВОД РЕЗУЛЬТАТОВ ******');
repeat
DelComp(pTop,sC);
writeln(sC);
until pTop = NIL
end.
После решения примера и компилирования я получила результат:
Рисунок 17.Результат после компилирования .
Задача с использованием стека на С++:
#include <iostream>
struct stek
{
int value;
struct stek *next; // указатель на следующий элемент списка (стека)
};
void push(stek* &NEXT, const int VALUE)
{
stek *MyStack = new stek; // объявляем новую динамическую переменную типа stek
MyStack->value = VALUE; // записываем значение, которое помещается в стек
MyStack->next = NEXT; // связываем новый элемент стека с предыдущим
NEXT = MyStack; // новый элемент стека становится его вершиной
}
int pop(stek* &NEXT)
{
int temp = NEXT->value; // извлекаем в переменную temp значение в вершине стека
stek *MyStack = NEXT; // запоминаем указатель на вершину стека, чтобы затем
// освободить выделенную под него память
NEXT = NEXT->next; // вершиной становится предшествующий top элемент
delete MyStack; // освобождаем память, тем самым удалили вершину
std::cout<<temp; //Вывод текущего элемента на экран
return temp; // возвращаем значение, которое было в вершине
}
int main()
{
stek *p=0;
push(p,100); //Положили в стек 100
push(p,200); //Положили в стек 200
pop(p); //вывели на экран текущий элемент стека = 200
pop(p); //вывели на экран текущий элемент стека = 100
return 0;
}