Java - 排序堆棧

我需要一個排序堆棧。我的意思是，從堆棧中移除的元素必須是優先級最高的元素。堆棧尺寸變化很大（變得非常快）。我還需要搜索該堆棧中的元素。Java - 排序堆棧

Java是否爲此提供了一些很好的實現？你對此建議什麼類或算法？

我現在正在使用PriorityQueue，除了搜索外我認爲它是合理的，所以我想知道如果我可以使用更好的東西。

在此先感謝！

編輯：我也需要刪除元素！總結：我需要維護排序的堆棧/隊列，快速獲取具有更高優先級的元素，並儘快刪除元素

2010-04-22 msr

退房這個問題，http://stackoverflow.com/questions/2168803/how-to-sort-a-stack-using-only- push-pop-top-isempty-isfull – 2010-04-22 19:34:44

定義「搜索」 - 您是否需要檢查項目是否已經在「堆棧」中，您需要找到與某些給定條件最接近的匹配項目，或者您需要迭代通過所有元素來應用一些任意的搜索條件/過濾器？ – 2010-04-22 19:38:44

它的第一個選項：「需要找到最符合某些條件的匹配項目」在行動中，我需要刪除元素！所以，找到它並將其刪除！堆棧將是「巨大的」。平均10k到100k元素。 – msr 2010-04-22 21:33:45

Java不提供PriorityStack，但您可以輕鬆地通過包裝PriorityQueue類並提供push/pop方法來管理底層隊列。

來源

2010-04-22 19:39:13 Paolo

您始終可以使用兩種數據結構。優先隊列和地圖。第一個會讓你獲得最小/最大的物品，第二個會讓你快速搜索物品。你只需要將它們包裝在邏輯中以保持它們在水槽中（這不應該太難）

來源

2010-04-22 19:42:45

接收器還是同步？保持你的數據結構與髒盤子堵塞垃圾收集器與食物粒子......或者什麼...：D – Paolo 2010-04-22 19:51:01

@Paolo - 聽起來像這可能導致代碼味道。 – CPerkins 2010-04-22 19:58:46

TreeSet是一個有序集合。設置意味着沒有重複。 add（）添加一個項目，插入正確的排序位置。 pollLast（）移除並返回最後一個項目， pollFirst（）移除並返回第一個項目。

來源

2010-04-22 20:08:07 Mike

TreeSet可能是您的答案。 – 2010-04-22 20:31:59

您可以修改/重載您用來將數據推入堆棧的方法，以便將數據插入到正確或「已排序」的位置。否則，如果要使用某種基本數據類型的數組實現堆棧，則每次將數據推入堆棧時，都可以使用java.util程序包中的Arrays.sort(*Stack data array goes here*)。

來源

2011-11-22 15:15:30

import java.util.Stack;

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

}

來源

2015-07-30 04:34:17

Java - 排序堆棧

回答

相關問題