-1 
from myNode import *
from tasks import *

class PriorityQueue():
    __slots__ = ( 'front', 'back', 'size' )

def mkPriorityQueue():
    queue = PriorityQueue()
    queue.front = NONE_NODE
    queue.back = NONE_NODE
    queue.size = 0
    return queue

def insert(queue, element):
    newnode = mkNode(element, NONE_NODE)
    if emptyQueue(queue):
        #if the queue was empty, the new node is now both the first and last one
        queue.front = newnode
        queue.back = newnode
    elif frontMax(queue).priority > newnode.data.priority:
        #if the new node has a higher priority than the first, insert at front
        newnode.next = queue.front #old first is now second node
        queue.front = newnode
    else:
        #the node has a lower priority than the first
        #find the next node with a lower priority, insert newnode before that
        currentnode = queue.front
        while not currentnode.next == NONE_NODE:
            #traverse nodes until we find a lower priority or until the end
            if currentnode.next.data.priority < newnode.data.priority:
                break
            currentnode = currentnode.next
        #insert newnode between currentnode and currentnode.next
        newnode.next = currentnode.next
        currentnode.next = newnode
        #if newnode.next is now NODE_NONE, we're at the end so change backMin
        if newnode.next == NONE_NODE:
            queue.back = newnode

    queue.size += 1

def removeMax(queue):
    """Remove the front element from the queue (returns None)"""
    if emptyQueue(queue):
        raise IndexError("Cannot dequeue an empty queue")
    queue.front = queue.front.next
    if emptyQueue(queue):
        queue.back = NONE_NODE
    queue.size -= 1

def frontMax(queue):
    """Access and return the first element in the queue without removing it"""
    if emptyQueue(queue):
        raise IndexError("front on empty queue")
    return queue.front.data

def backMin(queue):
    """Access and return the last element in the queue without removing it"""
    if emptyQueue(queue):
        raise IndexError("back on empty queue")
    return queue.back.data

def emptyQueue(queue):
    """Is the queue empty?"""
return queue.front == NONE_NODE

我这样做对吗？以下是我要解决的问题。我已经添加了我所做的所有功能。

使用优先级规则插入（在插入函数下）（每个任务具有从 10（最高优先级）到 1（最低优先级）的整数优先级。如果两个任务具有相同的优先级，则顺序应基于它们的顺序插入优先级队列（较早的第一个）。

4

1 回答 1

0

首先，您的else语句中有一个语法错误，它不采用测试表达式。除此之外，您的逻辑已关闭，因为它不会在正确的节点结构中维护insert- 当您这样做时queue.firstMax = newnode，您基本上会删除当前firstMax元素，因为您不再有对它的引用；newnode.next在这种情况下，您需要将旧的第一个元素分配给。此外，如果新任务的优先级是<=当前第一个，您需要遍历队列以找到新节点保持顺序的正确位置 - 它应该位于优先级较低的第一个元素之前。（在优化的实现中，您将存储按优先级分隔的节点，或者至少保留对每个优先级的最后一个节点的引用，以加快插入速度，但我想这超出了本练习的范围。）

这是一个insert应该正确执行的实现：

def insert(queue, element):
    newnode = mkNode(element, NONE_NODE)
    if emptyQueue(queue):
        #if the queue was empty, the new node is now both the first and last one
        queue.frontMax = newnode
        queue.backMin = newnode
    elif frontMax(queue).priority > newnode.data.priority:
        #if the new node has a higher priority than the first, insert at front
        newnode.next = queue.frontMax #old first is now second node
        queue.frontMax = newnode
    else:
        #the node has a lower priority than the first
        #find the next node with a lower priority, insert newnode before that
        currentnode = queue.frontMax
        while not currentnode.next == NODE_NONE:
            #traverse nodes until we find a lower priority or until the end
            if currentnode.next.data.priority < newnode.data.priority:
                break
            currentnode = currentnode.next
        #insert newnode between currentnode and currentnode.next
        newnode.next = currentnodenode.next
        currentnode.next = newnode
        #if newnode.next is now NODE_NONE, we're at the end so change backMin
        if newnode.next == NODE_NONE:
            queue.backMin = newnode

    queue.size += 1
于 2013-11-02T22:29:28.413 回答