Java - sorted stack

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 sugge开发者_StackOverflow社区st for this?

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

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

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.

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.

import java.util.Stack;

public class Q6_SortStack {

    /**
     * @param args
     * Write a program to sort a stack in ascending order. 
     * You should not make any assumptions about how the stack is implemented. 
     * The following are the only functions that should be used to 
     * write this program: push | pop | peek | isEmpty.
     */
    public static void main(String[] args) {
        int[] array = {2,5,10,3,11,7,13,8,9,4,1,6};
        Stack<Integer> s1 = new Stack<Integer>();
        //int[] array = {2,4,1,6};
        for(int i=0;i<array.length;i++){
            s1.push(array[i]);
        }
        //displayStack(s1);
        displayStack(sortStack(s1));
    }
    public static Stack<Integer> sortStack(Stack<Integer> s1){
        Stack<Integer> s2 = new Stack<Integer>();
        while(!s1.isEmpty()){
            int temp = s1.pop();
            while(!s2.isEmpty() && s2.peek()<temp){
                s1.push(s2.pop());
            }
            s2.push(temp);
        }
        return s2;
    }
    public static void displayStack(Stack<Integer> s){
        while(!s.isEmpty())
            System.out.print(s.pop()+"->");
        System.out.println("end");
    }
}

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)

You could modify/overload the method you use to push data into your stack such that it inserts into the correct or "sorted" position. Otherwise, if you're implementing the stack using an array of some primitive datatype, you could use Arrays.sort(*Stack data array goes here*) from the java.util package every time you push data into the stack.