Runtime: Add Dequeue functionality

[danmosemsft]

We have Queue<T> but no double ended queue (Deque) capability.

Opening this issue as a placeholder to gauge level of community need for the type and anyone interested in proposing an API.

Channels has added a private one for its own use. It looks a lot like the existing Queue<T> but with DequeueTail() and DequeueHead() instead of Dequeue().

As this shows it could possibly just need another method on Queue<T> instead of a fully fledged Deque<T> type - if that did not compromise implementation.

[danmosemsft]

@safern

[benaadams]

By itself it would be Stack<T>

I assume PeakTail() and PeakHead() would also be needed? Or just PeekTail and DequeueTail() if added to existing Queue<T> (perhaps with Try variants)

[safern]

Yes it should have Try variants for Dequeue and Peek. I think PeekTail and PeekHead make sense for this kind of structure.

[danmosemsft]

By itself it would be Stack

Can you clarify @benaadams ? I think of Stack as inherently FIFO whereas Deque is obviously double ended. Stack and Queue (and hypothetical Deque) do have similar implementations.

[benaadams]

Can you clarify @benaadams ? I think of Stack as inherently FIFO whereas Deque is obviously double ended.

Just meant Queue<T> is DequeueHead() and Stack<T> is DequeueTail(); obviously neither allows both operations (so there is a gap)

[stephentoub]

It would have:

• DequeueHead
• DequeueTail
• EnqueueHead
• EnqueueTail
• PeekHead
• PeekTail

plus Try variants of the Dequeue and Peek methods.

Or if it were added to Queue, we'd add DequeueHead/EnqueueTail or DequeueTail/EnqueueHead, depending on what we want to think of as the existing Dequeue and Enqueue polarities.

[benaadams]

It would have...

Also Forward and Reverse enumerators?

Sounds like a different type than additions to current Queue? (it would make the api surface quite noisy)

[stephentoub]

Also Forward and Reverse enumerators?

If there's a demonstrated need for that, sure, though I've not seen such a need in my own usage of dequeues.

[safern]

Would making it a wrapper around Queue make sense? And just add DequeueHead/Tail depending on what we want Dequeue to mean? And also add the corresponding PeekHead/Tail under the same constrain?

[GSPP]

I have needed a Deque a few times in the past. The Deque should be as fully featured as possible (e.g. insert and remove at both ends as Stephen already said; convenient helper methods and properties).

It also should implement an interface. IMO it was a mistake that some BCL collection classes started without an interface. For example the set interface and HashSet. It should be properly thought through and shipped in the first version.

Also IMO, the interface should be very rich. It is rare to implement a collection interface. It is far more common to use a collection interface. Example for a mistake: IList<T> is missing AddRange and other range methods. => Optimize for consumption, not for implementation.

Additional features to consider:

• Remove a range of items by value (IEnumerable<T>), by index range (int, int) and by predicate (Func<T, bool>).
• Add and insert ranges of values anywhere.
• An indexer to inspect elements by index (useful to peek ahead and for general extensibility).
• Copy a range of items out into a Span<T>.
• Span<T> overloads in general.
• Expose the internal buffer as an advanced feature. Deque is a fairly advanced functionality already. Maybe we can trust users to not misuse such a feature?!
• A Clear method
• A bool IsEmpty to make checking for that easier and self-documenting
• Enumerating the contents in both directions
• Managing capacity: The ctor should take a capacity specification; TrimExcess; int Capacity { get; set; }
• ToArray, ToList. Even if these are provided as extension methods already (which is not certain) they should be specialized to make them faster. List<T> does it that way.
• Sorting elements

While some of these suggestions might not make the cut a fully featured Deque would be a joy to use because everything you need is there. No need for workarounds.

[pgolebiowski]

Please don't call it a Dequeue. Use the full name of the data structure.

[stephentoub]

Why? "DoubleEndedQueue"? It's very commonly called a deque or dequeue, both in data structure books/articles/tutorials and in other frameworks; that is the name of the data structure as many people know it.

[pgolebiowski]

Yes, DoubleEndedQueue.

• It feels consistent with the .NET naming convention.
• Deque offends my sense of aesthetics.
• What do you mean by "common"? How common?

[svick]

@pgolebiowski

I'd say it's common.

