Стек — динамическая структура данных, для которой выполняется правило: последним пришёл — первым ушёл. Таким образом, и дополнение новых данных, и извлечение их из стека всегда выполняется с одной стороны.
|
Вершина стека — эта та его часть, через которую ведётся вся работа. На вершину стека добавляются новые элементы, и с вершины стека снимаются (удаляются) элементы. В общем, стек — это односвязный список, для которого определены только две операции: добавление и удаление из начала списка. Примером стека может служить коробка, в которую сверху укладывают книги. Извлекать книги также приходится сверху. |
Рассмотрим основные и дополнительные действия со стеком. Для работы используем структуры Data и Stek:
struct Data
{
int a;
};
struct Stek
{
Data d;
Stek *next;
};
В программе определяем указатель на начало будущего стека:
Stek *u = NULL;
После этого можно начать работать со стеком.
1. Добавление в стек. Функцию добавления назовём Push() — по аналогии с командой ассемблера push, которая заносит целое число в программный стек.
void Push(Stek **u, Data &x)
{
Stek *t = new Stek; // Память под новый элемент
t->d.a = x.a; // Заполнение полей
t->next = *u; // Подключаем новый элемент к имеющимся
*u = t; // Перенастройка вершины
}
Обратиться к функции можно так:
Push(&u,x);
где x — объект типа Data.
2. Извлечение из стека. Здесь снова аналогия с ассемблером (команда pop выталкивает целое число из стека).
bool Pop(Stek **u, Data &x)
{
if(*u == NULL)
{
cout << "Pustoj stek" << endl;
return false;
}
Stek *t = *u;
x.a = t->d.a; // Получаем значения полей на вершине стека
*u = t->next; // Перенастройка вершины
delete t; // Удаление ненужного элемента
return true;
}
Пример вызова функции:
Data y;
if(Pop(&u, x))
{
y = x;
cout << "y=" << y.a << endl;
}
Дополнительные действия со стеком — распечатка стека (можно взять алгоритм для работы с односвязным списком) и чтение с вершины стека. Чтение напоминает извлечение, но при этом данные из стека не удаляются. Вот возможный вариант реализации:
bool Read(Stek **u, Data &x)
{
if(*u == NULL)
{
cout << "Pustoj stek" << endl;
return false;
}
Stek *t = *u;
x.a = t->d.a; // Заполнение полей
return true;
}
Использование функции Read() может быть аналогичным использованию Pop().
