使用堆栈与仅使用双向链表相比有什么好处

Question

作为一项作业，我必须迭代而不是递归地实现快速排序。为此，我需要使用堆栈。在这种情况下使用堆栈与仅使用单链表或双向链表相比有什么好处？

Answer 1

Push 的时间复杂度为 O(1)，Pop 的时间复杂度为 O(1)，而 Inserting 的时间复杂度为 O(N)（最好的情况是添加到 head，O(1)），搜索的时间复杂度为 O(1)链表中的 O(N)。由于您需要同时执行添加和检索操作，因此使用 LinkedList

会更昂贵

Answer 2

简单的答案是表现力。正如评论中指出的那样，您可以使用链表实现堆栈。 "using a stack" 的好处是您不必担心实现的细节。也就是说，如果你只是使用链表，你会得到类似的东西：

// push onto the stack
newNode = createStackNode(myData);
newNode.Next = root;
root = newNode;

// pop from stack
poppedNode = root;
root = root.Next;
myData = poppedNode.data;

如果您使用现有的Stack数据结构，那么您不必担心压入和弹出的细节。您只需要写：

theStack.push(myData);

或

myData = theStack.pop();

要点是您知道 Stack 数据结构有效。而且很难调用 push 或 pop。 很容易搞砸向链表头部添加和删除内容的代码。

Answer 3

堆栈是一个接口，它定义了一组应该定义的操作，它可以通过多种方式实现，链表，双链表，数组等（如果你也可以使用队列想要，即使我不建议这样做）。这组操作的定义限制了数据结构的范围，允许为特定用例获得更好的性能。

一般从链表或数组中删除一个元素需要O(n)，因为你要删除的元素可能在任何位置，所以你必须先找到它。在堆栈中，使用相同的数据结构实现 pop 你可以实现 O(1) 因为你已经知道要删除的元素在哪里（如果是链表，它是头，如果是数组，它是最后一个元素).

使用堆栈与仅使用双向链表相比有什么好处

What is the benefit of using a stack versus just a doubly linked list

java

sorting

algorithm

stack

quicksort