A Dequeue - also called a ring-buffer

BenDi

1.19/5 (21 votes)

Mar 30, 2004

69253

1088

Another addition to the System.Collections - a ring buffer, more sophisticated than ArrayList or Queue.

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.