java - 如何从链表中创建堆栈？

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

这样它会更安全一些，并返回Characters 而不是Objects- 并且Characters可以隐式转换为char:)

Answer 2

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

Answer 3

LinkedList确实更有效，因为Stack它依赖于同步方法Vector。在单线程应用程序中，使用后者意味着付出同步代价而没有任何好处。即使在多线程应用程序中，您也可能希望对同步进行更多控制。

这是一个可能的基于 LinkedList 的解决方案。请注意使用组合而不是继承。这将为您提供一个行为良好的堆栈，不能通过使用与列表相关的方法来滥用。

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

LinkedList 提供了比堆栈更多的操作。

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

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

Answer 5

这是示例：堆栈实现。希望能帮助到你。

它是用 C# 完成的，但你明白了