Элементы, добавляемые в стек, копируются в реализующий его контейнер. Это может приводить к потере эффективности для больших или сложных объектов, особенно если мы только читаем элементы. В таком случае удобнее определить стек указателей на объекты. Например:
#include stack
class NurbSurface { /* mumble */ };
stack NurbSurface* surf_Stack;
К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом.
Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа
Civil ( War || Rights )
Абстракция очереди реализует метод доступа FIFO (first in, first out – “первым вошел, первым вышел”): объекты добавляются в конец очереди, а извлекаются из начала. Стандартная библиотека предоставляет две разновидности этого метода: очередь FIFO, или простая очередь, и очередь с приоритетами, которая позволяет сопоставлять элементы с их приоритетами. Текущий элемент помещается не в конец такой очереди, а перед элементами с более низким приоритетом. Программист, определяющий такую структуру, задает способ вычисления приоритетов. В реальной жизни подобное можно увидеть, скажем, при регистрации багажа в аэропорту. Как правило, пассажиры, чей рейс через 15 минут, передвигаются в начало очереди, чтобы не опоздать на самолет. Примером из практики программирования служит планировщик операционной системы, определяющий последовательность выполнения процессов.
Для использования queue и priority_queue необходимо включить заголовочный файл:
#include queue
Полный набор операций с контейнерами queue и priority_queue приведен в таблице 6.6.
Таблица 6.6. Операции с queue и priority_queue
Операция | Действие |
empty() | Возвращает true, если очередь пуста, и false в противном случае |
size() | Возвращает количество элементов в очереди |
pop() | Удаляет первый элемент очереди, но не возвращает его значения. Для очереди с приоритетом первым является элемент с наивысшим приоритетом |
front() | Возвращает значение первого элемента очереди, но не удаляет его. Применимо только к простой очереди |
back() | Возвращает значение последнего элемента очереди, но не удаляет его. Применимо только к простой очереди |
top() | Возвращает значение элемента с наивысшим приоритетом, но не удаляет его. Применимо только к очереди с приоритетом |
push(item) | Помещает новый элемент в конец очереди. Для очереди с приоритетом позиция элемента определяется его приоритетом. |
Элементы priority_queue отсортированы в порядке убывания приоритетов. По умолчанию упорядочение основывается на операции “меньше”, определенной над парами элементов. Конечно, можно явно задать указатель на функцию или объект-функцию, которая будет использоваться для сортировки. (В разделе 12.3 можно найти более подробное объяснение и иллюстрации использования такой очереди.)
У класса iStack, разработанного нами в разделе 4.15, два недостатка:
* он поддерживает только тип int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;
* он имеет фиксированную длину. Это неудобно в двух отношениях: заполненный стек становится бесполезным, а в попытке избежать этого мы окажемся перед необходимостью отвести ему изначально слишком много памяти. Разумным выходом будет разрешить динамический рост стека. Это можно сделать, пользуясь тем, что лежащий в основе стека вектор способен динамически расти.
Напомним определение нашего класса iStack:
#include vector
class iStack {
public:
iStack( int capacity )
: _stack( capacity ), _top( 0 ) {};
bool pop( int value );
bool push( int value );
bool full();
