How to restore the PriorityQueue to its initial state before the method call?

Two things need to be adjusted in your implementation. First, you should use a queue, rather than a stack, as your auxiliary data structure. The pushing items into a stack and then popping them back out will result in them being added back into your priority queue in reverse order. If they come out of the priority queue as 1, 2, 3, they’ll be added back to the priority queue as 3, 2, 1. This is because stacks are a LIFO (Last in, first out) data structure. You want to use a queue as your auxilary data structure because it is a FIFO (First in, first out) data structure, so it will preserve the same order.

Second, you only pull the first k elements out of the priorty queue. I would recommend draining the entire queue, so that you’re adding all of the elements back into the queue in the order they came out, rather than just some.

In other words, I would adjust your program as follows:

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: I changed the ‘element’ variable in your program from type int to Integer. It doesn’t matter for the correctness of your program, but it is a good habit to pay attention to auto-boxing. Generic types, like collections, use boxed integers. This is an object that stores the primitive integer. Assigning a boxed integer to something of type int requires that it be unboxed, i.e. turned back into an int primitive. This isn’t a big deal, except that you’re immediately adding this value back into a collection again. Since you’ve unboxed it into a primitive int, it needs to be boxed back into an Integer again, and that requires the system to create an object to store it in. Since all you’re doing with the value is taking it out of and putting it back into collections, it’s better to use an Integer value here, to avoid unboxing and boxing the value, since it isn’t really needed.