Java - отсортированный стек

Question

Мне нужен отсортированный стек. Я имею в виду, что элемент, удаленный из стека, должен иметь приоритет. Размер стека сильно варьируется (очень быстро увеличивается). Мне также нужно искать элементы в этом стеке.

Дает ли Java хорошую реализацию для этого? Какой класс или алгоритм вы предлагаете для этого?

Я сейчас использую PriorityQueue, который считаю разумным, за исключением поиска, поэтому мне интересно, могу ли я использовать что-то лучше.

Мне также нужно удалить элементы!

В итоге: мне нужно сохранить отсортированный стек / очередь, быстро получить элемент с более высоким приоритетом, а также удалить элементы как можно быстрее

Answer 1

TreeSet - это отсортированный набор. Установить означает, что нет дубликатов, хотя. add () добавляет элемент, который вставляется в правильном отсортированном месте. pollLast () удаляет и возвращает последний элемент, pollFirst () удаляет и возвращает первый элемент.

Answer 2

Java не предоставляет PriorityStack, но вы можете легко написать его, обернув класс PriorityQueue и предоставив методы push / pop для управления основной очередью.

Answer 3

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");
    }
}

Answer 4

Вы можете изменить / перегрузить метод, который вы используете, чтобы поместить данные в ваш стек так, чтобы они вставлялись в правильную или «отсортированную» позицию. В противном случае, если вы реализуете стек с использованием массива некоторого примитивного типа данных, вы можете использовать Arrays.sort(*Stack data array goes here*) из пакета java.util каждый раз, когда вы помещаете данные в стек.

Answer 5

Вы всегда можете использовать две структуры данных.Очередь приоритетов и карта.Первое позволит вам получить самый маленький / самый большой предмет, а второе позволит вам быстро искать предметы.Вам просто нужно обернуть их в логику, чтобы держать их в раковине (что не должно быть слишком жестким)