This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
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)
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 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)
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)
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)
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)
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)
"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)
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:
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: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 06:59, 13 September 2017 (UTC)
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 is incorrect, secondly, even if it was not, next sentence is in error: it should be either
Now on why 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 ie. , that is after list was in a balanced state (with ), we're confident it will stay balanced for at least next 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
andlet 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)
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)
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)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
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)
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 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)
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)
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)
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)
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)
"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)
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:
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: 5 June 2024).
Cheers.— InternetArchiveBot ( Report bug) 06:59, 13 September 2017 (UTC)
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 is incorrect, secondly, even if it was not, next sentence is in error: it should be either
Now on why 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 ie. , that is after list was in a balanced state (with ), we're confident it will stay balanced for at least next 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
andlet 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)
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)
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)