I need a sorted stack/queue. I mean, the element removed from the stack must be the one with great priority. Stack dimension varies a lot (becomes bigger very fast). I need also to search and REMOVE elements in that stack.

Does Java give some good implementation for this? What class or algorithm do you suggest for this?

I'm using a PriorityQueue right now which I consider reasonable except for searching and removing, so Im wondering if I can use something better.

Thanks in advance!

The JDK implementation of PriorityQueue is backed by an array and hence ad-hoc deletions tend to be expensive (multiple invocations of System.arrayCopy etc). You can try your hand at writing a Linked list backed priority queue or use ConcurrentLinkedQueue though the added cost of synchronization might not be acceptable in your scenario. In any case, profiling is your friend here.