Stack and Queue should allow for random access in constant time

[GSPP]

The Stack<T> and Queue<T> classes algorithmically could allow for random access in constant time. At the moment this is not represented in the API surface of those types. I propose to lift that restriction.

In fact most members of List<T> could be made available on Stack<T> and Queue<T> as well. Really, Stack<T> and Queue<T> are mostly different ways to index and interpret an underlying array.

There is no reason a Stack<T> could not have for example Remove(T) or a RemoveAll(Func<T, bool>) methods just like List<T> has.

I propose in priority order:

1. Add get indexers to Stack<T> and Queue<T>
2. Add the core read and write methods that are required for users to implement the remaining ones. I think that would be Insert, RemoveAt and a set indexer.
3. Add as many List<T> methods as seems appropriate to Stack<T> and Queue<T>, copying them from List<T>. I don't see a reason why the set of methods to copy should be limited. We could go for feature parity.

This issue seems like a good candidate for a community contribution.

[JonHanna]

Why have a stack at all then? (List could just have a few other methods added).

Why enforce a constant-time-random-access implementation?

[GSPP]

Maybe one of Stack or Queue should never have existed, true. But now they are here.

I don't see any other backing store coming for the same reason List will always be a simple array internally.

[JonHanna]

It might be interesting to experiment with a linked-list of increasingly sized arrays. That approach could reduce the time taken for resizes, while still having good locality of reference within each block.

[GSPP]

It might. This is, indeed, only a good idea for Stack in its current form and not for List.

Still, the Stack class always feels crippled when I use it. And what you propose does not change the asymptotic timings.

I always feel the BCL could have had a really good collection library with multiple implementations for the same logical interface. Alas, this is apparently not the leading idea. Here, there could have been multiple stack implementations one of which would implement the idea you just brought up. Too late, now we are fixed on this design.

[Clockwork-Muse]

logical/design problem: for both a stack and a queue, what does collection[0] retrieve? Or for any of the other methods; queues in particular are pretty bad, given you have processes preferring to interact with the same thing from different directions. Queues can also be conceptualized as moving "windows", so it also begs the question of whether the index should stay the same for a given element, as opposed to updating every push/pop.

What is it you've been doing that you need indexed access into a stack/queue? I do think it would have been nice for Stack/Queue interfaces, though...

[GSPP]

Collection[0] is, in my mind clearly, what Peek would return. After each write the indexes would change.

The use case is an expression parser and I need to peek into the current parsing stack. So I want the second-next element by saying stack[1].

I don't see any definition problem for queues. We are not talking about double-ended queues here as the BCL does not have such a thing.

Maybe instead of an indexer we could have a Peek(int) overload for increased clarity.

[ellismg]

I don't think it's a good idea to break the abstraction over the underlying representation (which this proposal would do) unless there's a clear benefit. What are the cases where you find yourself working with a Queue<T> and you want random access? In the cases where you are using Stack<T> and want random access to member elements, what drove you to use Stack<T> instead of List<T>? Interop with existing code? The fact that for Push and Pop the code is easier to read? Something else?

My general feeling is that it's a bad idea to add APIs to Stack<T> and Queue<T> to make them feel more like List<T>.

[weshaggard]

👍 to @ellismg's comments that I don't think it is a good idea to break this abstraction.

[GSPP]

what drove you to use Stack

Because I logically wanted a stack and List does not have a Pop method. I would have needed to add it.

I just did a survey how other platforms do it:

1. Java has a list-like stack.
2. Python, Ruby and PHP have stack-like methods on its list type.
3. C++ has a stack as a wrapper of another collection. The stack exposes only stack methods.

Maybe all that's needed is something like a Pop on List<T>. Could be called TakeLast, ExtractLast, RemoveLast.

[Clockwork-Muse]

@GSPP - But in your case you only wanted one extra level down, right? Were you not in a situation you'd be popping the top element off anyways?

Note that in the case of stacks, there are two different ways to index them: root is 0 ("I'm on the nth level"), and head is 0 ("root is n from my current position").

[GSPP]

@Clockwork-Muse sometimes I would pop one or multiple elements, but sometimes I would only peek and fail to match.

[ianhays]

Thanks for the suggestion, but from the above discussion it sounds like we won't end up taking this change. Closing.