На этом шаге мы приведем общее описание стека.
Класс stack() реализует стек, работающий по принципу "последним прибыл, первым обслужен" (LIFO). Функция push() вставляет в стек произвольное количество элементов (рисунок 1), а функция рор() удаляет элементы в порядке, обратном порядку их вставки.
Рис.1. Интерфейс стека
Чтобы использовать стек в программе, необходимо включить в нее заголовочный файл <stack>:
#include <stack>
В файле <stack> класс stack определяется следующим образом:
namespace std {
template <class Т,
class Container = deque<T> >
class stack;
}
Первый параметр шаблона определяет тип элементов. Необязательный второй параметр шаблона определяет контейнер, который будет использоваться внутренней реализацией для хранения элементов. По умолчанию это дек. Такой выбор объясняется тем, что деки (в отличие от векторов) освобождают память при удалении элементов и обходятся без копирования всех элементов при перераспределении памяти (рекомендации относительно того, когда следует выбирать тот или иной контейнер, приведены на 191 шаге).
Например, следующее объявление определяет стек с элементами типа int:
std::stack<int> st; // Стек целых чисел
Реализация стека просто отображает операции со стеком на соответствующие операции с используемым контейнером (рисунок 2).
Рис.2. Внутренний интерфейс стека
Допускается применение любого класса последовательного контейнера с поддержкой функций back(), push_back() и pop_back(). Например, элементы стека могут храниться в векторе или списке:
std::stack<int,std::vector<int> > st; // Стек целых чисел на базе вектора
На следующем шаге мы рассмотрим основной интерфейс стека.
