优先级列表 - 排队方法错误

Question

我想写一个 PriorityList 队列，其中所有元素都是一个订单的基础。就我而言，我想对 ElementType 类型的元素进行排序(可以是任何东西，为了测试，我使用了整数并根据它们的值对它们进行排序，从最高值开始，以最低值结束(

但是，我现在不知所措，在以下方法中发现了错误。代码运行，但未按预期工作。

让代码添加 3 3 4 或 3 4 5 效果很好。我得到 4 3 3 和 5 4 3，完全应该如此。但是，如果我给队列以下值：5 3 3 4 5 4，我得到：5 3 3;我期望 5 5 4 4 3 3;我认为这是可以理解的，出了什么问题，但是我不太了解指针来解决这个问题。

如果有人可以查看以下代码行并尝试找出问题所在以及如何解决它，我会非常高兴。如有必要，我可以在第二天早上提供更多信息。

public void enqueue(ElementType element) {
        ListNode elem = new ListNode ((ElementType)element);        
        if(head == null) {          
            head = elem;
            head.data = element;
            head.next = null;
            head.prev = null;
            tail = head;
        }
        else {  
            ListNode n = null;
            n = head;
            if(element.compareTo(head.data) > 0) {
                elem.prev = null;
                head.prev = elem; 
                elem.next = head;
                head.next = n.next; 
                head = elem;    return; 
            }
            int k = 0;  
            while(element.compareTo(n.data) <= 0 ) {
                k++;
                if(n.next !=null) {
                n = n.next; 
                 }
                else  {
                    elem.prev = n; 
                    n.next = elem;
                    tail = elem; 
                    elem.next = null;
                    return; }
            }   
            elem.prev = n.prev; 
            n.prev = elem; 
            elem.next = n; 
            } }

Answer 1

我相信

PriorityQueue可以取代您的大部分代码。查看JavaDocs。

优先级队列的元素根据其自然顺序进行排序，或者由队列构建时提供的比较器进行排序，具体取决于所使用的构造函数。

因此，如果ElementType实现了Comparable<ElementType>或者您提供了Comparator<ElementType>则应该一切就绪。

Answer 2

正如wasgren指出的那样，这段代码对于PriorityQueue来说是多余的。不过，也许您这样做是为了了解链表......

此代码不起作用，因为您在最后一个案例(倒数第二个右大括号之前的代码块(中没有正确链接elem。

尝试将其添加到该块的末尾，就在那些右大括号之前：

elem.prev.next = elem;

Answer 3

你为什么不直接使用 java 优先级队列，它将完成大部分工作，并且比你在这里拥有的非常优化