Skip to main content
 首页 » 编程设计

python之如何在不使用任何内置函数的情况下实现优先队列

2025年04月02日16cyq1162

这是我在这里的第一个问题,所以格式等可能有点不对劲。请不要恨我:)

所以我正在做的是创建一个名为 PQUEUE 的类,而我已经拥有的是:

class qNode: 
    def __init__(self,data=None, next=None): 
        self.data = data 
        self.next = next 
    def __str__(self): 
        return str(self.data) 
 
class PQUEUE: 
 
    def __init__(self): 
        self.head = None 
        self.foot = None 
 
    def push(self, value=None, priority=0): 
        #This is what I want to make 
 
    def pop(self): 
        x = self.front.data 
        self.front = self.front.next 
        return x 
 
    def clear(self): 
        self._head = None 
        self._foot = None 

我试图在不使用 heapq/queue 类或内置列表方法的情况下创建一个 Priority Queue 类(如您所见)。

我想不通的是我将如何继续这样做。我试过在网上到处搜索,但我看到到处都有人通过导入或使用内置列表方法来做到这一点。

帮助非常感谢! :)

请您参考如下方法:

这取决于你对优先级的定义是什么,但你将不得不自己迭代你的集合,寻找插入下一个节点的地方:

node = self.head 
while node.next and node.next.priority > priority: 
    node = node.next 
 
if node.next is None: 
    node.next = qNode(value=value, next=None, priority=priority) 
    self.foot = node.next 
else: 
    new_node = qNode(value=value, next=node.next, priority=priority) 
    node.next = new_node 

当然,您必须向您的qNode 添加一个priority,并且您可能必须准确调整要插入的位置,但这应该让您完成大部分工作。