Решение задачи с использованием стека. 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;

}