Определения типов

стек:;value type

О Тип элементов. О Эквивалент:

контейнер::value type стек::size type

О Беззнаковый целый тип для значений размера. О Эквивалент:

контейнер::size type

стек::container type Тип контейнера.

Операции

стек:;stack ()

О Конструктор но умолчанию. О Создает пустой стек.

explicit CTeK::stack (const Containers cont)

О Создает стек, инициализированный элементами cont. О Все элементы cont копируются в стек.

5ize type cre/<:;size О const

О Возвращает текущее количество элементов.

О Для проверки отсутствия элементов в стеке рекомендуется использовать функцию ennptyO, поскольку она может работать быстрее.

bool сгек: retnpty О const

О Проверяет, пуст ли стек.

О Эквивалент (по может работать быстрее):

стен: :size()==0 void cre/<::push (const value typee elem)

О Вставляет копию elem в стек, в результате чего она становится новым первым элементом.

value typee сгек::top О

const valuejiypeb, сгек: :top О const

О Обе формы возвращают верхний элемент стека, то есть элемент, который был вставлен последним (после всех остальных элементов стека).

О Перед вызовом необходимо убедиться в том, что стек содержит хотя бы один элемент (size()>0), иначе вызов приводит к непредсказуемым последствиям.

О Первая форма для неконстантных стеков возвращает ссылку, что позволяет модифицировать верхний элемент во время его нахождения в стеке. Хорошо это или нет - решайте сами.

void стен::рор ()

О Удаляет из стека верхгшй элемент, то есть элемент, который был вставлен последним (после всех остальных элементов стека).

О Функция НС имеет возвращаемого значения. Чтобы обработать значение верхнего элемента, следует предварительно вызвать функцию top().

О Перед вызовом необходимо убедиться в том, что стек содержит хотя бы один элемент (size()>0), иначе вызов приводит к непредсказуемым последствиям.

bool сравнение (const сгек& stackl. const стенЬ, stack2)

О Возвращает результат сравнения двух стеков одного типа. О Параметр сравнение - одна из следующих операций:

operator == operator != operator < operator > operator <= operator >=

О Два стека считаются равными, если они содержат одинаковое количество элементов, если элементы попарно совпадают и следуют в одинаковом порядке (то есть проверка двух соответствующих друг другу элементов на ргшенство всегда дает true).

О Отношение «меньше/больше» между контейнерами проверяется по лексикографическому критерию. Лексикографический критерий рассматривается при описании алгоритма (exicographica( connpare() на с. 356.

Пользовательская реализация стека

Стандартный класс stacko ставит на первое место не удобство и безопасность, а скорость работы. У автора на этот счет другое мнение, поэтому вашему вниманию предлагается нестандартная реализация стека. Она обладает двумя преимуществами:

О функция рор() возвращает верхний элемент;

О при пустом стеке функции рор() и top() генерируют исключения.

Кроме того, из реализации были исключены операции, лишние для рядового пользователя стеков (например, операции сравнения). Полученный класс стека приведен ниже.

cont/Stack.hpp

1 * ********************************************

* Stack,hpp

* - более удобный и безопасный класс стека

* *********************Sc************************************** j

#ifndef STACKJPP #define STACK HPP

finclude <deque> #include <exception>

template <class T> class Stack { protected:

std::deque<T> c: Контейнер дня хранения элементов

public:

/* Класс исключения, генерируемого функциями рорО и topO * при пустом стеке */

class ReadEmptyStack : public std::exception { public:

virtual const char* whatO const throwO { return "read empty stack":

Количество элементов

typename std::deque<T>::s1ze type sizeO const { return C.sizeC);

Проверка пустого стека bool empty С) const { return cemptyC):

Занесение элемента в стек void push (const T& elem) { c.push backCelem):

Извлечение элемента из стека с возвращением его значения Т pop С) {

if (C.emptyO) {

throw ReadEmptyStackC);