Java - 满足谓词的第一个元素的位置

Question

我正在编写一个有序队列。在顶部有高优先级的元素，从最旧的到最新排序。对于中间的一段中等优先级元素和底部的低优先级元素也是如此。

当我想要对新元素进行排序时，我通常可以引用列表的最后一个元素。如果最后一个元素具有更高或相同的优先级，我的新元素将放置在所有元素之后。

现在，在最后一个元素的优先级低于新元素的情况下，我必须找到一种方法来迭代列表并找到适用谓词“优先级低于新元素”的第一个元素。然后我的新元素将位于该位置。

我使用compareTo 来比较两个元素。

我是一个完全的初学者，我很难找到解决该问题的方法。

非常感谢每一个帮助。

提前谢谢

我尝试过类似的方法:

public Queue<T> queue;

public OrderedQueue() {
    queue = new LinkedList<T>();
}

public void enqueue(T newitem) {
    int sss;
    if (isEmpty()) {
        ((LinkedList<T>) queue).add(newitem);
    }
    else if (newitem instanceof BulkParcel) {
        ((LinkedList<T>) queue).addLast(newitem);
    }
    else if (newitem instanceof StandardParcel || newitem instanceof PriorityParcel) {
            if (newitem.compareTo(((LinkedList<T>) queue).getLast()) == 0) {
                ((LinkedList<T>) queue).addLast(newitem);
            }
            else if (newitem.compareTo(((LinkedList<T>) queue).getLast()) < 0) {
                ((LinkedList<T>) queue).addLast(newitem);
            }
            else
                for (Iterator<T> it = queue.iterator(); it.hasNext();) {
                sss = newitem.compareTo(it.next());
                ((LinkedList<T>) queue).add((((LinkedList<T>) queue).indexOf(sss==-1)), newitem);
                }
    }
}

我能够完成我想要的事情。 这是我的新代码，供所有仍然感兴趣的人使用。

public void enqueue(T newitem) {
    int pos = -1;
    int compVal = 2;
    if (isEmpty()) {
        ((LinkedList<T>) queue).add(newitem);
    }
    else if (newitem.compareTo(((LinkedList<T>) queue).getLast()) == 0 
            || newitem.compareTo(((LinkedList<T>) queue).getLast()) < 0) {
            ((LinkedList<T>) queue).addLast(newitem);
    }
    else {
            for (Iterator<T> it = queue.iterator(); it.hasNext() && compVal != 1;) {
                compVal = newitem.compareTo(it.next());
                pos = pos + 1;
            }
        ((LinkedList<T>) queue).add(pos, newitem);
    }

}

我有一个自己编写的方法“compareTo”，对于a.compareTo(b);，如果a小于b(这里是优先级)，则返回-1，如果相等则返回0，如果a大于b则返回1。

感谢您的帮助和详细解答! :)

Answer 1

您正在查看插入排序。几乎可以肯定，您的教科书中对此进行了描述...尽管您已经有了这个想法。

<小时/>

Queue 表示特定的事物；它用于将元素放入并让队列决定将它们放在哪里。 (例如在列表的末尾)。由于您想在特定位置插入，因此您需要 List 。如果您不想重复，则需要 OrderedSet 。将字段声明为最合适的字段并避免强制转换。

在任何情况下，您都应该注意确保您使用的图书馆馆藏不会违背您的教师设定的学习目标。

根据讲师对您的要求，您也许可以使用其中之一并只需几行代码即可完成。或者它们可能都被禁止，你必须自己破解它。找出来!

<小时/>

我有一些建议可以让您更轻松地理解自己的代码。例如，采用这一行:

if (newitem.compareTo(((LinkedList<T>) queue).getLast()) == 0) {

与

相同

if (lastItemIsEqualTo(newItem)) {

如果您添加以下辅助方法:

private boolean lastItemIsEqualTo(T newItem) {
     return newItem.compareTo(((LinkedList<T>) queue).getLast()) == 0;
}

继续努力，您最终可能会得到:

        if (lastItemIsEqualTo(newItem)) {
            stuff...
        }
        else if (lastItemIsLessThan(newItem) {
            stuff...
        }
        else for (Iterator<T> it = queue.iterator(); it.hasNext();) {
            otherStuff...
        }

这相当于:

        if (lastItemIsLessThanOrEqualTo(newItem)) {
            stuff...
        }
        else for (Iterator<T> it = queue.iterator(); it.hasNext();) {
            otherStuff...
        }

但您也可以说出您真正想通过该 if 语句完成什么:

        if (entireListComesBefore(newItem)) {
            stuff...
        }
        else for (Iterator<T> it = queue.iterator(); it.hasNext();) {
            otherStuff...
        }

<小时/>

StandardParcel 与 BulkParcel。有必要上两个类吗？例如，如果 BulkParcel 与仅包含单个项目的 StandardParcel 相同，则您可以只使用 Parcel，但具有如下所示的内容:

public boolean isABulkParcel() {
    return parcel.size() > 1;
}

并且具有对两者通用的算法。那么你就不需要instanceof。 instanceof 很少有没有更好的解决方案。

<小时/>

sss = newitem.compareTo(it.next());
queue.add(queue.indexOf(sss==-1), newitem);

sss 毫无意义。这里有一个逻辑错误，如果你的变量名称更有意义，你很快就会发现它。看:

boolean newItemGoesBeforeNextItem = newitem.compareTo(it.next()) == -1;
queue.add(queue.indexOf(newItemGoesBeforeNextItem), newitem);

现在你看到最后一行的问题了吗？这是一个 boolean 值，而不是数字索引。它会自动转换为对象 Boolean(注意大写)。因此它尝试在列表中搜索该 boolean 对象，但从未找到它。它基本上是这样做的:

queue.indexOf(new Boolean(sss == 1))

这确实是一件大事。如果看不懂，就花点时间仔细看一下。