C++ 中的优先级堆栈

Question

C++ 标准库提供了一个具有 priority_queue 的优先级队列。但它是否也提供 优先级堆栈 ？我寻找 priority_stack 但没有找到任何东西。

Answer 1

在c++中，标准模板库（STL）提供了一个priority_queue。参见示例 priority_queue。 STL 不提供 priority_stack 容器。

Answer 2

在常规队列或堆栈中，元素的移除顺序取决于插入顺序（队列顺序相同，堆栈顺序相反）。

在优先级队列中，顺序不取决于插入的顺序，而是取决于分配给每个元素的一些自定义"priority"。优先级队列首先给出具有最高优先级的元素。

例如：一个优先级队列(A 1) (B 3) (C 2)会按照B C A.

的顺序给出元素

不清楚你所说的"priority stack"是什么意思，但是如果栈只是一个移除顺序相反的队列，那么"priority stack"的自然解释是一个优先级队列，其中的顺序移除是相反的，即首先给出优先级最低的元素。但这与 优先级队列 相同，其中优先级被颠倒（通常只是否定它们）：

示例：一个"priority stack"(A 1) (B 3) (C 2)，它会给出顺序A C B，与优先级队列相同(A -1) (B -3) (C -2).

Answer 3

什么是优先堆栈？

Stacks and queues都是类似的抽象容器数据结构。它们的主要抽象区别在于堆栈实现了 LIFO 原则（后进先出），而队列是 FIFO（先进先出）。

优先级与删除项目的顺序正交。优先级表示优先级较高的项目在优先级较低的项目之前被删除：

在这两种情况下，如果只有一个元素具有最高优先级，它将是第一个被删除的元素。
但如果多个元素具有相同的最高优先级，则优先级堆栈将首先删除最新推送的元素，而 priority queue 将首先删除第一个入队的元素。

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;  
    } 
};

online demo 会告诉你区别：

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)

注意：如果您的数据元素非常大，将结构基于列表而不是向量可能更有趣，并将推送的数据插入正确的位置，从而最大限度地减少交换。

C++ 中的优先级堆栈

Priority stack in C++

c++

heap

queue

stack

data-structures

什么是优先堆栈？

C++标准库中有优先级栈吗？

快速实施