java - 快速包含和 LIFO 数据结构

Question

我正在寻找具有快速 contains() 方法的 java 中的数据结构，但可能需要某种排序，因为我需要能够添加到它并从中获取，但我希望它像一个 Stack具有后进先出功能。这可能吗？我想到了一个具有快速 contains() 但不保证排序的 HashSet，以及一个保证排序但慢速 contains() 的 LinkedList。

Answer 1

嗯，如果您需要进行 LIFO 堆栈操作，则无法对集合进行排序，因为这样您就失去了将项目添加到集合中的顺序。

坦率地说，做你想做的最简单的方法可能是创建两个并行结构，比如创建一个 Stack 和一个 HashMap。将它们包装在一个更大的类中，该类具有始终添加/删除两者的添加和删除功能。然后，您可以使用堆栈进行推送和弹出，并使用 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);
   }
}