截斷Java堆棧

Question

我有一個在Java中定義的Stack<String>，用於通過工作流進行導航。

我想要做的是確保堆棧中的所有值都是唯一的：當轉換到「上一個」狀態時，我想從堆棧中移除所有的東西，在第一次出現之前的狀態疊加。

有沒有簡單的方法來做到這一點？

編輯：提供了更多信息。下面是一個堆棧的內容的例子：

[state2, state3, state2, state1, startState] 

我需要的能力，接受一個字符串，檢查堆棧，看看是否有它的多次出現，然後彈出元素，直到該「最底層」的發生串。 「截斷」可能是我想要做的不好描述......「彈出，直到我打到任意索引」可能更接近我所需要的。

Answer 1

考慮使用deque。以下鏈接解釋了爲什麼您應該使用堆棧。

Why should I use Deque over Stack?

Answer 2

Stack實現List（各種其他接口之間）。獲取最後一個元素的ListIterator，並向後移動它，直到找到新狀態的出現點，統計出沿途有多少元素，然後彈出很多元素。 （如果你沒有找到新的狀態，那麼當然你不會彈出任何東西，而是將新狀態推到堆棧上）。

這可能不是特別有效，但它肯定會奏效。如果你也希望它是有效的，你可能需要使用另一個數據結構（或者代替堆棧）。一種可能是使用Map（除堆棧外）跟蹤堆棧上的哪些狀態以及它們出現的索引，或至少一個Set來跟蹤堆棧上的哪些狀態（您然後就可以彈出狀態，直到找到你正在尋找的那個）。你會保持堆棧和地圖或平行設置。

或者，如果你是認真的：

「的流行，直到我打了一個任意指數」是可能接近我所需要的。

......那麼可以肯定，這將足夠了：

int numberToPop = stack.size() - arbitraryIndex - 1; 
while (numberToPop-- > 0) { 
    stack.pop(); 
} 

Answer 3

難道簡化你的整個代碼，如果你創建了自己的容器，它基本上是一組，這是一個堆棧？類似（不是完整的實現）：

public class StackSet<T> { 
    private final Set<T> set; 
    private final Deque<T> queue; 

    public StackSet(){ 
     set = new HashSet<>(); 
     queue = new ArrayDeque<>(); 
    } 

    public void push(T value){ 
     if(set.add(value)){ 
      queue.push(value); 
     } 
    } 

    public T pop(){ 
     return queue.pop(); 
    } 
} 

這應該保證沒有重複。

Answer 4

下面是一個使用Deque而不是Stack的截斷方法的示例。

import java.util.ArrayDeque; 
import java.util.Arrays; 
import java.util.Collection; 
import java.util.Deque; 

public class ExampleDeque 
{ 

    public static void main(String[] args)  
    { 
    Deque<String> deque = new ArrayDeque<String>(); 
    deque.offer("startState"); 
    deque.offer("state1"); 
    deque.offer("state2"); 
    deque.offer("state3"); 
    deque.offer("state2"); 

    System.out.println("Before"); 
    print(deque); 
    deque = truncate(deque, "state2"); 
    System.out.println("After"); 
    print(deque); 
    } 

    static Deque<String> truncate (Deque<String> deque, String value) 
    { 
    if(!deque.contains(value)) return deque; 

    String[] array = deque.toArray(new String[deque.size()]); 
    for(int i = 0; i < array.length; i++) 
    { 
     if(array[i] == value) 
     { 
     String[] truncated = Arrays.copyOfRange(array, 0, i + 1); 
     Collection<String> collection = Arrays.asList(truncated); 
     return new ArrayDeque<>(collection); 
     } 
    } 
    return null; 
    } 

    static void print(Deque<String> deque) 
    { 
    for(String s : deque) 
     System.out.println(s); 
    System.out.println(); 
    } 
}