|
qlntegers.push (10);
|
|
pop
|
Извлекает элемент из начала очереди, т.е. из ее первой позиции
|
front
|
qlntegers.pop ();
|
|
Возвращ ает ссылку на элемент в начале очереди
|
back
|
cout «
|
"Element at front: " «
|
qlntegers.front ();
|
Возвращ ает ссылку на элемент в конце очереди, т.е. на последний вставлен
|
|
ный элемент
|
|
|
cout «
|
"Element at back: " «
|
qlntegers.back ();
|
empty
|
Проверяет, не пуста ли очередь; возвращ ает значение типа bool
|
|
if (qlntegers.empty ())
|
|
size
|
cout « "The queue is empty!";
|
Возвращ ает количество элементов в очереди
|
size_t nNumElements = qlntegers.size ();
Класс q u eu e библиотеки STL не предоставляет такие функции, как b e g in () и en d (), хотя они доступны в большинстве контейнеров библиотеки STL, включая базовые классы d eq u e, v e c t o r и l i s t , лежащие в основе класса очереди. Это сделано намеренно, чтобы единственными допустимыми операциями очереди были те, которые согласуются с ее по веденческими характеристиками.
Вставка в конец и извлечение из начала очереди с использованием методов push () и pop ()
Для вставки элементов в очередь используется метод p u sh ():
qlntegers.push (5); // элемент вставляется в конец
Извлечение, напротив, осуществляется с начала при помощи метода pop ():
qlntegers.pop (); // извлечь элемент из начала
отличие от стека, у очереди элементы доступны для просмотра с обоих концов кон тейнера при помощи методов f r o n t () и b a c k ():
cout « "Element at front: " « qlntegers.front() « endl;
cout « "Element at back: " « qlntegers.back() « endl;
Вставка, извлечение и просмотр представлены в листинге 24.4.
ЛИСТИНГ 24.4. Вставка, извлечение и просмотр элементов очереди целых чисел
#include
#include
2 :
int main ()
{
using namespace std;
queue qlntegers;
8: cout « "Inserting {10, 5, -1, 20} into queue" « endl;
qlntegers.push (10);
qlntegers.push (5); // элемент вставляется в конец
qlntegers.push (-1);
qlntegers.push (20);
13:
14: cout « "Queue contains " << qlntegers.size () « " elements"
endl;
15:'
|
cout «
|
"Element at
|
front:
|
" «
|
qlntegers.front ()
|
« endl;
|
16:
|
cout «
|
"Element at
|
back:
|
" «
|
qlntegers.back() «
|
endl;
|
17:
|
|
|
|
|
|
|
while (qlntegers.size () != 0)
{
cout « "Deleting element: " « qlntegers.front () « endl;
qlntegers.pop (); // извлечь элемент из начала
22: }
23:
if (qlntegers.empty ()) // true, поскольку все элементы
были извлечены
cout « "The queue is now empty!" « endl;
26:
return 0;
}
Результат
Inserting {10, 5, -1, 20} into queue
Queue contains 4 elements
Element at front: 10
Element at back: 20
Deleting element: 10
Deleting element: 5
Deleting element: -1
Deleting element: 20
Анализ
В строках 9-12 элементы были добавлены в конец очереди q l n t e g e r s с использовани ем метода p u sh (). Методы f r o n t () и b a c k () используются для обращения к элементам в начальной и конечной позициях очереди, как показано в строках 15 и 16. Цикл w h ile в строках 18-22 отображает элементы из начала очереди, прежде чем извлечь их с использо ванием метода pop () в строке 21. Это продолжается до тех пор, пока очередь не опустеет. Вывод демонстрирует, что элементы были извлечены из очереди в том же порядке, в каком они были вставлены, поскольку вставляются они в конец очереди, а извлекаются с начала.
554 ЗАНЯТИЕ 24. Адаптивные контейнеры: стек и очередь
Использование класса priority_queue библиотеки STL
Для применения шаблон класса p r io r i ty _ q u e u e библиотеки STL требуется включить его заголовок . Приоритетная очередь (priority queue) отличается от очереди тем, что элемент с наивысшим значением (или значением, считающимся наивысшим согласно бинарному предикату) доступен в начале очереди, а работа с очередями ограничивается их началом.
Создание экземпляра приоритетной очереди
Ш аблон класса s t d : : p r i o r i t y _ q u e u e определен так:
template <
class типЭлемента,
class Контейнер = vector<Тип>,
class Сравнение = lessctypename Контейнер::value_type> > class priority_queue
Параметр типЭлемента задает тип объектов, которые будут храниться в приоритетной очереди. Второй параметр шаблона, Контейнер, — это класс контейнера, используемо го классом s t d : : p r io r i t y _ q u e u e для хранения данных, тогда как третий параметр по зволяет программисту определить бинарный предикат для выявления располагающегося вверху элемента. Если бинарный предикат не определен, класс p r i o r i t y _ q u e u e исполь зует заданный по умолчанию предикат s t d : :le s s < > , который сравнивает объекты, ис пользуя оператор o p e r a t o r s
Самый простой экземпляр приоритетной очереди целых чисел создается следующим образом:
std::priority_queue pqlntegers;
Если необходимо создать приоритетную очередь, содержащую элементы типа d o u b le в контейнере s t d : : deq u e, используйте следующий код:
priority_queue , greater > pqlntegers_lnverse;
Подобно стеку, экземпляр очереди может быть создан как копия другой очереди:
std::priority_queue pqCopy(pqlntegers) ;
Создание экземпляра класса p r i o r i t y _ q u e u e представлено в листинге 24.5.
И С Т И Н Г 2 4 .S . Создание экземпляра класса priority queue__________________________
Do'stlaringiz bilan baham: |
