Talk:Double-ended queue

deque

This came up in a Scrabble game: how is deque pronounced? Should the correct pronunciation be put into the article? -- hike395 05:50 27 Jul 2003 (UTC)

Wouldn't it be a kindness if someone could come up with a different word to use for this ADT? How about "biqueue" ? Then we could quit trying to keep deque and dequeue straight from one another. --MarkGoldfain (talk) 05:05, 16 October 2019 (UTC)

pronunciation, external link nit

deque rhymes with "check"

the implementation at the external link looks to implement something like a doubly-linked list... ostensibly, one would use a linked list if one wanted a linked list...

Maybe, but that's no reason not also to use a linked list if one wants a deque. A doubly-linked list is a very complicated structure to reason about. By hiding it behind an abstract interface with very limited access functions (push and pop at each end) one acquires a useful structure which is also easy to reason about. You're confusing interface with implementation; if a deque is the interface you want, the implementation should be largely irrelevant.

Dequeue redirects to Deque

Dequeue is an action, which means to remove from a Queue. Deque is a double-ended queue. Therefore, I suggest that Dequeue redirect to Queue, not Deque. Cparker 21:47, 28 March 2006 (UTC)

Either that, or just remove the redirect altogether. Cparker 21:47, 28 March 2006 (UTC)

Actually you can find uses of "dequeue" as a noun, "double-ended queue". Notably, Hopcroft & Ullman use it this way. There was some discussion of this in comp.lang.c++ a few years ago: http://groups.google.com/group/comp.lang.c++/browse_thread/thread/730d25ca7f9fe937/38129ef5a0328a0a?tvc=2. SpuriousQ 10:46, 23 May 2006 (UTC)

Comment on Implementations

There is 3rd common way of implementing deques and that is as an array of pointers to fixed sized pages of the elements (usually a power of 2, even 1 element) The advantage of this scheme is that if new elements are inserted at the front or end of the deque, pages containing elements in the middle of the deque need not be disturbed. Nearly all the C++ vendor implement in this fashion. Note also: The C++ deque cannot be implemented using an array. There is a requirement that references to elements in the middle of a deque remain valid if only the only thing done to the deque is add new elements at either end. An array implementation would fail when the array needs to be reallocated. --Stephen Howe 14:53, 29 December 2006 (UTC)

Be bold and add it! -SpuriousQ 17:50, 29 December 2006 (UTC)

Applications?

Could someone add an example of what a deque may be used for? Specifically, a deque that contains the six operations described in the wiki article and no others. I think it would help me (and others) understand conceptually what a deque actually is. —Celtic Minstrel (talk • contribs) 03:23, 15 November 2008 (UTC)

There has been no action or comment about this. Is it because my question went unnoticed, or does nobody know the answer? —Celtic Minstrel (talk • contribs) 20:30, 13 April 2009 (UTC)

I added now description of one application (A-Steal job scheduling algorithm). I hope this helps. Andreas Kaufmann (talk) 21:07, 15 April 2009 (UTC)

