Q.front(b

(10) 20 (зо)

Позиция добавления

▼ с помощью Q.push(...)

-Q.backO

удаляется при QpopO

Рисунок 5.2. Очередь

В отличие от стека мы не можем представить очередь с помощью вектора, поскольку у вектора отсутствует операция pop Jront. Например, нельзя написать

queue<int, vector<int> > Q; Ошибка

Но если sector заменить на deque или list, такая строчка станет допустимой. Из следующей программы видно, что функции-члены push и pop работают так, как показано на рисунке 5.2.

queue.срр: Использование очереди; демонстрация

функций-членов push, pop, back и front.

#include <iostream> Iinclude <list> Iinclude <queue>

using namespace std;

int mainO

{ queue <int, list<int> > Q;

Интересно отметить, что функция-член top возвращает ссылку, которая позволяет нам изменить непустой стек, не прибегая к помощи операций push и pop. Например, вместо

S.popO ; S.push(15);

мы можем написать

S.topO = 15;

5.2. Очереди

Очередь (queue) является структурой данных, в которую можно добавлять элементы с одного конца, сзади, и удалять с другого конца, спереди. Мы можем узнать и изменить значения элементов спереди и сзади, как показано на рисунке 5.2.

Q.push(lO); Q.push(20); Q.push(30); cout << After pushing 10, 20 and 30:\n ; cout Q.front 0 = Q.front 0 endl; cout Q.backO = Q.backO endl; Q.pop();

cout After Q.pop():\n ;

cout Q.front 0 = Q.front 0 endl; return 0;

Вывод программы:

After pushing 10, 20 and 30: Q.front 0 = 10 Q.backO = 30 After Q.popO : Q.front 0 = 20

Любопытно отметить, что при использовании очередей из HP STL необходимо включить заголовок stack.h, а согласно проекту стандарта С++ нужно включать заголовок queue (см. таблицу в разделе 1.2). Также отличается количество параметров шаблона; мы не будем останавливаться на этом подробно, поскольку отличие то же, что и для стеков, о чем рассказано в предыдущем разделе.

Функции-члены empty и size класса queue аналогичны этим функциям для класса stack, так же как и операторы присваивания и сравнения. Сравнение начинается с передних элементов; если они равны, происходит сравнение следующих, и так далее.

5.3. Очереди с приоритетами

Очередь с приоритетами (priority queue) является структурой данных, из которой, если она не пуста, можно удалить только наибольший элемент. Как и для стеков, наиболее важными функциями-членами являются push, pop и top. Следующая программа использует эти функции:

prqueue.cpp: Очередь с приоритетами; программа

демонстрирует функции-члены push, pop, empty и top.

♦include <iostream> ♦include <vector> ♦include <functional> ♦include <queue>

using namespace std;

int mainO

{ priority queue <int, vector<int>, less<int> > P;

int х;

P.push(123); P.push(51); P.push(lOOO); P.push(17); while (!P.empty 0) { X = P.top();

cout Retrieved element: x endl;

P.popO ;

return 0;

В этой программе числа следуют в нисходящем порядке:

Retrieved element: 1000

Retrieved element: 123

Retrieved element: 51

Retrieved element: 17

Поскольку требуется проводить сравнение элементов, шаблон priority queue имеет третий параметр, как видно из определения очереди с приоритетами Р:

priority queue <int, vector<int>, less<int> > P;

Если требуется извлекать элементы в порядке возрастания, мы можем просто заменить less<int> на greater<int>. При работе с HP STL необходимо опустить первый аргумент шаблона, а также использовать заголовок stack.h вместо queue.

Чтобы продемонстрировать возможность задания любого правила упорядочения элементов, приведем еще один пример, в котором элементы будут извлекаться по порядку возрастания последних цифр в десятичном представлении целых чисел, хранящихся в очереди с приоритетами:

lastdig.cpp: Очередь с приоритетами; P.topO указывает

на элемент, последняя цифра которого не больше

последних цифр других элементов.

Iinclude <iostream> Iinclude <vector> Iinclude <queue> using namespace std;

class CompareLastDigits { public:

bool operator 0 (int x, int y) { return X % 10 > у % 10; )