在C#堆栈中是否有随机访问？

Question

我有点学习数据结构,所以请原谅新手问题.问题是,我在C#中使用Stack类,我想随机访问元素.我知道我可以使用ElementAt随机访问:

Stack<int> mystack = new Stack<int>(4);
...//assume the stack is filled here
int value = mystack.ElementAt(2) // if I wanted element 2

但我只能得到价值,我无法修改它.我的意思是,在List中,我可以将随机元素修改为:

List<int> mylist = new List<int>(4);
mylist[2] = 35;

我想对Stack做同样的事情,但它没有索引器.也许这是不可能的,如果是这样,我也想知道原因.我知道当需要随机访问时,通常不会使用堆栈,但在解决问题时我仍然需要它.我最终找到了一个更好的方法,但我仍然想知道.最后,关于ElementAt(),它是O(1)还是O(N)??

Answer 1

我想对Stack做同样的事情,但它没有索引器.也许这是不可能的,如果是这样,我也想知道原因.

不,这是不可能的.Stack<T>不提供允许随机访问的任何成员(直接到底层列表数据,即).同样,公共接口Stack<T>仅确保可以修改堆栈的顶部,而不是任何其他项目 - 这反过来意味着不必以适合随机访问的方式实现类(例如,内部数组),但可以以随机访问不是非常高效的方式实现(例如链表).因此,Stack<T>故意仅实现ICollection<T>接口,该接口不提供用于随机访问的任何成员,相反IList<T>,其实质上是具有随机访问的集合.

最可能的原因是,正如你所说:

当需要随机访问时,通常不会使用堆栈

至于你的具体情况:

但在解决问题时我仍然需要它

在这种情况下,你显然不需要堆栈(LIFO列表),所以只需使用List<T>.

最后,关于ElementAt(),它是O(1)还是O(N)??

与前面提到的Stack<T>类型相关,并且没有检查实现ElementAt,我会假设ElementAt使用堆栈提供的枚举器并迭代堆栈中的元素,直到它到达指定的索引,因此在这种情况下它表现为O(N) .

请注意,在一般情况下,这不一定是真的; 很可能ElementAt以首先检查IEnumerable<T>传递给它的方式是否也实现的方式实现IList<T>,在这种情况下它可以使用为该接口定义的索引器,在这种情况下可能实现O(1)的复杂性.