Talk:Deque
From Wikipedia, the free encyclopedia
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)
[edit] 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.
[edit] 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)
[edit] 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)
