Стек

push{)

Рис. 10.1. Интерфейс стека

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

#1nclude <stack>

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

namespace std {

template <class Г,

class Container = deque<T> > class stack:

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

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

std::stack<1nt> st: Стек целых чисел

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

std;;stack<1nt.std:;vector<int> > st; Стек целых чисел на базе вектора

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

Основной интерфейс стеков состоит из функций push(), top() и рор():

О функция push() вставляет элемент в стек;

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

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

В исходной версии STL стек определялся в заголовочном файле <stack.li>. В предыдущих версиях STL единственным параметром шаблона был тип контейнера, а объявление стека с элементами типа mt выглядело так:

stack<deque<1nt> > st;

top()

Стек

Ьаск{)

Рис 10.2. Внутренний интерфейс стека

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

Если стандартный интерфейс stacko вас не устраивает, вы легко можете написать более удобный интерфейс. Пример приведен на с. 428.

Пример использования стека

пример использования класса stacko:

cont/stackl.cpp linclude <iostream> linclude <stack> using namespace std;

int mainO {

stack<1nt> St:

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

Извлечение и вывод двух элементов из стека

cout « st.topO « :

st.popC):

cout « St.topO « : st.popO:

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

Занесение двух новых элементов

st.push(4); st.push(5);

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

Извлечение и вывод оставшихся элементов while С!St.emptyO) {

cout « st.topO « :

St.popO:

cout « endl:

Результат выполнения программы: 3 2 4 77

Строение класса stack

Интерфейс класса stacko настолько компактен, что в нем можно легко разобраться, проанализировав типичную реализацию:

namespace std {

template <class Т. class Container = deque<T> > class stack { public:

typedef typename Container::value type value type:

typedef typename Container;:size type s1ze type;

typedef Container container type:

protected:

Container c: Контейнер public:

explicit stack(const Containers = ContainerO);

bool emptyO const { return c.emptyO; }

size type sizeO const { return csizeO; }

void pushCconst value type& x) { c.push back(x); }

void popO { c.pop back(): }

value type& topO { return c.back(); }

const value type& topO const { return c.backO; }

template <class T. class Container> bool operator==(const stack<T. Conta1ner>&.

const stack<T. Container>&); template <class T. class Container> bool operator< (const stack<T. Container>&.

const stack<T, Conta1ner>&); .. (Другие операторы сравнения)

Ниже приводятся более подробные описания членов класса stacko.