如何從鏈表中創建堆棧？

Question

我試圖創建一個堆棧來接收一個字符串並將每個字符串字符添加到它，但我被告知它會更高效地使用LinkedList。我將如何使用LinkedList來創建和操作堆棧？

一個例子將非常感激！

Answer 1

好了，問題是，你不使用First可言。請嘗試以下操作：

public class Example 
{ 
    private LinkedList aList = new LinkedList(); 

    public void push(char c) { 
     aList.addFirst(c); 
    } 
    public Object pop() { 
     return aList.removeFirst(); 
    } 
    public boolean empty() { 
     return aList.isEmpty(); 
    } 
    public static void main(String[] args) { 
     Stack exmpStack = new Stack(); 
     String ranString = "Dad"; 
     for (int i = 0; i < ranString.length(); i++) { 
      exmpStack.push(ranString.charAt(i)); 
     } 
     while (!exmpStack.empty()) { 
      System.out.print(exmpStack.pop()); 
     } 
    } 
} 

因爲你從來不使用First它總是null - 讓你的循環永遠不會運行在所有！完全不使用它，只需使用isEmpty()函數中的內部版本即可。

編輯：當然，你並不真的需要這些功能在所有 - 下面將正常工作：

public class Example 
{ 
    private LinkedList aList = new LinkedList(); 

    public static void main(String[] args) { 
     String ranString = "Dad"; 
     for (int i = 0; i < ranString.length(); i++) { 
      aList.push(ranString.charAt(i)); 
     } 
     while (!aList.isEmpty()) { 
      System.out.print(aList.pop()); 
     } 
    } 
} 

現在這還是有點不安全的 - 你可以走得更遠一步通過使用以下：

private LinkedList<Character> aList = new LinkedList<>(); 

這樣，它是一個更加安全，並返回Character！而非Objects - 和Characters可以隱式轉換爲char :)

Answer 2

Java的LinkedList是一個雙向鏈表，它具有高效的訪問器來獲取，添加和移除列表的末尾和頭部的元素，因此您可以使用這些方法來模擬堆棧。

Answer 3

LinkedList確實更高效，因爲Stack憑藉其對Vector的依賴而帶有同步方法。在單線程應用程序中，使用後者意味着付出同步價格並沒有任何好處。即使在多線程應用程序中，您也可能想要更多地控制同步。

這裏有一個基於LinkedList的解決方案。請注意使用組合而不是繼承。這會給你一個行爲良好的Stack，不能被List相關的方法濫用。

class MyStack<T> { 
    private List<T> list = new LinkedList<T>(); 

    public void push(T object) { list.add(0, object); } 

    public T pop(T object) { 
     if (isEmpty()) throw new NoSuchElementException(); 
     return list.remove(0); 
    } 

    public boolean isEmpty() { return list.isEmpty(); } 
} 

不過，如果你的籌碼只是針對字符串中的字符作爲你的問題建議，你可能想直接動態字符數組上模擬堆棧。我將把這些作爲練習留給讀者，或者我可以在將來的編輯中提供。

Answer 4

甲鏈表提供多個操作的堆疊的那個。

您使用堆棧壓入和彈出你的字符串你的角色。但是，只能按照與插入字符串方式相反的順序檢索字符。所以你確定你是否想要這種行爲。

鏈接列表允許您從頭部/尾部添加/檢索您的數據。

Answer 5

下面是示例：Stack implementation。希望能幫助到你。

它是用C＃做，但你的想法