java - MergeQueue 在返回语句中缺少一些值

Question

我的方法的目的是将两个排序队列合并到一个更大的字母 A - Z 排序队列中并返回它。我的方法在大多数情况下都有效(即返回 A-Z)，但是有时它会丢失返回队列中的字母 Y、Z，有时只是丢失字母 Z 本身。这是我所说的一个例子。

q1 和 q2 的示例将在结果队列中产生缺失的 Y 和 Z。
q1 是包含 (A C E H I J K M N P Q R S T U X Y Z)
的字符串队列q2 是包含 (B D F G L O V W)
的字符串队列这两个参数传递到我的合并方法中。

 private static Queue<Comparable> merge(Queue<Comparable> q1, 
                                       Queue<Comparable> q2) {
    Queue<Comparable> q3 = new Queue<Comparable>();
    while (!q1.isEmpty() && !q2.isEmpty()){
        if (less(q1.peek(),q2.peek())) q3.enqueue(q1.dequeue());
        else if (less(q2.peek(),q1.peek())) q3.enqueue(q2.dequeue());
        if (q1.isEmpty() && !q2.isEmpty()) q3.enqueue(q2.dequeue());
        else if (q2.isEmpty() && !q1.isEmpty()) q3.enqueue(q1.dequeue());
    }
    //while (!q1.isEmpty()) q3.enqueue(q1.dequeue());
    //while (!q2.isEmpty()) q3.enqueue(q2.dequeue());
    return q3;
}

我尝试解决此问题的方法是

while (!q1.isEmpty()) q3.enqueue(q1.dequeue());
while (!q2.isEmpty()) q3.enqueue(q2.dequeue()); 

它解决了它!但是我对这个解决方案不满意。我通过使用 System.out.println 调试上面的代码来弄清楚这一点，看看在初始 while 循环后 q1 和 q2 是否为空。在这种情况下，初始 while 循环结束后 q1 不为空。所以我知道问题出在我的条件语句中的某个地方，但不确定在哪里。我的逻辑有点不对劲。

但我只是不明白这段代码上面的实现是如何忽略 Y 和 Z 的，因为循环一直持续到 q1 和 q2 都为空为止。如果 Y 和 Z 未排队到 q3 中，则意味着 q1 仍然保存 Y 和 Z 并且显然不为空，并且代码应继续运行，直到 q1 为空。

有人能解释一下 q1 是如何没有将 Y 和 Z 排入 q3 的吗？以及如何做我用比我找到的解决方案更有效的编码来修复它。

Answer 1

while 循环的条件是 !q1.isEmpty() && !q2.isEmpty() - 也就是说，两个队列都不能为空。这是一个正确的条件，因为循环体会查看两个队列，如果其中一个队列为空，循环体就会失败。但是，如果一个队列中的所有元素都小于另一个队列中的某些元素，则循环终止后这些元素将保留在另一个队列中。但是，由于每次迭代中仅从其中一个队列中删除一个元素，因此其中一个队列将先于另一个队列清空。因此，在循环之后，恰好一个队列将为空，而另一个队列则不会。

因此，最终的操作一定是将非空队列中的所有元素移动到结果队列中。由于您知道只有一个队列将为空，因此通过添加两个队列中的所有元素来完成此操作是安全的，因为添加空队列的所有元素将不会产生任何效果。