Что такое стек приоритетов?
Стеки и очереди являются аналогичными абстрактными структурами данных контейнера.Их основное абстрактное отличие заключается в том, что в стеке реализован принцип LIFO («Последний пришел - первый вышел»), тогда как очередь представляет собой FIFO («Первый пришел - первый вышел»).
Приоритет является ортогональным порядку, в котором элементы удаляются.Приоритет означает, что элемент с более высоким приоритетом удаляется перед элементом с более низким приоритетом:
- В обоих случаях, если только один элемент имеет наивысший приоритет, это будет тот, который будет удален первым,
- Но если несколько элементов имеют одинаковый наивысший приоритет, стек приоритетов сначала удалит самый последний отправленный, а очередь приоритетов сначала удалит первый в очереди.
Есть ли в стандартной библиотеке C ++ стек приоритетов?
К сожалению, стандартный C ++ предоставляет только priority_queue.Это адаптер.
Нет priority_stack.Так что вам нужно реализовать свой собственный.
Гипотеза: Я думаю, что причина в том, что приоритетные стеки являются чем-то довольно экзотическим.Конечно, есть допустимые варианты использования, но большинство стеков использует итеративную реализацию некоторых рекурсивных алгоритмов, в которых приоритет не имеет смысла.
Быстрая реализация
Если вы не знаете, с чего начать, вот быстрая и грязная реализация:
template<class T>
class priority_stack {
vector<T> stack;
public:
bool empty() const { return stack.size()==0; }
void push(const T& x) {
stack.push_back(x);
for (int i=stack.size()-1; i!=0; i--)
if ( (stack[i]<stack[i-1])) // assuming priority is reflected in order of elements
swap (stack[i-1],stack[i]);
}
void pop() {
if (! empty() )
stack.resize(stack.size()-1);
}
T top() {
if (empty())
throw;
return stack[stack.size()-1];
}
};
Вы можете проверить это с помощью следующихструктура данных:
struct data {
int priority;
string message;
bool operator< (const data&a) const { // order by priority
return priority<a.priority;
}
};
Демоверсия онлайн покажет вам разницу:
Data to be pushed:(10,one) (10,two) (11,high) (12,very high) (10,three)
Priority queue (FIFO): (12,very high) (11,high) (10,one) (10,two) (10,three)
Priority stack (LIFO): (12,very high) (11,high) (10,three) (10,two) (10,one)
Примечание: если ваши элементы данных достаточнобольшой может быть более интересным основывать структуру на списке, а не на векторе, и вставлять отправленные данные в нужное место, минимизируя таким образом перестановки.