Т elein(c.back()); c.pop back(): return elem;

Получение значения верхнего злемента Т& top О {

if (C.emptyO) {

throw ReadEmptyStackO;

return C.backO;

lendif /* STACK HPP */

При использовсшии этого класса стека предыдущий пример можно записать в следующем виде:

cont/stack2.cpp linclude <iostream>

#1nclude "Stack.hpp" Использование нестандартного класса стека using namespace std;

int mainO {

try {

Stack<int> st;

Занесение трех элементов в стек st.push(l) st.push(2) st.push(3)

Извлечение и вывод двух элементов из стека cout « St.popO « ; cout « St.popO « :

Модификация верхнего элемента St.topO = 77;

Занесение двух новых элементов st.push(4): st.push(5):

Извлечение одного эпемента без обработки St.popO:

/* Извлечение и вывод трех элементов * - ОШИБКА: одного элемента не хватает

cout « St.popO « ; cout « St.popO « endl; cout « St.popO « endl:

catch (const exceptions e) {

cerr « "EXCEPTION: " « e.whatO « endl:

При последнем вызове pop() нгшеренно допущена ошибка. В отличие от стандартного класса стека с неопределенным поведением наш класс генерирует исключение. Результат выполнения программы выглядит так:

3 2 4 77

EXCEPTION: read empty stack

Очереди

Класс queue о реализует очередь, работающую по принципу «первым поступил, первым обслужен» (FIFO). Функция push() заносит элементы в очередь (рис. 10.3), а функция рор() удаляет элементы в порядке их вставки. Следовательно, очередь может рассматриваться как классический буфер данных.

Ьаск()

frontO

Рис. 10.3. Интерфейс очереди

Чтобы использовать очередь в программе, необходимо включить заголовочный файл <queue>:

finclude <queue>

В файле <queue> класс queue определяется следующим образом:

namespace std {

template <class Т.

class Container = deque<T> > class queue;

Первый параметр щаблона определяет тип элементов. Необязательный второй параметр щаблона определяет контейнер, который будет использоваться внутренней реализацией для хранения элементов. По умолчанию это дек.

Например, следующее объявление определяет очередь со строковыми элементами :

std::queue<stcl::string> buffer: Строковая очередь

Реализация очереди просто отображает операции с очередью на соответствующие операции с используемым контейнером (рис. 10.4). Допускается применение любого класса последователъного контейнера с поддержкой функций front(), back(), push back() и pop front(). Например, элементы очереди могут храниться в списке:

std::queue<std:;str1ng.std::list<std:;string> > buffer:

backO

frontO

push{)

backO Очередь front()

push back()

i pop-frontO

popO

Рис. 10.4. Внутренний интерфейс очереди

Основной интерфейс

Основной интерфейс очередей состоит из функций push(}, front(), back() и рор(): О функция push() вставляет элемент в очередь;

О функция front() возвращает следующий элемент очереди (тот, который был вставлен раньще других);

О функция Ьаск() возвращает последний элемент очереди (тот, который был вставлен позже других);

О функция рор() удаляет элемент из очереди.

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

В предыдущих версиях STL едипственпым параметром шаблона был тип контейнера, а объявление очереди с эле.ментами типа string выглядело так:

queue<deque<string> > buffer;