java - 为什么我的出列方法不适用于我的 treeMap PriceQueue？

Question

我有一个 PriceQueue 类，并且我已经通过了除 2 之外的所有测试。失败的是:

public void test05DeleteBackInOrder() {
    PriceQueue pq = new PriceQueue();
    pq.enqueue(p101);
    pq.enqueue(p202);
    pq.enqueue(p303);
    pq.enqueue(p404);
    pq.enqueue(p505);
    assertTrue(pq.delete(p303));
    assertTrue(pq.delete(p404));
    assertTrue(pq.delete(p505));
    assertEquals(p101, pq.dequeue());
    assertEquals(p202, pq.dequeue());

    pq = new PriceQueue();
    pq.enqueue(p101);
    pq.enqueue(p202);
    pq.enqueue(p303);
    pq.enqueue(p404);
    pq.enqueue(p505);
    assertTrue(pq.delete(p303));
    assertTrue(pq.delete(p404));
    assertTrue(pq.delete(p505));
    pq.enqueue(p303);
    pq.enqueue(p404);
    assertEquals(p101, pq.dequeue());
    assertEquals(p202, pq.dequeue());
    assertEquals(p303, pq.dequeue()); //This is where it is failing
    assertEquals(p404, pq.dequeue());
}

和

public void test05DeleteMiddleInOrder() {
    PriceQueue pq = new PriceQueue();
    pq.enqueue(p101);
    pq.enqueue(p202);
    pq.enqueue(p303);
    pq.enqueue(p404);
    pq.enqueue(p505);
    assertTrue(pq.delete(p202));
    assertTrue(pq.delete(p303));
    assertTrue(pq.delete(p404));
    assertEquals(p101, pq.dequeue());
    assertEquals(p505, pq.dequeue()); // This is where it fails

    pq = new PriceQueue();
    pq.enqueue(p101);
    pq.enqueue(p202);
    pq.enqueue(p303);
    pq.enqueue(p404);
    pq.enqueue(p505);
    assertTrue(pq.delete(p202));
    assertTrue(pq.delete(p303));
    assertTrue(pq.delete(p404));
    pq.enqueue(p202);
    pq.enqueue(p303);
    assertEquals(p101, pq.dequeue());
    assertEquals(p505, pq.dequeue());
    assertEquals(p202, pq.dequeue());
    assertEquals(p303, pq.dequeue());
}

这些是失败的，我不明白我在哪里错过了删除 prie 以便它正确出列。 这是我的代码:

public Price dequeue() {
    if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    Price price = first.price;
    first = first.next;
    n--;
    if (isEmpty()) last = null; 
    hold.remove(hold.lastKey());
    // to avoid loitering
    return price;
}


/**
 * Deletes a Price from the queue if it was present.
 * @param price the Price to be deleted.
 * @return {@code true} if the Price was deleted and {@code false} otherwise
 */
public boolean delete(Price price) {
    // TODO implelment me!!!
    // Make sure the running time is no worse than logrithmic!!!
    // You will want to use Java's TreeMap class to map Prices to the node
    // that precedes the Price in the queue
    //last node==special case
    //^^ requires resetting prev. to null, and val to next
    if (hold.containsKey(price)) {
        Node temp = hold.get(price);
        //if (price.equals(f))
        if (price.equals(first.price) && n >= 3) {
            first = first.next;
            n--;
            hold.remove(price);
            return true;
        }
        if (price.equals(first.price)) {
            first = first.next;
            hold.remove(price);
            n--;
            return true;
        }
        if (price.equals(last.price)) {
            temp.next = null;
            last = temp;
            n--;
            hold.remove(price);
            return true;
        }
        if (temp.next != (null)) {
            temp.next = temp.next.next;
            n--;
            hold.remove(price);
            return true;
        }

        return true;
    }
    else return false;

}

任何帮助，即使是提示或暗示，我们都会表示感谢。如果需要其他任何东西，请告诉我，我会提供，这些只是我的代码的一部分。 谢谢!

Answer 1

关于标准出队的一个快速答案是简单地返回remove的输出。

public Price dequeue(){
    return some_list.remove(0); //null if empty
}

Remove 返回它删除的元素，并自动将删除的项 1 后面的元素向左移动。如果该项目不存在(列表为空)，则它将返回 null。