Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Difference between circular queue and double-ended queue (deque)

Reply
Thread Tools

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

 
 
bintom
Guest
Posts: n/a
 
      11-02-2012
Is there any difference between a circular queue and a double-ended queue (deque)?
 
Reply With Quote
 
 
 
 
bintom
Guest
Posts: n/a
 
      11-02-2012
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.
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      11-02-2012
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
 
Reply With Quote
 
bintom
Guest
Posts: n/a
 
      11-02-2012
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.
 
Reply With Quote
 
Werner
Guest
Posts: n/a
 
      11-02-2012
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.

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


 
Reply With Quote
 
Werner
Guest
Posts: n/a
 
      11-02-2012
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...ar_buffer.html

Regards,

Werner
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      11-03-2012
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-endedqueue (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 islimited with fixed size, that is it.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Program blocked in Queue.Queue.get and Queue.Queue.put Kris Python 0 01-04-2012 03:46 PM
Is Queue.Queue.queue.clear() thread-safe? Russell Warren Python 4 06-27-2006 03:03 PM
what's the difference between #include "queue.h" and #include "queue.cpp" Kceiw C++ 3 03-14-2006 03:01 AM
Difference between bin and obj directories and difference between project references and dll references jakk ASP .Net 4 03-22-2005 09:23 PM
Semi-circular definitions (plus circular references) Kiuhnm C++ 16 01-03-2005 03:49 AM



Advertisments