Java - sorted stack

Question

Hello,

I need a sorted stack. 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 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, so Im wondering if I can use something better.

Thanks in advance!

Edit: I also need to remove elements! In summary: I need to maintain a sorted stack/queue, get the element with greater priority fast and also remove elements as fast as possible

Answer 1

Java doesn't provide a PriorityStack, but you could easily write one by wrapping the PriorityQueue class and providing the push/pop methods to manage the underlying queue.

Answer 2

You can always use two data structures. A priority queue and a map. The first will let you get the smallest/largest item, and the second will let you search items fast. You just need to wrap them in the logic to keep them in sink (which shouldn't be too hard)

Answer 3

TreeSet is a sorted set. Set means no duplicates though. add() adds an item, which is inserted in the correct sorted place. pollLast() removes and returns the last item, pollFirst() removes and returns the first item.