Circular Queue and Circular Linked List

Question

I want to have a clear difference between circular queue and circular single linked list ?? Although on the outset,both look nearly same....

Solution 1

Circular queue or Circular Buffer: is a way of implementing a queue. For example, suppose you want to implement a queue using an array. You'd have your enqueue() and dequeue() methods.

Suppose the underlying array is of length 7, and the user enqueues five values, so the values in the underlying array look like this:

            head                   tail
position:  | 0 | 1  | 2 | 3 | 4  |   5  |   6  |
value:     | 3 | 12 | 5 | 4 | 71 | free | free |

Now the user wants to dequeue an element, removing value 3 from position 0. As the queue implementer, you'd have to figure out how to handle this. A basic solution would be to move all values down by one position so the underlying array now looks like this:

            head               tail
position:  | 0  | 1 | 2 | 3  | 4    |   5  |   6  |
value:     | 12 | 5 | 4 | 71 | free | free | free |

but that may require unnecessarily copying a lot of values every time you dequeue anything! One way to avoid that is to say that your head is now at position 1 instead of 0,

                   head               tail
position:  |   0  | 1  | 2 | 3 | 4  |   5  |   6  |
value:     | free | 12 | 5 | 4 | 71 | free | free | 

so now every time you add a new element you'll just add it to the tail (and increment the tail position), and if you remove an element, you'll just move the head. This way you don't have to do any unnecessary copying.

Once the tail reaches the end of the array it'll start wrapping over to the beginning of the array -- i.e. the queue will move in "circle" over the underlying array. For example, after a few more enqueues and dequeues, the underlying array would look like this:

                  tail                head
position:  | 0  |   1  |   2  |   3  | 4  | 5  | 6 |
value:     | 91 | free | free | free | 71 | 22 | 8 | 

The tail now wrapped around to the beginning of the array.

Circular linked list: a linked list where the head points to the tail. It's a general-purpose circular structure. It can be used to implement a circular queue/buffer, or it may be used for something else.

Solution 2

Check this out: http://www.vias.org/cppcourse/chap20_05.html You will notice that a circular queue is implemented as an array in the standard definition.

Comments

[obataku]

A linked list can be used to implement a circular queue, but a circular queue need not be implemented as a linked list.

[Admin]

@oldrinb we know circular linked list can be used to implement queue and stack. but is it acceptable as a general question to ask stack can be used to implement circular linked list?

[keerthi]

so what is the main difference exactly??

[Mihai Todor]

If you implement it as an array, you only need to make a single lookup in the buffer to get the desired element. Otherwise, if it's a list, you would need to traverse it node by node to get the element that you need. This structure is used in resource tight environments, where every CPU cycle counts, and also the memory is very limited (so you don't allow buffers to expand indefinitely).

[Admin]

we know circular linked list can be used to implement queue and stack. but is it acceptable as a general question to ask stack can be used to implement circular linked list?