如何从链表中创建堆栈？

-1

我试图创建一个堆栈来接收一个字符串并将每个字符串字符添加到它，但我被告知它会更高效地使用LinkedList。我将如何使用LinkedList来创建和操作堆栈？如何从链表中创建堆栈？

一个例子将非常感激！

来源

2013-01-21 Jay

更高效？为什么？ – Thilo

@Thilo因为当我做“Stack ”时，我不断收到错误。 – Jay

Re：不断收到错误？你怎么知道代码不工作时效率不高？ – Thilo

好了，问题是，你不使用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 :)

来源

2013-01-21 02:22:49 Jeff

真棒！非常感谢你！！ – Jay

你可能想摆脱你的第二个例子中的exmpStack。 –

@DavidConrad你是 - 谢谢 – Jeff

Java的LinkedList是一个双向链表，它具有高效的访问器来获取，添加和移除列表的末尾和头部的元素，因此您可以使用这些方法来模拟堆栈。

来源

2013-01-21 02:07:28 Thilo

你能提供一个例子吗？我不确定代码会是什么样子 – Jay

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(); } 
}

不过，如果你的筹码只是针对字符串中的字符作为你的问题建议，你可能想直接动态字符数组上模拟堆栈。我将把这些作为练习留给读者，或者我可以在将来的编辑中提供。

来源

2013-01-21 02:12:07

看起来我看起来像做家庭作业的高级答案。感谢-1，哥们！ –

那不是我给你的-1，我感谢你的帮助。 – Jay

现在你不是-1 :) – Jay

甲链表提供多个操作的堆叠的那个。

您使用堆栈压入和弹出你的字符串你的角色。但是，只能按照与插入字符串方式相反的顺序检索字符。所以你确定你是否想要这种行为。

链接列表允许您从头部/尾部添加/检索您的数据。

来源

2013-01-21 02:13:06 Hitman47

是的我意识到这一点，我对它没问题。 – Jay

我会争辩说，如果需要一个堆栈，那么应该提供一个堆栈来坚持封装的原则。要在堆栈中提供列表方法会引发错误，因为如果绕过常规合同，堆栈可能会受到影响。 –

@MihaiDanila你是对的。我误解了这个问题 – Hitman47

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

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

来源

2013-01-21 02:15:13 DarthVader

这使我困惑了一下......但我很欣赏这个输入！ – Jay

什么是混淆？这个想法是你总是首先添加T，然后总是从链表中删除第一个节点 – DarthVader

如何从链表中创建堆栈？

回答

相关问题