It's somewhat helpful, but it wasn't quite what I had in mind. A stack or a queue is easy to understand, because we encounter such things all the time (a stack of papers, a queue at the supermarket). A deque, on the other hand, isn't so obvious. Perhaps that's unavoidable though. (I don't think a deck of cards makes a good example, does it?) —Celtic Minstrel (talk • contribs) 15:37, 14 August 2009 (UTC)

Operations

Why should list of supported operations of an abstract data type list language specific names for these operations? --Drakyoko (talk) 23:23, 11 March 2009 (UTC)

do any one know about the merit and demerits of dequeue? —Preceding unsigned comment added by 117.97.117.133 (talk) 15:36, 5 May 2009 (UTC)

Compexity

Why the computational cost of accessing an element in the middle of the array is even considered? --Drakyoko (talk) 23:25, 11 March 2009 (UTC)

Because it's part of the tradeoff between array and linked-list implementations. Random access (this is what accessing an element in the middle by index) is O(1) in an array implementation but O(n) in a linked-list implementation. --76.167.241.45 (talk) 05:23, 14 March 2009 (UTC)

His point, I think, is that random access is not one of the operations that a deque exposes. Sneftel (talk) 19:04, 14 March 2009 (UTC)

Neither is insertion and deletion in the middle of the list. For the operations that a deque exposes, both the array-based and linked-list implementations are O(1) or amortized O(1). So if you only care about the operations that a deque exposes, then either implementation would be very good, and there wouldn't be anything to compare. It's the additional operations that contrast them that is being talked about. --76.167.241.45 (talk) 06:45, 15 March 2009 (UTC)

I agree that it's not worth considering middle insertion/deletion either. As to comparison, there's more to linked lists and dynamic arrays than complexity analysis. Sneftel (talk) 22:29, 15 March 2009 (UTC)

First sentence: mis-statement?

"a double-ended queue ... is an abstract data structure that implements a *queue* for which elements can only be added to or removed from the front (head) or back (tail)"

Is a dequeue really a type of queue? You can only add to one end of a queue, right? I agree that a dequeue is a type of *list*, though.

(I'm holding back on changing the sentence because I might be missing something.) — Preceding unsigned comment added by 131.107.0.76 (talk) 17:32, 18 July 2011 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Double-ended queue. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20091015073943/http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html to http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 06:59, 13 September 2017 (UTC)

Big problem with "Purely functional implementation"

I've read section "Purely functional implementation", and noticed a number of "errors" in it. I say "errors" because they seem to me so obvious and abundant that I'm considering it's failure to understand on my part. As a mater of fact, it looks like whole section is beyond repair, as if someone has been trolling by posting it at wikipedia. Due to sheer quantity, as well as nature of this "errors", I don't feel confident trying to fix things up: 1. It may be that I correctly identified real mistakes, in which case me fixing them would left article with a content with less obvious errors, but still deeply incorrect (especialy last two passuses, which are enormously confusing both for lack of explanation and possibly incorrect content), so problem would be "sweept under a carpet". 2. or it may be that I misunderstood whole thing, and would only do a damage.

Here are some of "mistakes" I've found.

CURRENT: "Furthermore, it is assured that |f| <= 2|r|+1 and |r| <= 2|f|+1 - intuitively, it means that neither the front nor the rear contains more than a third of the list plus one element."

CORRECTED: Furthermore, it is assured that |f| <= 2|r|+1 and |r| <= 2|f|+1 - intuitively, it means that neither the front nor the rear contains more than a two thirds of the list plus one element.

EXPLANATION: first part of this sentence (specifically formula in it) is at odds with the second part of it

CURRENT: "Note that, when a double-ended queue contains n elements in the front list and n elements in the rear list, then the inequality invariant remains satisfied after i insertions and d deletions when (i+d)/2 <= n. That is, at most n/2 operations can happen between each rebalancing."

CORRECTED:

EXPLANATION: First, formulae $(i+d)/2<=n$ is incorrect, secondly, even if it was not, next sentence is in error: it should be either

• when (i+d)/2 <= n. That is, at most n*2 operations can happen between each rebalancing." or
• when (i+d)*2 <= n. That is, at most n/2 operations can happen between each rebalancing."

Now on why $(i+d)/2<=n$ is incorrect: There are many ways to demonstrate this but simplest one is that you may alternately add and delete one element to the front (or back) of the list and keep it forever, and it will still stay balanced, that is list may stay balanced even after infinitely many insert and delete operations, they only need to be properly ordered. Now if certain constrains were applied, like insertion only at one end, deletions from the other, certain limits can be deduced. Also it may be said that in most unfavorable scenario, where all operations are deletion, and on the same side of deque it holds that $(n-d)*2+1>=n$ ie. $d<=(n+1)/2$, that is after list was in a balanced state (with $|f|=|r|$), we're confident it will stay balanced for at least next $(n+1)/2$ operations, no mater what those operations are. After that, list may become unbalanced depending on what operations are applied ...

CURRENT: "... double-ended queue lenf, f, sf, lenr, sr leads almost to the ..."

CORRECTED: " ... double-ended queue lenf, f, sf, lenr, r, sr leads almost to the ... "

EXPLANATION: list is sixtuple (as it was previously called)

Next two pasuses lack explaination, so I can't really say what/if something is wrong with them besides being confusing since I didn't understand them really, but given previous pasages I'm not sure if that is maybe due to them containing mistakes as well..

In short, I considered correcting specific problems within this section but than backed-off since that would be incomplete and whole section actualy seems broken. Then, there was an option to simply delete section, but that would potentialy be considered an act of vandalism, and besides that it wouldn't be that good idea removing whole thing - best if someone who knows his busines would actualy fix or rewrite the whole section. Besides that, I started wandering if I am maybe geting it all teribly wrong, and this is not as bad as I came to think.

Anyway, if you have good understanding of this section's subject, please try and fix it. I usualy don't revisit wery often pages I've already read trough, so I'll posibly miss any answeres posted here. This edit was mostly to draw attention to identified deficiencies in this article, so they could be potentialy fixed by someone else who's closer to subject at hand.

If this is an error on my part, please excuse me for vasting your time - I see this post is quite a long one.

Edit:

CURRENT: In code example at the end of this section, on two similar lines:

          let val i= (left+lenr)div 2 and let val j= (left+lenr)div 2

CORRECTED: let val i= (lenf+lenr)div 2 and let val j= (lenf+lenr)div 2

EXPLANATION: Variable 'left' is mentioned. It does not exist, and it doesn't make sense at all. It probably should be 'lenf' instead.

Wikoped (talk) 12:46, 9 June 2018 (UTC)

@Wikoped:. Given that I wrote most part of it, you find me very sorry that I sounded like a troll and that it took me so long to answer. May I suggest you pinging the author of wrong content next time, so that they get notified of the issue. I clearly admit that you noticed some errors that are actually real errors. I'm going to correct them, and hopefully the content will be more clear, I'd love to improve the content as much as possible until it becomes actually useful! As an example, your first remark is totally right, having front and rear of size at most a third is absurd, there would be a third of the list missing. I should have wrote "at least a third", which makes far more sens. I plainly admit it's an error, that is obvious when proof reading. I would hope that it's just human error and not troll level. Which does not mean that I'm happy that it was in wikipedia during three years. Arthur MILCHIOR (talk) 07:33, 18 July 2021 (UTC)

Persistent implementations

Two related questions. Both about this change. I think this whole part should be removed from Language support. We should keep what Haskell currently is. The remaining should be in a section about persistent implementations. Also, User:Dfeuer can you please add references for the various implementations you mention. I can't find any paper co-authored by Tarjan and by some Mihaesau. I find some reference online mentioning a version with Mihaescu, but nothing that lead to an article. Appart from wikipedia quality, I'd also like to read the implementation. Arthur MILCHIOR (talk) 07:24, 18 July 2021 (UTC)

The name is Mihaescu, Radu. I added the missing references. AFAIK no implementation nor official publication. You can find some comments on stackoverflow. Xavier-gl71 (talk) 13:21, 29 November 2023 (UTC)

I believe there has been an implementation, which Ed Kmett pointed me to. No, I don't remember where. It's rather absurdly complex. Dfeuer (talk) 03:33, 31 January 2024 (UTC)

"Common name(s)" in the chart makes no sense

Last year @Defur added this column to the chart of various language names, with no references and no clue as to what qualification makes them "common" when not a single listed language uses them. Maybe a few old CS papers once did? I'm inclined to remove the column, but I'd like to make sure I'm not missing something here. SilverbackNet ^talk 05:29, 10 August 2023 (UTC)