Is there random access in C# stacks?

Question

I am kind of learning data structures so excuse the newbie question. The thing is, I am using the Stack class in C# and I would like to have random access to elements. I know I can get random access with ElementAt like:

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

But I can only get the value, I cannot modify it. I mean, in a List for example, I can modify a random element as:

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

I would like to do the same with a Stack but it has no indexer. Maybe it´s just not possible, if so, I would like to know also the reason. I know one doesn´t normally use stacks when random access is needed but still I needed it while solving a problem. I eventually found a better way but still I want to know. Finally, about the ElementAt(), it it O(1) or O(N)??

Answer 1

I would like to do the same with a Stack but it has no indexer. Maybe it´s just not possible, if so, I would like to know also the reason.

No, this is not possible. Stack<T> does not provide any members that allow for random access (directly to the underlying list data, that is). Likewise, the public interface of Stack<T> only ensures that the top of the stack can be modified, not any of the other items - which in turn means that the class does not have to be implemented in a way which would lend itself to random access (e.g. an internal array), but can be implemented in a way where random access would not be very performant (e.g. a linked list). Accordingly, Stack<T> deliberately only implements the ICollection<T> interface, which does not provide any members for random access, as opposed to IList<T>, which is essentially a collection with random access.

The most likely reason is that, as you said:

one doesn´t normally use stacks when random access is needed

As for your concrete situation:

but still I needed it while solving a problem

In that case, you apparently do not want a stack (LIFO list), so just use a List<T>.

Finally, about the ElementAt(), it it O(1) or O(N)??

Related to the aforementioned Stack<T> type, and without checking the implementation of ElementAt, I would assume that ElementAt uses the enumerator provided by the stack and iterates over the elements in the stack till it reaches the specified index, hence in that case it behaves as O(N).

Please note that this does not have to be true in the general case; it is well possible for ElementAt to be implemented in a way that first checks whether the IEnumerable<T> passed to it also implements IList<T>, in which case it could use the indexer defined for that interface, possibly achieving a complexity of O(1) in that case.