Очередь. Адаптеры контейнеров

S.pop();

Стек

Адаптеры контейнеров

Специализированные последовательные контейнеры - стек, очередь и очередь с приоритетами — не являются самостоятельными контейнерными классами, а реализованы на основе рассмотренных выше классов, поэтому они называются адаптерами контейнеров.

Шаблонный класс stack (заголовочный файл <stack>) определен как

template <class Т, class Container = deque<T> >

class stack { / *... */ };

где параметр Container задает класс-прототип. По умолчанию для стека прототипом является класс deque. Смысл такой реализации заключается в том, что специализированный класс просто переопределяет интерфейс класса-прототипа, ограничивая его только теми методами, которые нужны новому классу.

В табл. 5 показано, как сформирован интерфейс класса stack из методов класса-прототипа.

Таблица 5. Интерфейс класса stack

Методы класса stack Методы класса-прототипа

push() push_back()

pop() pop_back()

top() back()

empty () empty()

size() size()

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

Напоминаем, что метод рор() не возвращает удаленное значение. Чтобы считать значение на вершине стека, используется метод top().

Пример работы со стеком — программа вводит из файла числа и выводит их на экран в обратном порядке:

int main() {

ifstream in ("inpnum.txt");

stack<int> s;

int x;

while (in >> x) s.push(x);

while (!s.empty()) {

cout << s.top() << ' ';

}

return 0;

}

Объявление stack<int> s создает стек на базе двусторонней очереди (по умолчанию). Если по каким-то причинам нас это не устраивает и мы хотим создать стек на базе списка, то объявление будет выглядеть следующим образом:

stack<int, list<int> > s;

Шаблонный класс queue (заголовочный файл <queue>) является адаптером, который может быть реализован на основе двусторонней очереди (реализация по умолчанию) или списка.

Класс vector в качестве класса-прототипа не подходит, поскольку в нем нет выборки из начала контейнера.

Очередь использует для проталкивания данных один конец, а для выталкивания — другой.

В соответствии с этим ее интерфейс образуют методы, представленные в табл. 6.

Таблица 6. Интерфейс класса queue

Методы класса queueМетоды класса-прототипа

push() push_back()

pop() pop_front()

front() front ()

back() back()

empty() empty ()

size() size()

Очередь? с приоритетами

Шаблонный класс priority_queue (заголовочный файл <queue>) поддерживает такие же операции, как и класс queue, но реализация класса возможна либо на основе вектора (реализация по умолчанию), либо на основе списка.

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

Если очередь с приоритетами организуется для объектов класса, определенного программистом, то в этом классе должна быть определена операция <.

Пример работы с очередью с приоритетами:

int main() {

priority_queue <int> P;