[benaadams]

Abbreviations are capitalised so would it be DEQue or DEQueue?

[stephentoub]

What do you mean by "common"? How common?

Java uses deque: https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

Python uses deque: https://docs.python.org/2/library/collections.html

C++ STL uses deque: http://www.cplusplus.com/reference/deque/deque/

Boost uses deque: https://www.boost.org/doc/libs/1_48_0/doc/html/boost/container/deque.html

Etc.

Abbreviations are capitalised so would it be DEQue or DEQueue?

Are you thinking of acryonyms? Besides, even if it started as a cute abbreviation, the data structure has become known as "deque". Lots of things in computer science get their name because someone's being "fun", and it sticks. If it were, for example, pronounced dee-ee-cue, I'd agree with you, but it's not, it's pronounced deck. Capitalizing it like that would be really confusing, IMO.

[pgolebiowski]

The fact that the authors of these libraries have chosen this name does not mean you should do the same. Don't make a mistake just because a certain number of people made it in the past.

[stephentoub]

Huh? Just because you'd prefer something else doesn't mean everyone else has made a mistake.

[pgolebiowski]

Just because you'd prefer something else doesn't mean everyone else has made a mistake.

Kindly read up and don't involve such rhetoric anymore.

Now to the point. Choosing the term dequeue to actually mean double-ended queue is unfortunate for the following reasons:

• The primary meaning of dequeue is to remove from a queue. Using the same word to refer to a kind-of-related-but-actually-fundamentally-different-concept is in my opinion a wrong decision, because it is confusing.
• Linguistically, the prefix de- indicates removal of or from something specified. This makes the case stronger, because language rules people are familiar with apply to dequeue when it refers to remove from a queue but do not apply when the same word refers to double-ended queue.
• The rules that have been used to form the term dequeue (when referring to a double-ended queue) are not commonly applied by people (general purpose).

On these grounds, I say that it was a mistake. No matter how many people repeat this mistake, it remains being one.

As for .NET naming guidelines:

Using Abbreviations and Acronyms

X DO NOT use abbreviations or contractions as part of identifier names.
For example, use GetWindow rather than GetWin.
X DO NOT use any acronyms that are not widely accepted, and even if they are, only when necessary.

Kindly prove that it is necessary to choose Dequeue rather than DoubleEndedQueue.

[GSPP]

It is so funny that the discussion about the name has already consumed as much space in this thread as everything else.

I vote vor Deque because other platforms do it the same way. Consistency is an important concern.

[stephentoub]

Kindly read up and don't involve such rhetoric anymore.

