如何将 PriorityQueue 恢复到方法调用之前的初始状态？

我正在做一道练习题

这个问题基本上是你传入一个 PriorityQueue 和某个 k，并且你要返回该 PriorityQueue 中的第 k 个最小值。您还可以将 PriorityQueue 恢复到其初始状态，并可以使用一个堆栈或队列作为辅助数据结构。

我的更高层次的伪想法是，因为 PriorityQueue 已经充当了最小堆，从Java优先级队列 http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html，我真正要做的（我的算法）是：

1. 从 PriorityQueue 中删除 k 个元素

2. 将第 k 个最小值存储为局部变量

3. 将删除的 k 个元素推入堆栈（堆栈，以便我可以按相同顺序添加元素）

4. 从 Stack 中弹出所有元素并将它们重新添加回 PriorityQueue

5. 返回第 k 个最小值

这是完成所有这些操作的代码：

public int kthSmallest(PriorityQueue<Integer> pQ, int k) {
    if(k <= 0 || k > pQ.size()) {
           throw new IllegalArgumentException();
    } else {
         Stack<Integer> aux = new Stack<Integer>();
         int kThSmallest = -1;
         for(int c=0;c<k;c++){
               int element = pQ.remove();
               if(c == k-1) 
                   kThSmallest = element;
               aux.push(element);
          }
          while(!aux.isEmpty())
              pQ.add(aux.pop());
         return kThSmallest;
      }    
}

当我运行该程序时，我得到了所有正确的输出（就第 k 个最小而言），但我无法恢复 PriorityQueue 的状态。例如，当传入以下 PriorityQueue 时：

[-3, 9, 17, 22, 42, 81] with a k of 3

...我的算法产生了正确的结果 17，但它将 PriorityQueue 的状态更改为[-3, 17, 9, 81, 22, 42]，这是意料之外的。

我考虑过制作 PriorityQueue 的副本，但这违反了一个条件，“您可以使用一个堆栈或队列作为辅助数据结构”。

我怎样才能恢复 PriorityQueue 的状态？

在您的实施中需要调整两件事。首先，您应该使用队列而不是堆栈作为辅助数据结构。将项目推入堆栈然后将其弹出将导致它们被添加回优先级队列中以相反的顺序。如果它们从优先级队列中出来1, 2, 3，它们将被添加回优先级队列3, 2, 1。这是因为堆栈是一种 LIFO（后进先出）数据结构。您想要使用队列作为辅助数据结构，因为它是 FIFO（先进先出）数据结构，因此它将保留相同的顺序。

其次，您只从优先级队列中取出前 k 个元素。我建议排空整个队列，以便将所有元素按照它们出现的顺序添加回队列，而不仅仅是一些元素。

换句话说，我会把你的程序调整如下：

public int kthSmallest(PriorityQueue<Integer> pQ, int k) {
    if(k <= 0 || k > pQ.size()) {
           throw new IllegalArgumentException();
    } else {
         Queue<Integer> aux = new ArrayDeque<Integer>();
         int kThSmallest = -1;
         for(int c=0;c<pQ.size();c++){
               Integer element = pQ.remove();
               if(c == k-1) 
                   kThSmallest = element;
               aux.add(element);
          }
          while(!aux.isEmpty())
              pQ.add(aux.remove());
         return kThSmallest;
      }
}

Note:我更改了程序中的“元素”变量的类型int to Integer。程序的正确性并不重要，但注意自动装箱是一个好习惯。通用类型，如集合，使用boxed整数。这是一个存储原始整数的对象。将装箱整数分配给某种类型int要求将其拆箱，即变回原样int原始。这不是什么大问题，只是您会立即再次将此值添加回集合中。既然你已经把它拆箱成一个原始的int，它需要装回一个Integer再次，这需要系统创建一个对象来存储它。由于您对值所做的只是将其从集合中取出并放回集合中，因此最好使用Integervalue 在这里，以避免拆箱和装箱该值，因为它并不是真正需要的。