I can just say that as a non-native English speaker, before reading an explanation and being a bit more careful, I always mentally read "Dequeue" (and thus pronounced it such), doing a google search for dequeue also yields reasonable results. Never got the shortening and weird pronunciation hack used with "deque". Given that it is also reasonably widely used, I definitely would prefer that to avoid the weirdness that is deque.
7 Likes
I still like to use them regularly as much as possible because it gives me the ability to apply the basics of business-math, control of cash flow. The main idea that you keep your "accounts payable" taking longer to close than your "accounts receivable".
I can pay a bill on the 15th, but the money won't come out until the 25th? I won that exchange against the company I owed money to 
On the topic of the thread - several of these comments (on both sides of the discussion) have done an excellent job of summarizing my conflicting feelings as well.
In general, I'm much more in favor of DoubleEndedArray if we're going to rename. Though I also wouldn't mind keeping it with the documentation change you proposed @lorentey
1 Like
I would prefer to keep the name Deque. As many others have pointed out already, it's widely used and understood.
I am against calling it a Ring, because that is not a name widely used for this concept and also clashes with the algebraic structures of the same name.
RingBuffer is a commonly used name, but is really just an implementation detail in this case, so I would also prefer not to use it.
Queue is too abstract in my opinion and should not be a name of a particular implementation, but should be reserved for a protocol.
Deck... please don't.
4 Likes
I second this. Deque may be known in computer science circles, but without that prior knowledge it is really unintuitive.
2 Likes
No names for collections are intuitive. Would you know what an Array was if you hadnât learned the definition?
4 Likes
That's not necessarily true, as array in English has prior usage in (old) formal language. I was taught arrays with the following sentence:
An array of naval cannons on a ship, but replace the cannons with bits or bytes
Also, Dictionary is more accurate than HashMap in that it more relates to how we would interact with the object in real life: looking up definitions (values) by their name (key)
This makes me wonder in hindsight if Array should've been called List and ContiguousArray should've just been Array 
There are easy similes to explain them, that doesnât make them intuitive.
Array, Dictionary, and Sequence are all pre-existing terms that appear in a English dictionary. In my mind, that makes them more intuitive because they map to real-world concepts/definitions. Deque as a word only appears in computer science.
I understand your point that there will always be terms and concepts to learn, it's just my experience that Deque is an especially obscure term.
1 Like
I have a minor preference to not call this "deque" just because there are several major implementation patterns that all share that name, and the differences are consequential. I believe the intended implementation here is an extensible ring buffer, not (say) a segmented buffer. The only thing this data structure provides over Array is faster insertion/removal at the beginning; notably, it does not promise stable element addresses or improve insertion/removal in the interior.
(To be clear, I'm not criticizing the implementation choice. Segmented-buffer deques have much higher overheads, and their added guarantees are rarely useful. List data structures that try to support efficient interior changes usually find that the overheads more than cancel out the theoretical benefits until you scale to enormous sizes. But still, we aren't making those guarantees, and some people may associate them with the name "deque".)
I like DoubleEndedArray as a name; it very conveys the additional properties of the type. But it's not a strong preference, and I could accept Deque.
15 Likes
I like the longer form name you suggested, I know it is minor but in my head deque goes straight to dequeue or popping items out of a queue. Not sure why we need such a short form either.
3 Likes
There are easy similes to explain them, that doesnât make them intuitive.
No, but it makes them a easier to learn and remember...
Anyway, I think DynamicRingBuffer / ExtensibleRingBuffer would also be descriptive in terms of properties of the type (would probably be my personal preference), I think @John_McCall made a very relevant point that there are several major implementation patterns sharing the Deque naming making it unclear what to expect from it as a user when browsing available collection types.
It's like Queue is a bit unclear. Is it a MPSC, MPMC, SPSC, SPMC, for starters...
I can definitely live with DoubleEndedArray, just a targeted -1 for Deque.
2 Likes
As a native English speaker I also read "de-queue" initially. And was unsurprised to learn that itâs pronounced differently, and was even less surprised when I found out why. Especially because âde-queueâ has another obvious meaning as a verb.
English is full of words that have unusual pronunciation that you âjust have to knowâ. It should not come as a surprise that unfamiliar words might need to be looked up in a dictionary or other reference to learn their pronunciation. Thereâs nothing unique about âdequeâ that makes it worth having a referendum on IMO.
I want to be clear that Iâm not disparaging learners of English either. Learning languages is my passion, I live in a non-English-speaking country, and am fully aware of the challenges involved. I just think that, mostly due to Englishâs insane spelling system, it shouldnât be unusual for learners and native speakers alike to need to look up a wordâs pronunciation in order to master it.
In short, thereâs nothing wrong with Deque in my opinion. And itâs a better name than Deck because it shows its etymology through its orthography (ie. you can learn where the word comes from by how itâs spelled).
I think we go with precedent here and put the pronunciation into the docs (as is already the case AFAIK). If there are two accepted versions we can put both (cf. aluminum / aluminium).
5 Likes
Waaaait a second -- "Deque" is supposed to represent a Double Ended Queue?? And we're seriously considering calling it "Deque"?? WHY?? Okay, term of art : who cares -- it's a terrible name, and as a term of art, it is a lesser-known one.
If we're going to pronounce it "Deck", then let's call it "Deck" -- like a deck of cards. That makes sense, and even mostly makes sense in terms of features/usage. (Note: This doesn't really make sense though, because a deck of cards can be shuffled, cut, and have items inserted or removed at positions other than its ends. So "deck" is still a bad name, unless it will have full array semantics, which it shouldn't (see below).)
If we're going to pronounce it "D. Q." -- or worse, also spell it "Dequeue" -- then we're all just crazy. "Dequeue" means to remove something from a queue. Nearly everyone will read it as meaning something like that, and then struggle to understand the usage based on assumptions made due to the name.
Terms of art generally add real value and clarity when they are commonly-used. In this case, while "deque" does have precedent in other languages and is documented in algorithms literature, overall the name makes things less clear and understandable.
Here's a canonical list of names, from best to worst:
- BidirectionalQueue
- DoubleEndedQueue
- Queue
- DoubleEndedArray
- Deck
- [... all other possible names based on English words...]
- EggSalad
- DjwkhdkuWkjh (and all other random-looking character strings)
- Deque
- Dequeue
Swift's API guide makes a few points regarding terms of art:
- Avoid obscure terms if a common word conveys meaning just as well.
- Terms of art [...] should only be used to capture crucial meaning that would otherwise be lost.
One could argue that simply calling it "Queue" could lose crucial meaning -- such as, for example, that one could insert or remove from both ends, as opposed to a strict FIFO behavior. This makes sense, which is why it should be BidirectionalQueue, DoubleEndedQueue, or, if it really does support Array semantics, DoubleEndedArray.
Takin this one step further, if I'm a dev and know what an array is, a "Double Ended Array" doesn't make sense to me. All arrays have two ends, right? And I can already insert and delete anywhere I want. It won't be clear what is being gained. If we don't support all Array semantics, it's not really an array, and if we do, it's not really a queue. Thus, the DoubleEndedArray name is out.
BidirectionalQueue is probably the most accurately descriptive. Or maybe even NonDirectionalQueue, DualHeadedQueue, etc.. Most people think of a generic "queue" as FIFO. If it's FILO/LIFO, it's a stack, and we'll usually call it a Stack. Any sort of prioritized queue will probably be a PriorityQueue. What's a "Double Ended Queue"? Again, queues already have two ends. So DoubleEndedQueue differentiates it from Queue, but doesn't help to clarify the difference. So we have BidirectionalQueue.
Best name: BidirectionalQueue
1 Like
Thats fine, but it had better support an efficient .shuffle()
6 Likes
It does support all array semantics. It's not really [just] a queue. Why is DoubleEndedArray out?
3 Likes
The type weâre talking about supports everything Array does except for direct access to its storage through UnsafeBufferPointer types. It just has slightly different performance characteristics (accesses are very slightly slower; insertions near the front are way faster) and a couple of extra methods that make it more convenient to take advantage of them.
2 Likes
I think Deque is fine. It's a term of art, it's no harder to pronounce than other technical words (cache, for example), and the alternatives are confusing. E.g. What does âbidirectionalâ mean in this context? How is a âdouble-ended arrayâ (or queue) different from a normal array (or queue)? Etc.
7 Likes
+1 for naming it something better. Deck is my favorite so far. De-Queue only describes part of a Deck, but a Deck of cards is easy to visualize.
Im not a compiler programmer by any means but my first thought after reading Deckâs description was, how come this isnât an optimization for Array? Characteristics that make a Deck faster then Array seem really predictable. It would be nice if Deck was just an optimization on array that happens automatically for release builds. But I could see that being very time consuming for the compiler to figure out.
1 Like
That kind of data structure specialization optimization is very difficult to do statically, yeah.
4 Likes
Knuth reports that the term "deque" was coined by E. J. Schweppe. It's conventional to allow the person coining a term to choose the pronunciation for the word they are coining. Popularity has nothing to do with it.
Most of the pronunciation guides on the Web, as well as many people, mispronounce my last name. Does that mean I should change how I pronounce my last name? Of course not! It's just something I gently teach people. I even have a pronunciation guide for my name on my webpage.
People mispronounce words and names all the time, especially in English where pronunciation is only partly phonetic. But that's no cause for shaming anyone. We all should strive to learn proper pronunciations so that we can communicate more effectively via our shared linguistic medium. And we should gracefully tolerate mispronunciations since we all do it.
E. J. Schweppe says "deque" is pronounced "deck." That's good enough for me. It's a wonderful data structure, and I gratefully pay homage to the inventor by pronouncing it correctly.
1 Like