«Олимпиадное программирование» - курс для начинающих

Язык программирования C++ содержит библиотеку STL (Standart template library, стандартная библиотека шаблонов). В библиотеку STL входят шаблоны для реализации стеков, деков, очередей для произвольных типов данных. Например, чтобы создать стек целых чисел необходимо использовать тип stack<int>, для создания стека строк – stack<string>, для создания стека объектов типа Person – stack<Person>.

Рассмотрим подробнее стеки, очереди, деки в STL. Описание шаблонов stack, queue, deque содержится в одноименных заголовочных файлах, то есть для использования этих структур необходимо подключить один из трех заголовочных файлов:

     #include<stack>
     #include<queue>
     #include<deque>

После этого можно создавать объекты на основе данных шаблонов:

     stack<int> S;      // Стек объектов типа int
     queue<double> Q;   // Очередь объектов типа double
     deque<string> D;   // Дек объектов типа string

После этого с объявленными объектами можно выполнять операции, например:

     S.push(3);      // Положить в стек S число 3
     Q.size();       // Узнать размер очереди Q
     D.pop_front();  // Удалить элемент из начала дека D

Рассмотрим более подробно список методов, присущих шаблонам stack<type>, queue<type>, deque<type> (typeT – это тип данных, хранящихся в соответствующей структуре).

Обратите внимание, что методы удаления pop, pop_front и pop_back в STL не возвращают значения. Кроме того, реализации стека, очереди, дека в STL не содержат проверок на возникновение ошибок, то есть за некорректную работу программы при вызове операций на пустом стеке отвечает сам пользователь.

Метод очистки clear существует только у дека.

Методы шаблона stack<type>

type top()           

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

void push(type)           

Добавить элемент в конец стека

void pop()           

Удалить верхний элемент из стека

int size()           

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

Методы шаблона queue<type>

type front()           

Узнать значение первого элемента в очереди

type back()           

Узнать значение последнего элемента в очереди

void push(T)           

Добавить элемент в конец очереди

void pop()           

Удалить первый элемент из очереди

int size()           

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

Методы шаблона deque<type>

T front()           

Узнать значение первого элемента в деке

T back()           

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

void push_front(T)           

Добавить элемент в начало дека

void push_back(T)           

Добавить элемент в конец дека

void pop_front()           

Удалить первый элемент из дека

void pop_back()           

Удалить последний элемент из дека

int size()           

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

void clear()           

Удаляет все элементы из дека