I'm sorry if you believe I was using rhetoric, that was not my intention. I said two things here. One, that you prefer a different name, which you've stated multiple times, e.g. "Please don't call it a Dequeue" and "Deque offends my sense of aesthetics." Second, that you believe everyone else I cited made a mistake: "don't make a mistake just because a certain number of people made it in the past." And I suggested that the former (that you don't like it) doesn't imply the latter (that everyone else made a mistake). I'm not seeing how that's a fallacy. If you're objecting to my use of the word "everyone", I was talking about the frameworks I cited; feel free to substitute "all of them" or "those frameworks' designers" if you prefer.

Choosing the term dequeue to actually mean double-ended queue is unfortunate for the following reasons

But we're not "choosing" it: it's already been chosen. For decades. By every other popular language's framework I could find that has a collection for this concept.

Kindly prove that it is necessary to choose Dequeue rather than DoubleEndedQueue.

There is no way to "prove" that; whether a type should be named A or B is not "provable." Asking me to prove this suggests to me that you believe this type was always going to be named "DoubleEndedQueue", that you believe your decision on the matter is final, and that you believe I need to make some kind of stellar justification for why it should change. Obviously I don't think any of that is true.

The primary meaning of dequeue is to remove from a queue

I'm actually suggesting we use deque. As have all of those other frameworks.

Linguistically

Lots of words commonly in place started life as a derivation of or acronym of or abbreviation of something else. You don't need to know the history of "deque" as a word to understand the data structure it describes.

As for .NET naming guidelines:

To me it'd be like if we were naming a class ScubaGear: we would name it ScubaGear, not SelfContainedUnderwaterBreathingApparatusGear, because even though it started life as an acronym, it's now a generally accepted word in its own right, and the latter would end up being way more verbose and cumbersome and arguably more confusing than the former.

It is so funny that the discussion about the name has already consumed as much space in this thread as everything else.

I agree with @GSPP here. I've heard and understood your arguments, and I continue to disagree with you. My preference is for Deque, not DoubleEndedQueue. I'll leave it at that so we can move the discussion back to other aspects of the type's design. Feel free to respond on the naming further, but I will refrain from doing so.

[benaadams]

It is so funny that the discussion about the name has already consumed as much space in this thread as everything else.

Its an important aspect of an api 😄

Other item on naming; positionally should it be Head/Tail vs First/Last vs Start/End vs Front/Back

and operationally Append/Prepend, Add/Insert etc as lots of variation across languages:

Its should be a compatible naming between Peek and Enqueue so they are in matching terms regarding the positional

e.g. PeekStart + AddStart rather than PeekStart + Prepend

Unless its an addition to Queue<T> when only one side gets positional as only operating on the head would be the new apis.

[benaadams]

Precedent-wise (not sure https://apisof.net/ is picking up everything as didn't find Last in Linq)

Head doesn't seem to be used in any apis (other than Headers etc)
Tail has some usage in Microsoft.FSharp.Collections
First and Last has usage in System.Linq (also in string and array for LastIndexOf etc)
Append and Prepend is also System.Linq
Front use is graphics related (z-depth, front-facing, bringtofront etc)
Start/End use in string (TrimStart,StartsWith, TrimEnd,EndsWith etc)

[benaadams]

Or... could take the P-languages + JS inconsistency approach and just keep the existing methods and merge Queue and Stack operations for Deque so

Push
Dequeue
Pop

Though that wouldn't help with Peek as it would still require a positional indicator (unless that was conveyed by an enum param)

[safern]

In my opinion I'd use Push/Pop or Enqueue/Dequeue with a positional indicator. i.e PushFront, rather than combining Push/Pop concepts with Enqueue/Dequeue just to avoid using positional indicators as that would be more confusing and people might find in the position of needing to read the docs of what does Push means, inserting at the front or the back of the Deque.

From the two above I would use the later (Enqueue/Dequeue) to be consistent with the Queue concept.

And in my opinion for the positional operators, I like Front/Back as they are more descriptive to me of where the item in the Deque is going.

[benaadams]

In my opinion I'd use Push/Pop or Enqueue/Dequeue with a positional indicator. i.e PushFront

Could just use an enum; then it would work with existing Queue

enum QueuePosition
{
    Front,
    Back
}

public partial class Queue<T>
{
    T Dequeue(QueuePosition position);
    bool TryDequeue(QueuePosition position, out T result);

    void Enqueue(T item, QueuePosition position);
    bool TryPeek(QueuePosition position, out T result);
}

[danmosemsft]

@benaadams after all that thinking -- any interest in writing out a straw man API?

For extending Queue vs a new type -- I am not sure I see a consensus emerging. If we expect to keep the implementation the same as Queue then it seems to me simplest to extend the API of Queue.

[Berrysoft]

it seems to me simplest to extend the API of Queue.

Yes, It is indeed the simplest, but may lack compatibility, or readability. You see, if you keep the compatibility, the APIs may look like that:

void Enqueue(T item);//Front or back?
void Enqueue(T item, QueuePotision position);

or

void Enqueue(T item);//Front or back?
void Push(T item);//Front or back?

Another question: do we need Stack<T>, after extending Queue<T> or adding Deque<T>?

[stephentoub]

QueuePosition

It'd be good to avoid forcing every operation to do an additional branch to determine what end on which to operate.

[mthalman]

If the decision ends up being that there are two distinct queue classes (the original Queue class and the proposed double-ended queue class), might I then propose that there be a common interface between the two? The interface would contain all the same public members as the original Queue class (e.g. Dequeue, Enqueue, etc.). This would then allow for code to consume either instance but of course be restricted to using it in the way the original Queue class is used.

public interface IQueue<T> : IReadOnlyCollection<T>, ICollection
{
    T Dequeue();
    void Enqueue(T item);
    // etc.... same members as Queue class
}

[V0ldek]

Reusing the existing Queue<T> API is tempting, but I think there is more code reuse opportunity here. The implementations of Queue<T>, Stack<T> and Deque<T> will be very similar. Specifically, Queue<T> and Stack<T> are just constrained versions of the Deque<T>. So for an example API of the Deque<T>:

class Deque<T>
{
    void EnqueueFirst(T item);
    void EnqueueLast(T item);
    T DequeueFirst();
    T DequeueLast();

    // Additional Peak and Try variations of the methods.
}

we could implement Queue<T> and Stack<T> as simple facades over a Deque<T>

class Queue<T>
{
    private readonly Deque<T> _deque;

    public void Enqueue(T item) => _deque.EnqueueFirst(item);
    public T Dequeue() => _deque.DequeueLast(item);
    // Pick, Try, etc.
}

class Stack<T>
{
    private readonly Deque<T> _deque;

    public void Push(T item) => _deque.EnqueueLast(item);
    public T Pop() => _deque.DequeueLast(item);
    // Pick, Try, etc.
}

Also, I agree with mthalman on the common interfaces. I'd propose obvious IQueue<T> and IStack<T> interfaces, and then making Deque<T> explicitly implement them

class Deque<T> : IQueue<T>, IStack<T>
{
    // Implementation...

    void IQueue<T>.Enqueue(T item) => EnqueueFirst(item);
    T IQueue<T>.Dequeue() => DequeueLast();
    void IStack<T>.Push(T item) => EnqueueLast(item);
    T IStack<T>.Pop() => DequeueLast();
    // Explicit implementations of Pick, Try, etc.
}

This has the obvious drawback of adding an additional layer of indirection into Queue<T> and Stack<T>, which I'm guessing would have be a performance hit. Also both will take up more effective memory, word size for both for the Deque<T> references and 8 bytes for Stack<T> (_head and _tail members in Deque<T> that Stack<T> wouldn't need). Oh, and it breaks serialization for both as well. But I doubt there's a way to achieve more code reuse.

As an alternative that also tries to maximise reuse, I'd be in favour of creating the obvious IQueue<T> and IDeque<T> interfaces and then either adding deque functionality into Queue<T> or opening up Queue<T> for extension via inheritance: perhaps a QueueBase<T> that is basicaly the current Queue<T> implementation with all public methods turned protected, then turning Queue<T> and Deque<T> into dummy interface implementations calling the base methods. That way we can provide any naming convention for various operations independently of the actual implementation. Alternatively the members of QueueBase<T> would be private protected and the class would be an inaccessible implementation detail more than anything else.

class Queue<T> : QueueBase<T>, IQueue<T>
{
    public void Enqueue(T item) => base.EnqueueLast(item);
    public T Dequeue() => base.DequeueFirst();
}

class Deque<T> : QueueBase<T>, IDeque<T>
{
    public new void EnqueueFirst(T item) => base.EnqueueFirst(item);
    public new void EnqueueLast(T item) => base.EnqueueLast(item);
    public new T DequeueFirst() => base.DequeueFirst();
    public new T DequeueLast() => base.DequeueLast();
}

And to chime in on the naming discussion, I prefer First/Last because it's in line with how LINQ names it and with FIFO/FILO naming.

[TonyValenti]

Hi All,
I wanted to point out that the LinkedList class has pretty much everythign you're looking for out of the Dequeue except for the nicely named members. I've used LinkedList plenty of times as a Dequeue since you can quickly add and remove from both ends.

[Avid29]

Deques, being an abstract structure also have many implementations.

It appears the only method considered has been a reallocating circular buffer with a few more methods than the existing Queue<T>

For example: This C++ implementation
This is a C++ Deque that has a 2D array for reallocation with the root array acting as a circular buffer.

Pros:
Faster reallocation
Static pointers (useful for unsafe)

Cons:
Slower constant time due to extra math
More memory overhead

I've also played with the idea of a Deque with dynamically sized "chunks" as I've called the segment in the map. I found some really good cases for it but it also wildly under performed in others. Perhaps someone wiser could make something of it. All my work is here.

[Frassle]

I'd like to add another pro to @Avid29 suggestion of using the approach of nested arrays. It would allow deque to hold more elements than a plain .NET array allows. I suggested it as one solution to https://github.com/dotnet/runtime/issues/12221.