92.Стеки adt-контейнеров шаблонов.

C++ Stack – это адаптер контейнера, предоставляющий функциональность стека, то есть структуру данных FILO (first-in, last-out). Конструкторы создают новый стек

empty истина, если в стеке нет элементов

pop удаляет верхний элемент стека

push добавляет элемент на вершину стека

size возвращает количество элементов в стеке

top возвращает ссылку на верхний элемент стека

Стек

Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции:

Push Добавить (положить) в конец стека новый элемент

Pop Извлечь из стека последний элемент

Back Узнать значение последнего элемента (не удаляя его)

Size Узнать количество элементов в стеке

Clear Очистить стек (удалить из него все элементы)

Хранить элементы стека мы будем в массиве. Для начала будем считать, что максимальное количество элементов в стеке не может превосходить константы MAX_SIZE, тогда для хранения элементов массива необходимо создать массив размера MAX_SIZE.

Объявим структуру данных типа stack.

const int MAX_SIZE=1000;

struct stack {

int m_size; // Количество элементов в стеке

int m_elems[MAX_SIZE]; // Массив для хранения элементов

stack(); // Конструктор

~stack(); // Деструктор

void push(int d); // Добавить в стек новый элемент

int pop(); // Удалить из стека последний элемент

// и вернуть его значение

int back(); // Вернуть значение последнего элемента

int size(); // Вернуть количество элементов в стеке

void clear(); // Очистить стек

};

Объявленная здесь структура данных stack реализует стек целых чисел. Поле структуры m_size хранит количество элементов в стеке в настоящее время, сами элементы хранятся в элементах массива m_elems с индексами 0..m_size-1. Элементы, добавленные позже, получают большие номера.