为什么会使用 Stack<T> 而不是 List<T>？

Question

System.Collections.Generic 中的 List<T> 能够完成 Stack<T> 所能完成的所有功能，并且还有更多扩展功能 -- 它们是基于相同的底层数据结构。在什么情况下选择使用 Stack<T> 是正确的呢？

- Billy ONeal

---

当你想要使用堆栈时，可以认为 Stack<T> 更清晰地传达了意图。 - CodesInChaos

它们是两种不同的数据结构 - List 给你一个项目列表，而 Stack 给你一个FILO（先进后出）队列。 - Dave Zych

@Servy 我在 List<T> 中找不到 Pop() 和 Push()，这两个对于栈来说非常有用的操作。虽然可以模拟实现，但并不一定高效。 - Joachim Isaksson

@JoachimIsaksson 在列表中，只需添加到末尾并从末尾删除即可。这两个操作都是O(1)的，并且在现有API中得到支持。 - Servy

@JoachimIsaksson 它是摊销常数时间。 - CodesInChaos

Answer 1

如果你需要一个后进先出的集合，你会使用栈。列表允许你在任意索引处访问它的项。还有很多其他的区别，但我认为这是最基本的区别。

在你的评论之后更新：

我认为使用 Stack<T> 声明了你希望代码被使用的方式。计划未来总是好的，但如果你现在需要 Stack<T>，并且没有使用 List<T> 的强烈理由，那么我会选择 Stack<T>。

- Abe Miessler

---

@BillyONeal 如果你需要的是堆栈API中没有的东西，那么你就不符合逻辑地表示一个堆栈，最初就不应该使用它。 - Servy

我认为使用 Stack<T> 可以表明你希望这段代码如何被使用。虽然未来的计划总是好的，但如果你现在需要 Stack<T>，并且没有充分的理由使用 List<T>，那么我会选择 Stack<T>。 - Abe Miessler

另一方面，一开始使用List<T>可以让您在没有显著性能损失的情况下使用所有Stack<T>功能，并在以后决定重构时增加灵活性。总的来说，我同意您的观点，认为如果您决定要一个列表而不是堆栈，应该在需要做出决策时而不是一开始就做出决策，但我可以理解双方的立场。 - Jeremy Todd

@JeremyTodd 当下一个开发人员出现并不知道你的List列表在逻辑上是一个Stack，并尝试在末尾以外的位置添加/删除/读取时会发生什么？此外，如果您在逻辑上表示堆栈，则以后不需要随机访问，这就是重点。这种情况并不罕见；Stack是一种有用的逻辑数据结构。 - Servy

@JeremyTodd，虽然可以为List实现Stack.Pop()，但这会使代码更复杂。 另外，对于以后阅读该代码的人来说，这看起来可能有点奇怪，而且不够简洁。 - Abe Miessler

Answer 2

这是你的答案——当你需要强制约束正在使用的数据结构只能被视为堆栈时，你应该使用Stack。当然，你真正想要这样做的时候是有限的，但在适当的时候它是一个重要的工具。 例如，假设正在处理的数据如果不执行堆栈顺序就毫无意义，在这些情况下，如果你将数据作为列表提供，那么你将会自找麻烦。通过使用Stack（或Queue，或任何其他有序敏感的结构），你可以在代码中精确定义数据的使用方式。

- dimo414

---

即使底层数据结构不能像列表一样高效地操作，本文的重点在于这种情况永远不会发生。 - Servy

不，你误解了。Queue<T>与List<T>和Stack<T>非常不同。（我怀疑队列是双端队列实现，或者在实际队列周围加上填充实现摊销常数时间队列结构）但List<T>和Stack<T>是相同的数据结构，只是它们周围包裹的不同。这些是具体实现，而不是假设的list<t>和stack<t>接口。 - Billy ONeal

@BillyONeal Queue 实现为循环数组（根据 MSDN 页面上的内容），而不是双端队列。遗憾的是，.NET 在 System.Collection 中没有双端队列实现。 - Servy

