Difference between circular queue and double-ended queue (deque)

bintom

unread,

Nov 2, 2012, 6:06:33 AM11/2/12

to

Is there any difference between a circular queue and a double-ended queue (deque)?

bintom

unread,

Nov 2, 2012, 6:11:59 AM11/2/12

to

On Friday, November 2, 2012 3:36:34 PM UTC+5:30, bintom wrote:
> Is there any difference between a circular queue and a double-ended queue (deque)?

I HOPE TO CONFINE THIS DISCUSSION TO DEQUES IMPLEMENTED AS AN ARRAY

To continue with my query about deques, should one allow elements to be eliminated from the end of the queue or any access be allowed to a deque's elements except to the one at the beginning of the dequeue?

Thanks in advance.

Victor Bazarov

unread,

Nov 2, 2012, 7:29:43 AM11/2/12

to

On 11/2/2012 6:06 AM, bintom wrote:
> Is there any difference between a circular queue and a double-ended queue (deque)?
>

Yes.

V
--
I do not respond to top-posted replies, please don't ask

bintom

unread,

Nov 2, 2012, 8:04:34 AM11/2/12

to

Thanks Victor,

Now I need somebody else to tell me that difference ...

Thanks in advance.

Werner

unread,

Nov 2, 2012, 8:20:23 AM11/2/12

to

There is a good article concerning both these data structures
in wikipedia. The one is called Circular Buffer (to my knowledge
the same as what you refer to as circular queue). The other
deque/double-ended queue.

A circular buffer is typically used (IME) to buffer data
in communication layers. Writes and reads only take place in
one direction (refer to the wiki article).

Deques may grow in both directions, but can only grow from
the ends. You can read/write from the beginning or end.

That is the main difference (IMhO).

Kind regards,

Werner

Luca Risolia

unread,

Nov 2, 2012, 1:25:57 PM11/2/12

to

On 02/11/2012 11:06, bintom wrote:
> Is there any difference between a circular queue and a double-ended queue (deque)?

Apart from all the theoretical differences, circular container types do
not fit into the STL framework well.

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

Werner

unread,

Nov 2, 2012, 2:02:22 PM11/2/12

to

On Friday, November 2, 2012 7:25:59 PM UTC+2, Luca Risolia wrote:
> On 02/11/2012 11:06, bintom wrote:
>
> > Is there any difference between a circular queue and a double-ended queue (deque)?
>
>
>
> Apart from all the theoretical differences, circular container types do
>
> not fit into the STL framework well.

Are you aware of this?

http://www.boost.org/doc/libs/1_51_0/libs/circular_buffer/doc/circular_buffer.html

Regards,

Werner

Luca Risolia

unread,

Nov 2, 2012, 3:32:30 PM11/2/12

to

Yes, I am aware of the boost library: see the Caveats paragraph about
iterators in the documentation, and also Josuttis The C++11 Standard
Library, Extending the STL, paragraph 6.13.

Juha Nieminen

unread,

Nov 3, 2012, 6:38:26 AM11/3/12

to

bintom <binoyth...@gmail.com> wrote:
> Is there any difference between a circular queue and a double-ended queue (deque)?

A deque grows as needed while a circular buffer has a fixed size?

Öö Tiib

unread,

Nov 3, 2012, 9:22:35 AM11/3/12

to

On Friday, 2 November 2012 14:20:23 UTC+2, Werner wrote:
> On Friday, November 2, 2012 2:04:35 PM UTC+2, bintom wrote:
> > On Friday, November 2, 2012 4:59:54 PM UTC+5:30, Victor Bazarov wrote:
> > > On 11/2/2012 6:06 AM, bintom wrote:
> > >
> > > > Is there any difference between a circular queue and a double-ended queue (deque)?
> > >
> > > >
> > >
> > >
> > >
> > > Yes.
> > >
> > >
> > >
> > > V
> > >
> > > --
> > >
> > > I do not respond to top-posted replies, please don't ask
> >
> > Thanks Victor,
> >
> > Now I need somebody else to tell me that difference ...
> >
> > Thanks in advance.
>
> There is a good article concerning both these data structures
> in wikipedia. The one is called Circular Buffer (to my knowledge
> the same as what you refer to as circular queue). The other
> deque/double-ended queue.

The difference is still that ring buffer has *fixed* size. So there are no growth above limit and so there are two implementations when limit is reached:
1) discarding: push to one end of full buffer silently discards an element from other end.
2) refusing: push to full buffer fails.

Deque grows and shrinks dynamically so ends are not related to each other. If lots are pushed and few are popped long enough then it is also "refusing": you get bad_alloc inevitably into your face.

> A circular buffer is typically used (IME) to buffer data
> in communication layers. Writes and reads only take place in
> one direction (refer to the wiki article).

I have seen that the discarding circular buffer is used for storing such data where old data is least important and recent data is most important. So the contents of such circular buffer can be viewed as The Most Recent things + some history. Things are pushed to one end and never popped. Typically diagnostics, alarms, faults, oscilloscope-like data.

Refusing circular buffer however is better than deque in all situations where sane limits for length of queue are not too large. It is considerably faster, does not fragment heap and timely refusal (before the memory is full) is very handy.

> Deques may grow in both directions, but can only grow from
> the ends. You can read/write from the beginning or end.

Circular buffer does not also have any limitations of direction. Growing is limited with fixed size, that is it.