为什么 C# 中的 Stack<T> class 允许 ElementAt(index) 而它是一个 ADT？

Question

Stack 是一种抽象数据类型 (ADT)，它应该有一个密封的操作列表，例如 Push()、Pop()、Peek() 等，以执行后进先出（后进先出）原则。

但它有 ElementAt(index) 允许我访问堆栈中的任何元素。根据我的理解，Stack 对不在表面的元素的可见性应该较低。不是吗？

Answer 1

ElementAt() 是通过 Linq 的 Enumerable.ElementAt() 提供的，而不是通过 Stack<T> 接口提供的。

这是可行的，因为 Stack<T> 实现了 IEnumerable<T>，而这正是实现 ElementAt() 所需要的，因为它所做的只是遍历通过 IEnumerable<T> 提供的所有元素直到访问了 N 个。

对于 Stack<T> 这是一个 O(N) 操作。如果您将 ElementAt() 与 List<T> 一起使用，那么内部优化会将其转换为 O(1) 操作。

至于为什么 Stack<T> 实现 IEnumerable<T> - 只有一位设计师能真正回答这个问题。因为它是一个非变异操作，所以它并没有真正违反堆栈的任何基本原则。我会猜测它是为了方便而提供的。

正如 /u/Damien_The_Unbeliever 在他的回答中指出的那样，代码可以在没有 IEnumerable 接口的情况下确定第 N 个元素，方法是将 N 个元素弹出到另一个堆栈，然后以相反的顺序将它们全部推回，从而使原始堆栈保持不变.

美中不足的是 Microsoft 没有记录 Stack 的 IEnumerable return 其元素的顺序。您可以检查源代码以查看它确实 return 后进先出顺序中的元素 - 但这根本没有记录。

的答案中对此进行了讨论。

无论如何，为您所说的抽象堆栈定义的 ADT 接口在哪里？我认为对此没有明确的答案。严格来说，你可以说一个堆栈只有 Push() 和 Pop()。然而大多数实现还提供 Count.

作为the article about Stack on Wikipedia states:

In many implementations, a stack has more operations than "push" and "pop". An example is "top of stack", or "peek", which observes the top-most element without removing it from the stack.

Since this can be done with a "pop" and a "push" with the same data, it is not essential. An underflow condition can occur in the "stack top" operation if the stack is empty, the same as "pop". Also, implementations often have a function which just returns whether the stack is empty.

所以你的问题的基本答案是：

库设计者决定在只有变异方法 Push() 和 Pop().[=32 之外添加一些非变异的便捷方法=]

Answer 2

Stack is an Abstract Data Type (ADT)

Stack 的一般概念确实如此，但 System.Collections.Generic.Stack<T> 永远不会承诺（只是）一个 ADT。

它必须至少提供 ADT 功能（名副其实），但可以免费提供更多功能。

因此它不会尝试隐藏 Contains()、Count、TryPeek() 等。

Answer 3

在伪代码中，这是 Stack 外部的一个 ElementAt，它只使用 ADT 操作：

T ElementAt<T>(Stack<T> items, int index)
{
    var tmp = new Stack<T>();
    while(!items.Empty && index > 0)
    {
       tmp.Push(items.Peek());
       items.Pop();
       index --
    }
    try {
        return items.Peek(); //Presumed to throw an appropriate exception if empty
    }
    finally {
       while(!tmp.Empty)
       {
          items.Push(tmp.Peek());
          tmp.Pop();
       }
    }
}

（以上假定变异 Stacks - 稍微不同的实现适用于不可变堆栈，不需要笨拙的撤消操作）

当然，事实是 .NET 中的 Stack 类型是为 实际问题解决 而构建的，而不是为了一些抽象的纯度，并且 (由于 Stack 提供允许枚举），这里实际上提供了更高效的实现。而且我们不会强迫人们将此类方法复制到 "utils" 库中。

为什么 C# 中的 Stack<T> class 允许 ElementAt(index) 而它是一个 ADT？

Why does Stack<T> class in C# allow ElementAt(index) while it is an ADT?

c#

stack

adt

data-structures