我正在尝试创建一个队列,以避免元素在队列中存在太长时间。我正在使用链表。我想实现它的方式是,如果添加了更大的优先级,则推送支持的优先级将添加 0.4。我还需要为链表实现排序,但这已经有些意义了。我真的不明白我应该如何将这个 0.4 添加到已被取代的优先级中。
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self,):
self.head = Node()
def append(self, data):
new_node = Node(data)
current = self.head
while current.next is not None:
current = current.next
current.next = new_node
def __str__(self):
data = []
current = self.head
while current is not None:
data.append(current.data)
current = current.next
return "[%s]" %(', '.join(str(i) for i in data))
def __repr__(self):
return self.__str__()
def length(self):
current = self.head
total = 0
while current.next is not None:
total += 1
current = current.next
return total
def display(self):
elements = []
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
elements.append(current_node.data)
print("Elements ", elements)
def get(self, index):
if index >= self.length():
print("Error: Index is out of range!")
return None
current_index = 0
current_node = self.head
while True:
current_node = current_node.next
if current_index == index:
return current_node.data
current_index += 1
def remove(self):
current = self.head
if current is not None:
self.head = current.next
else:
print("Queue is empty!")
def main():
queue = LinkedList()
queue.append(5)
queue.append(2)
queue.display()
main()
我建议使用python的heapq而不是链表。因为您正在进行自定义比较,所以您可能希望使用自定义比较谓词实现类似 heapq 中描述的内容。
除了优先级之外,添加一个字段,其中包含将项目添加到堆中的时间。然后,您的实际优先级是分配的优先级和项目在堆中的时间长度的函数。例如,优先级可以是这样的:
elapsed_time = current_time - added_time;
real_priority = assigned_priority * elapsed_time;
您可能希望使乘数成为已用时间的一小部分。
另一种可能性是,如果您想确保某些内容在队列中的停留时间不会超过某个设定的时间。例如,如果要确保事情不会停留超过 5 分钟,则可以添加dequeue_time
字段。然后,您的比较将变为:
// assume items a and b are being compared
if (a.dequeue_time < current_time) {
if (b.dequeue_time < a.dequeue_time) {
// b sorts before a
}
else if (b.dequeue_time > a.dequeue_time) {
// return a sorts before b
}
else { // dequeue times are equal
return result of comparing a.priority to b.priority
}
}
else {
// here, return result of comparing a.priority and b.priority
}
Heapq 将比链表更有效率,尤其是当队列中的项目数量增加时。另外,它已经编写并已知有效。您所要做的就是提供比较功能。