快速包含和LIFO數據結構

Question

我正在尋找具有快速contains（）方法的java中的數據結構，但可能需要某種排序，因爲我需要能夠添加到它並從中取出，但我希望它像一個具有LIFO功能的堆棧。這可能嗎？我想到了一個HashSet，它具有快速的contains（），但它沒有保證的排序，而LinkedList有保證的排序，但是緩慢的包含了（）。

Answer 1

嗯，如果您需要執行LIFO堆棧操作，則無法對集合進行排序，因爲那樣會丟失向集合添加項目的順序。老實說，做你想做的最簡單的方法可能是創建兩個並行結構，比如創建一個Stack和一個HashMap。將它們包裹在一個更大的類中，添加和刪除總是添加/刪除的函數。然後你可以使用棧來做你的push和pops以及HashMap來做你的包含。

通常我不想創建重複的數據，但我看到做你想做的事情的唯一方法是有一個「索引堆棧」，這幾乎是我在這裏建議的方法。

我強調把它包裝在一個增加和刪除的類中，並確保所有添加和刪除都通過該類。否則，如果你有代碼添加/刪除遍佈全部，你創建的可能性，兩個結構將不同步。通過一個類強制它，你只需要調試一次該部分。

Answer 2

LinkedHashSet()讓你部分在那裏，但不幸的是並沒有揭示一個好方法去除LIFO。

我想你想要的是包裝LinkedList<T>（用於LIFO清除）和HashMap<T, Integer>（用於跟蹤基數）。那麼你會有這些方法（非常粗略）：

public class QuickCheckStack<T> { 

    private final Map<T, Integer> elementCardinality = new HashMap<T, Integer>; 
    private final Deque<T> stack = new LinkedList<T>(); 

    public void push(T element) { 
     Integer count = elementCardinality.get(element); 
     if (count == null) { 
      count = 0; 
     } 
     elementCardinality.put(element, count + 1); 
     stack.push(element); 
    } 

    public T pop() { 
     T element = stack.pop(); 
     elementCardinality.put(element, elementCardinality.get(element) - 1); 
     return element; 
    } 

    public boolean contains(T element) { 
     Integer count = elementCardinality.get(element); 
     return count != null && !count.equals(0); 
    } 
}