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
Наиболее существенным изменениям подвергнется конструктор iStack. Никаких действий
от него теперь не требуется. Можно было бы определить пустой конструктор:
inline iStack::iStack() {}
Однако это не совсем приемлемо для пользователей нашего класса. До сих пор мы строго сохраняли интерфейс класса iStack, и если мы хотим сохранить его до конца, необходимо оставить для конструктора один необязательный параметр. Вот как будет выглядеть объявление конструктора с таким параметром типа int:
class iStack {
public:
iStack( int capacity = 0 );
// ...
};
Что делать с аргументом, если он задан? Используем его для указания емкости вектора:
inline iStack::iStack( int capacity )
{
if ( capacity )
_stack.reserve( capacity );
}
Превращение класса в шаблон еще проще, в частности потому, что лежащий в основе вектор сам является шаблоном. Вот модифицированное объявление:
#include
template
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 _stack;
};
Для обеспечения совместимости с программами, использующими наш прежний класс iStack, определим следующий typedef: