#include <stack> class NurbSurfac<

NurbSurface { /* mumble */ };

объекты. Например:

stack< NurbSurface* > surf Stack;

К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом.

Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа

[ Civil && ( War Rights )

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

Абстракция очереди реализует метод доступа FIFO (first in, first out - первым вошел, первым вышел ): объекты добавляются в конец очереди, а извлекаются из начала. Стандартная библиотека предоставляет две разновидности этого метода: очередь FIFO, или простая очередь, и очередь с приоритетами, которая позволяет сопоставлять элементе! с их приоритетами. Текущий элемент помещается не в конец такой очереди, а перед элементами с более низким приоритетом. Программист, определяющий такую структуру, задает способ вычисления приоритетов. В реальной жизни подобное можно увидеть, скажем, при регистрации багажа в аэропорту. Как правило, пассажиры, чей рейс через 15 минут, передвигаются в начало очереди, чтобы не опоздать на самолет. Примером из практики программирования служит планировщик операционной системы, определяющий последовательность выполнения процессов.

Для использования queue и priority queue необходимо включить заголовочный файл:

#include <queue>

Полный набор операций с контейнерами queue и priority queue приведен в таблице

6.6.

Таблица 6.6. Операции с queue и priority queue

stack< int, list<int> > intStack;

Элементы, добавляем1е в стек, копируются в реализующий его контейнер. Это может приводить к потере эффективности для больших или сложных объектов, особенно если мы только читаем элементы. В таком случае удобнее определить стек указателей на

Элементы priority queue отсортированы в порядке убывания приоритетов. По умолчанию упорядочение основывается на операции меньше , определенной над парами элементов. Конечно, можно явно задать указатель на функцию или объект-функцию, которая будет использоваться для сортировки. (В разделе 12.3 можно найти более подробное объяснение и иллюстрации использования такой очереди.)

6.18. Вернемся в классу iStack

У класса iStack, разработанного нами в разделе 4.15, два недостатка:

он поддерживает только тин int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;

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

Напомним определение нашего класса iStack:

#include <vector>

class iStack { public:

iStack( int capacity )

: stack( capacity ), top( 0 ) {};

bool pop( int svalue ); bool push( int value );

bool full();

bool empty(); void display();

int size() ;

private:

int top;

vector< int > stack;

Сначала реализуем динамическое выделение памяти. Тогда вместо использования индекса при вставке и удалении элемента нам нужно будет применять соответствующие функции-члены. Член top больше не нужен: функции push back() и pop back() автоматически работают в конце массива. Вот модифицированный текст функций pop()

bool iStack::pop( int stop value )

if ( empty() )

return false; top value = stack.back(); stack.pop back();

return

true;

bool iStack::push( int value )

if ( full() )

return false; stack.push back( value ); return true;

и push() :

Функции-члены empty(), size() и full() также нуждаются в изменении: в этой версии

inline bool iStack::empty() inline bool iStack::size()

inline bool iStack::full()

return stack.empty(); } return stack.size(); }

они теснее связаны с лежащим в основе стека вектором.

return stack.max size() == stack.size(); }

Надо немного изменить функцию-член display(), чтобы top больше не фигурировал в качестве граничного условия цикла.