Case in point: if we valued terms of art above all else, Dictionary would probably be called HashMap.
But I like Dictionary - it's less intimidating, and emphasises the associative aspect that people (especially beginners) care about rather than the specific implementation details.
The data structure in question is more like an array thatâs suitable for implementing a double-ended queue because you can efficiently prepend values. Itâs a RandomAccessCollection, and its âbidirectionalityâ has to do with insertion, not traversal.
I think the team should rename Deque. There's a number of good suggestions in the thread for what it could be named, of which Queue is probably the best in my view. But I'm adding my voice to weight support against the name Deque rather than for any particular alternative.
My context is that I am a self-taught developer, from New Zealand, a country that primarily uses British-English but also encounters a lot of American English. My degrees are in other disciplines, not Computer Science.
I don't recall encountering the term Deque until it was covered in recent updates about these Collections. I definitely mis-read it as being equivalent to "Dequeue", and my assumption was that perhaps it was the American English spelling of Dequeue.
I think it is hugely problematic for accessibility of this type when people will be learning to dequeue from a deque. It just doesn't pass the sensibly-accessible test for me, for non-English speakers, for new learners, and for people from alternative backgrounds who are more likely to first encounter this type in code rather than in a textbook or class. Swift I think can take pride in being generally very readable. I think the name Deque detracts from that. Just my 2c.
Deque is sometimes written dequeue, but this use is generally deprecated in technical literature or technical writing because dequeue is also a verb meaning "to remove from a queue". Nevertheless, several libraries and some writers, such as Aho, Hopcroft, and Ullman in their textbook Data Structures and Algorithms, spell it dequeue . John Mitchell, author of Concepts in Programming Languages, also uses this terminology.
In my view, the fact that some reputable sources literally call a Deque a "Dequeue", the term that already has another clear meaning in Swift (and elsewhere) should also be a major strike against using it as the name of this type.
Just voicing my preference for Queue. I've always found "deque" confusing. And I don't think it adds much value to mention in the name that the queue is double-ended. The data structure is the same whether it is double-ended or single-ended: you're just disallowing some operations to make it single-ended.
Dictionary is a term of art. It's from NSDictionary, given Swift's obvious Obj-C influence. There's not always a single term of art in use.
Like Stack, Queue already has an obvious meaning, especially in British English, and it's one that creates a different mental model of the type's behavior than it actually has (remove from front, append on back). It also already has a particular meaning in CompSci (e.g. DispatchQueue). This is why deque was coined in the first place.
Given the original issue was one of pronunciation, isn't it simplest to conclude that English is a silly language not governed by laws and just not care? Let the debate be lost to memes like GIF.
std::deque is from the pre-standard C++ STL where it existed since 1999 or earlier
This is in addition to it being the standard term in algorithm literature.
I think DoubleEndedQueue or BidirectionalQueue would also be okay (albeit wordy).
I don't think Queue is a good name. I think there is a place for a standard Queue that does not offer a deque API, not for efficiency but for clarity. Using a Queue makes it clear what functionality you need, which end to enqueue elements to, and which end to dequeue elements from. Using a double-ended queue where a single-ended queue would suffice obscures your intent and makes it easier to enqueue/dequeue at the wrong end.
My opinion on this matter will most likely just be an echo of the many fantastic summaries that everyone has already put into this thread. I find great value in using term of art names because many will instantly know what it is they're looking for and will easily be able to find it within Swift's ecosystem. It's also a great opportunity for those that don't know the term of art to learn about the terminology for future usage. To that end, I also agree that naming should be easy to read and understand for all people, not just people whose native language is English (mine is and I constantly read this as de queue). So I believe there's a fine line where term of art and easy to understand naming can agree and get along, but in the case of Deque, I believe the naming actively hurts readability and understandability.
The immediate reaction is to flesh out the name to DoubleEndedQueue so that 1. we preserve term of art and 2. readability of this name is significantly improved. Many have expressed that this name is a bit wordy, and I agree, but I also believe that the number of times this name is going to be spelt is far lower in practice. Another prior usage of this name is Rust's std::collections::VecDeque (pronounced veck deck...?). Rust's Vec type is their resizable array type, so the name VecDeque implies some array like qualities. That's why I really love @beccadax 's suggestion of DoubleEndedArray. We do lose the Queue term of art ending, but I believe there's also value in using names users are already familiar with (which is what I think Rust is somewhat hinting at with their name). There's also the argument that the stdlib prefers full names vs. acronyms (see RandomNumberGenerator vs. RNG) even though Deque is only partially an acronym.
I think there's a lot of great suggestions in this thread and discussion, but I just wanted to pop in and express my thoughts.
The analogy to a deck of cards is apt as you can add or remove from the bottom or the top of the deck (letâs ignore the cheating implications from bottom dealing in card games).
As a British person, adding to the wrong end of a queue is tantamount to a crime in this country, so Iâd suggest that many people would assume that queues can only be added to at the end (like a stack). Thatâs probably why this structure is sometimes called double ended queue.
Deck is succinct and close to the original name and can only be pronounced one way.
This seems like the least controversial option. AFAIR all class names in Swift right now are UpperCamelCased combinations of English words. We don't seem to have many contractions like Deque. (I may have missed one, but it seems to be the majority at least)
Anyway, mainly a vote against the name Deque in Swift. If it really isn't actually a queue, then I'm fine with other names.
The wikipedia article on this collection is interesting. The title of the article is "Double-ended Queue" but the text uses Deque exclusively. And for British English speakers it reminds us that Deque is pronounced like cheque.
DoubleEndedQueue and Deque seem like the most likely choices for the name.
where i live at least (an american college campus), it is perfectly fine to âappendâ to the wrong end of a queue if you know a sufficiently-ranking staff member in the establishment, are comfortable with chatting up random elements in the buffer, or are an athlete. itâs also quite common for elements to âpopâ off the end of the queue depending on how fast the underlying implementation is, and the length of similar queues nearby :)
I'll put in my preference for Queue. It's simple, straightforward, and well-understood. The fact that the particular Queue implementation supports double-ended operations can be explained in the documentation and doesn't need to be manifested in the name. Short of that, I'm also ok with the term of art Deque. I suspect in general people will be seeking out the data structure because it's a Queue, and those who really need a Deque will easily discover that it's that as well.
As Xiaodi was replying to me, I think I may perhaps be allowed an opinion in this case. A small bit of hyperbole surrounded by extremely insightful and very relevant supporting arguments didnât feel like bullying to me at all. I wasnât hurt the slightest â quite the opposite.
However, spoiling a mostly lighthearted & very very interesting technical discussion by what feels uncomfortably close to a personal attack does feel counter productive to me. I donât think Xiaodiâs wording deserved this reaction at all, and Iâm very sorry to learn how much it upset him.
I think as a general rule, if one needs to start a post with the words âWithout commenting on the actual issueâ, then one might be better off posting it somewhere else.
Case in point:
Sir, this is an Arbyâs.
Edit: And now I find myself worrying I may have in turn upset Jens by overreacting. It is so very easy to unintentionally hurt someone by publicly calling attention to a potential problem, and itâs difficult to undo it. Iâm sorry, Iâll try to be better.
I opened this topic to get a reading on peopleâs opinions and to collect naming suggestions.
Just to be clear, Iâve now published two separate production-grade Swift implementations of this data structure, and I called both of them Deque. I myself need to be convinced that renaming it would be the right move â Iâm part of the problem.
It seems to me that âdequeâ is a bizarre name. I did consider changing it this time, but decided against it â until I witnessed some interactions that reminded me of the problem: its pronunciation works like a secret handshake, and it is very clear to me that some software engineers use it as such. (Thankfully, Iâm sure nobody on these hallowed fora would do that.)
What is not clear to me is whether this problem is bad enough that itâs worth discarding at least half a centuryâs worth of very clear precedent. This discussion didnât exactly clear this up â clearly, people who are already familiar with the name tend to prefer to keep it as is. People who are just coming across it the first time (or still remember the first time they encountered it) tend to be surprised by its bizarro spelling and pronunciation, and wouldnât mind changing it.
My general opinion is that we apply the term-of-art backdoor to our naming conventions way too easily in Swift; software is such a young discipline that Iâm pretty sure no term-of-art is beyond changing yet. (Our profession is at the toddler stage at best. We still soil our nappies every day.)
Or rather, the names would still be pliable, were it not for the searchability argument. The ease of looking up a term is a very effective force against changing it, and âdequeâ is extremely easy to search for. If it didnât have the pronunciation issue, (or if online and offline resources were consistently careful to explain it), then I think it would in fact make an excellent name â this is why the Collections package uses it, too.
Here is an inventory of naming alternatives that stuck with me:
DoubleEndedQueue really is the obvious choice. It is exactly as searchable as âdequeâ, describes what the thing is, and has no pronunciation issues. (âQueueâ is listed in every English dictionary.) However, it is also a bit bland and verbose: it discards a memorable one-syllable name with a five-syllable phrase. I wouldnât like to reinforce peopleâs impression that Swift is a language that prefers a circuitous naming style.
Queue was the name I considered using before settling on Deque. I donât think itâs wrong to use the name Queue for something thatâs not just a single-ended queue. Iâm also not convinced by the argument that Dequeâs queueness is unimportant â I consider single-ended queues are its most important use case, and itâs worth emphasizing it.
However, calling this data structure Queue would be underselling it a little. It would be somewhat like renaming Array to Stack. (Then again, note that beginner Swift programmers are often under the impression that the stdlib doesnât come with a stack implementation. )
Deck would be a great name for this abstract type, if we were inventing it from scratch today. I find the âdeck of cardsâ analogue is a good one. Unfortunately, I think it might be too late â using it would be a short-term disservice to people learning to program, because it would go against all the existing references.
Ring I really like, too. It paints an even better picture than deck, and it has an even better precedent in RingBuffer. However, it has the same short-term issue as Deck â with the addition that it shares a name with an unrelated maths construct.
All in all, this was a very interesting discussion. It did very much weaken my confidence that calling it Deque was the right call â but at the end of the day, I donât regret the decision, either. I think the documentation does a good job of explaining the secret pronunciation, but it would be a good idea to fix it to be less judgmental about it:
struct Deque<Element>
A collection implementing a double-ended queue. Deque (pronounced "deck" or âde-queueâ) implements an ordered random-access collection that supports efficient insertions and removals from both ends.
I donât think the argument about confusing the operation called âdequeueâ with the abstract type pronounced âdequeueâ holds much water. English has a fun tradition of verbing nouns without affecting understanding, and Swift doesnât offer a member function called dequeue, anyway.
Fun fact: I liked the cheque analogue so much that I personally edited the Wikipedia article to add it. Wikipedia really isnât a very reliable resource.
Do people these days even use cheques anymore? I personally never owned a cheque book, I only know about them because my father had them for a few years, and that one time an American tried to pay me with one and my bank just stared at me blankly because they hadn't dealt with one in years.
After pondering it for the wequend, I think that I'm pretty opposed to any *Queue* name if we're going to rename it, because the actual Deque type under discussion exposes considerably more API that a strict reading of "Queue" implies (O(1) insert and delete and both ends); in particular, I do not expect an arbitrary type named *Queue* to be random access. So if we wanted to go with a verbose and explanatory name, I think DoubleEndedArray would be the clear frontrunner for me. If we want to have a compact name, both Deque and Deck are pretty good ("deque" suffers from a bit of the same problem, but is at least commonly used to talk about this specific implementation pattern).