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

B

bintom

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

bintom

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.
 
W

Werner

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
 
Ö

Öö Tiib

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top