[Feature Request] Add a deque struct to the stdlib

[gabrieldemarmiesse]

Review Mojo's priorities

• I have read the roadmap and priorities and I believe this request falls within the priorities.

What is your request?

Add a Deque struct to the stdlib, similar to python's deque: https://docs.python.org/3/library/collections.html#collections.deque

What is your motivation for this change?

While it's a very useful collection to have in general, in the context of the standard library it offers some new possibilities.
There are multiple places in the stdlib where we want to "consume" objects in a list in order. Doing so currently means either

1. calling List.pop(0), while safe, this is very inneficient as all elements must be moved at every pop()
2. Using a pointer and move_pointee. While this is efficient, this is quite unsafe.

Moving a list pointer into a deque would allow us to call deque.popleft() at very little cost. Thus consuming the elements in order.

Any other details?

The two places where we currently have this issue in the stdlib are List.extends() and Dict.fromkeys()

[bgreni]

@gabrieldemarmiesse I was thinking about this a couple days ago so I'd like to take a crack at it if you haven't already started

[gabrieldemarmiesse]

Let's wait for the go of the maintainers before working on a new struct.

[gryznar]

To be aligned with current naming convention, it should be Deque, not deque ;)

[dimitrilw]

If you want a space to make a Deque struct before core Mojo maintainers give the green-light for std-lib, you are more than welcome to submit PRs to toybox. Honestly, I'm disappointed with myself for overlooking putting deque, ring-queue, and the like to my "hit list" of desired data structures.

[JoeLoser]

I'm +1 for a deque collection. Do you want to write up a one pager on an API design proposal for consideration and we can take a look to discuss before starting down an implementation? You may want to check out https://doc.rust-lang.org/std/collections/struct.VecDeque.html as something to consider too.