python - Python 3 中的 "Priority stack"(优先级队列和堆栈的混合)？

Question

我需要 Python 3 中的“优先级堆栈”数据结构(类似于优先级队列，但更像是像堆栈一样的 LIFE)。

我知道queue.PriorityQueue，但没有发现像queue.PriorityStack这样的东西。

Answer 1

最简单的方法是创建一个对象，其中包含要插入的实际数据以及每次插入时递增的序列号。所以你有一个看起来像这样的对象:

queueObject
    actual_data
    sequence_number
    priority

当您想要将某些内容插入优先级队列时，您可以使用新的序列号创建该对象。像这样的东西:

function insert(data, priority)
    obj = new queuedObject(data, priority, ++globalSequence)
    pq.insert(obj)

有了它和自定义比较器，您就可以使用标准的 Python heapq 对象。只需确保比较器比较优先级和序列号即可。

如果您愿意，可以使用时间戳代替序列号。无论哪种方式，假设您的比较器是正确的，这将确保具有相同优先级的项目按 LIFO 顺序出队。