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

Абстракция очереди реализует метод доступа 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 можно найти более подробное объяснение и иллюстрации использования такой очереди.)

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

У класса 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();

bool empty();

void display();

int size();

private:

int _top;

vector< int > _stack;

};

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

bool iStack::pop( int &top_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;

}

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

inline bool iStack::empty(){ return _stack.empty(); }

inline bool iStack::size() { return _stack.size(); }

inline bool iStack::full() {

return _stack.max_size() == _stack.size(); }

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

void iStack::display()

{

cout << "( " << size() << " )( bot: ";

for ( int ix=0; ix < size(); ++ix )

cout << _stack[ ix ] << " ";

cout << " stop )\n";

}

Наиболее существенным изменениям подвергнется конструктор iStack. Никаких действий от него теперь не требуется. Можно было бы определить пустой конструктор:

inline iStack::iStack() {}

Однако это не совсем приемлемо для пользователей нашего класса. До сих пор мы строго сохраняли интерфейс класса iStack, и если мы хотим сохранить его до конца, необходимо оставить для конструктора один необязательный параметр. Вот как будет выглядеть объявление конструктора с таким параметром типа int:

class iStack {

public:

iStack( int capacity = 0 );

// ...

};

Что делать с аргументом, если он задан? Используем его для указания емкости вектора:

inline iStack::iStack( int capacity )

{

if ( capacity )

_stack.reserve( capacity );

}

Превращение класса в шаблон еще проще, в частности потому, что лежащий в основе вектор сам является шаблоном. Вот модифицированное объявление:

#include <vector>

template <class elemType>

class Stack {

public:

Stack( int capacity=0 );

bool pop( elemType &value );

bool push( elemType value );

bool full();

bool empty();

void display();

int size();

private:

vector< elemType > _stack;

};

Для обеспечения совместимости с программами, использующими наш прежний класс iStack, определим следующий typedef:

typedef Stack<int> iStack;

Модификацию операторов класса мы оставим читателю для упражнения.

Упражнение 6.29

Модифицируйте функцию peek() (упражнение 4.23 из раздела 4.15) для шаблона класса Stack.

Упражнение 6.30

Модифицируйте операторы для шаблона класса Stack. Запустите тестовую программу из раздела 4.15 для новой реализации

Упражнение 6.31

По аналогии с классом List из раздела 5.11.1 инкапсулируйте наш шаблон класса Stack в пространство имен Primer_Third_Edition