Email Password Remember me?  Lost your password?

• Download source files - 2.37 Kb
• Download demo project - 6.13 Kb

Introduction

Dequeue means 'double-ended-queue'. All who remember the good old STL days will know exactly what it is. For all the others: it's a System.Collections-compatible class implementing a queue that supports Enqueue and Dequeue at both ends.

Usage

The main functions (in addition to all the System.Collections-brabble) are:

• EnqueueHead, EnqueueTail for adding to the DQ
• DequeueHead, DequeueTail for taking from the DQ
• EnqueueHeadRange, EnqueueTailRange for adding a collection to the DQ (the order is preserved)

The DQ allows enumerations and indexed access. For that, you need to know that the 'head' of the DQ is always the element with index 0, the tail is always the element with the index (Count-1). Enumeration is in that order as well.

EnqueueHead/Tail- and DequeueHead/Tail-operations are O(1)-complex, except when the buffer has to be grown, which will take O(n) steps (naturally). So you can see that the buffer is faster than an ArrayList and more flexible than a Queue.

Example

Dequeue D = new Dequeue();
D.EnqueueTail("The");
D.EnqueueTail("big");
D.EnqueueTail("brown");
D.EnqueueTail("fox");
// now D is [The big brown fox ]

Dequeue D2 = new Dequeue();
D2.EnqueueHead("dog.");
D2.EnqueueHead("lazy");
D2.EnqueueHead("the");
D2.EnqueueHead("over");
D2.EnqueueHead("jumped");
// now D2 is [jumped over the lazy dog. ]

Dequeue D3 = new Dequeue();
D3.EnqueueTailRange(D2);
D3.EnqueueHeadRange(D);
// now D3 is [The big brown fox jumped over the lazy dog. ]

History

• 30.3.04 - Inserted.

You must Sign In to use this message board.

Per page 102550

FirstPrevNext

bug found Guggsdu 1:01 13 Sep '04   There is a bug in the DequeueTail-method. The read-out of the object and the count down of the Tail-variable, appear in the wrong order: So you try to read, while the InnerList[Tail]-variable shows you the next free Dequeue-position (with no entry). You better should use this code: public object DequeueTail() {    if(Count==0)             throw new Exception("Dequeue was empty!");    object r = InnerList[--Tail];    if(Tail<0)             Tail+=Capacity;    count--;    version++;    return r; } Sign In·View Thread·PermaLink not a ring buffer wyldeling 10:19 30 Mar '04   Nice description of a deque, but there are a couple of issues. First, you've mispelled the name, it is properly deque, not dequeue, which implies the operation of removing an item from a queue. A ring buffer to me is a circular queue, where if you attempt to add an item when the buffer is full, the first item added to the queue is overwritten. So, a deque is not a ring buffer. Sign In·View Thread·PermaLink 5.00/5 Re: not a ring buffer BenDi 10:57 30 Mar '04   well, i guess youre right with the name but thats really not something to argue about. The ring-buffer thing is more a reference to the implementation. In fact, it only describes the way the DQ uses the (linear) buffer - meaning it writes elements 'around' the linear buffer. Call it a self-extending ring-buffer if you wish. But you are right of course, no elements are ever overridden (behold!). Sign In·View Thread·PermaLink 1.00/5 Re: not a ring buffer Anonymous 17:21 18 Jun '04   wyldeling is quite right. Furthermore, there's nothing circular about about the stl deque. It simply allocates objects using an underlying linked list of pages. This way you don't have the wasted memory of a linked list, but you can keep growing without having to keep reallocating the whole array and then copying the old contents to the new and then deleting the old. If you think about it, a self-extending ring-buffer makes absolutely no sense. The "ring" (or circularity) only exists for fixed sized queues. Otherwise, it just grows in a linear fashion. Capiche? I don't think that wyldeling was trying to be argumentative. He appeared to be correcting a couple of serious inaccuracies in the text that would tend to give people the wrong idea. Publishing incorrect information is worse than not publishing at all because people read it and take it at face value. Then people repeat the errors as if they were fact. The web is peppered with explanations of the underpinnings of the various stl collections. There's no reason to publish stuff without first checking your facts. There's also no reason to get defensive when someone points out a mistake. Nobody's calling you stupid - although one would wonder... The proper thing to do would be to simply correct the error - which I notice you did not. Sign In·View Thread·PermaLink 4.22/5 Re: not a ring buffer swampmonster 15:01 25 Jul '08   wyldeling is right about the name, it's called std::deque, yes. Anonymous wrote: Furthermore, there's nothing circular about about the stl deque. It simply allocates objects using an underlying linked list of pages. Now see that's where you're completely wrong. I would like to see a conforming implementation of a std::deque that uses a linked list of pages. std::deque has to implement at() and operator [], and as the standard dictates they have to run in constant time. Meaning you cannot walk a list of pages to get to the required element. In one widely used implementation std::deque is implemented as an array of pointers to blocks (which hold 1 to 16 elements and which you call pages). So take your own advice and check up on your "facts" (which happen to be WRONG!) before you publish them. Sign In·View Thread·PermaLink 5.00/5

Last Visit: 2:43 14 Nov '09     Last Update: 2:43 14 Nov '09 1