在.NET中，几乎没有或者根本没有实现真正的“链表”结构，它只由引用其内容和下一个（或上一个）节点的节点组成。这是有很好的理由的；链表在内存堆上的性能非常差。数组是一块固定的连续内存块；而链表项可以散布在整个堆中。 - KeithS

@BillyONeal - 实际上，Servy所说的完全是MSDN所说的。队列使用固定大小的连续数组，当该数组已满并且必须添加另一个项时，对象将现有数组复制到两倍大小的数组中。这种基于数组的内部结构对于大多数System.Collections对象都是通用的；不同之处在于可用访问方式（以及在像HashSet/Dictionary这样的集合中，这些数组层数的数量）。 - KeithS

Answer 3

如果你想表达一个栈数据结构，那么你应该使用 Stack。如果你使用栈数据结构，它将在整个代码中传达程序员的意图，并防止不小心误用数据结构（无意中添加/删除/读取其他位置而不是一个端点）。

当然，Stack 可能只是一个接口，而不是具体实现。你可以让 List 实现这个接口。问题主要在于方便性。如果有人需要一个栈，他们需要选择一些具体的实现并记住（“哦，是的，List 是首选的栈实现”），而不仅仅是新建具体类型。

- Servy

Answer 4

这一切都与概念有关。列表是一个列表，栈是一个栈，它们执行两个非常不同的操作。它们唯一的共同点是它们的通用性和可变长度。

列表是一个可变长度的项目集合，其中任何元素都可以通过索引访问和重写，并且可以在任何此类索引处添加和删除项目。

堆栈是一个可变长度的元素集合，支持LIFO访问模型；只能访问堆栈顶部的元素，并且只能从该集合的“端点”添加和删除元素。从“顶部”三个元素的项目只能通过“弹出”上面的两个元素来显示它。

使用正确的工具来完成工作；当您需要对集合中的任何元素进行“随机”访问时，请使用列表。当您希望强制执行对数组中元素的更受限制的“仅顶部”访问时，请使用堆栈。当您想要强制执行FIFO“管道”时，请使用队列；项目从一端进入，从另一端出去。

- KeithS

---

在这个例子中，今天只需要LIFO访问。但明天可能需要非LIFO访问。考虑一个遍历文件系统并在内部以堆栈形式存储目录名称的类。堆栈很好，因为此代码仅需要LIFO访问。但是，明天想要添加一个ToString重载，该重载从开头到结尾打印堆栈的所有内容（例如，打印目录路径）。现在，要添加此重载，必须更改触及堆栈的所有代码。 - Billy ONeal

不行。开闭原则：从Stack派生，覆盖ToString()并使用Stack的Enumerable实现来生成所有元素所需的字符串表示形式。消费代码不必知道它是你的StringableStack而不是.NET的Stack在执行ToStringing。 - KeithS

Answer 5

除了概念上的不同，正如其他答案已经指出的那样，在 Stack 中也有不同的方法可以使您的代码更清晰（且更易于生活），而与使用 List 时相应的代码相比，这些方法非常实用。

例如，当使用 Stack 时，一个简单的对象池代码片段：

if (!pool.TryPop(out var obj))
{
    obj = new Foo();
}

而且同样可以写成一个List，同时保持操作O(1)：

Foo obj;
int count = pool.Count;
if (count > 0)
{
    obj = pool[--count];
    pool.RemoveAt(count);
}
else
{
    obj = new Foo();
}

- Jorge Galvão

Answer 6

System.Collections.Generic.Stack<T> 是一种后进先出（LIFO）的数据结构，也被称为堆栈。

尽管它的名称是这样的，但SCG.List<T> 不是所谓的[链接]列表抽象数据类型：实际上，它是一个可变长度数组。

两个非常不同的数据结构。

- Nicholas Carey

---

System.Collections.Generic.Stack是一个向量，就像System.Collections.Generic.List一样。（这是我在这个问题中要表达的全部意思） - Billy ONeal