Circular queue implementation and it's basic functions.

Question

5.00/5 (1 vote)

See more:

So as the name of the topic is i have some questions regarding the circular queue.

I'm not asking for anyone to show me the code or develop one for me, my question is probably rather simple for an experienced developer.

So what are the basic functions of Circular queue,

So far i know it has to have insertion method, reading method etc.

But when we read from the circular queue, do we delete the read value as we do with stack? or do we keep it, and once the queue is full we add the new values by simply overwriting the old ones.

Thanks to anyone trying to answer my question!

What I have tried:

I just need some knowledge updates in theoretical part of data structures.

Posted 5-Mar-16 1:05am

Member 12371341

Updated 5-Mar-16 2:31am

Add a Solution

Comments

[no name] 5-Mar-16 7:22am

*lol" I'm just doing similar stuff, while implmenting usb hid for w32 (pure c++), where I use a Queue.

I decided to Support:
a.) ReadFrontQueue()
Does only give you a view to the front element. Does not Change the Queue!
b.) PopFromQueue
Does remove the element from the Queue. And in my case (maybe very specific)... the one who Popped (? not shure whether this was kid save :) ) the front is responsible to release the object at the end.

It's all up to you how you like to do it.

Patrice T 5-Mar-16 13:21pm

What is your usage of the "circular queue" ?
I suspect a wrong name.

Member 12371341 6-Mar-16 8:13am

Nope it's not a wrong name you can call it circular buffer, ring buffer, circular queue, you can google the "circular queue" and you'll get exactly what i'm referring to.

Patrice T 6-Mar-16 15:51pm

Ok, I commonly use a circular buffer which involve fixed size.
For variable size queue, I prefer FIFO queue.

3 solutions

Solution 1

Generally, when you read a value from a queue, you remove it from the head (and you add to the tail, obviously). Some implementations allow a "peek" function which lets you look at the value at the head, but these have to be implemented and used with care as in a multithreaded environment you are not guaranteed that the value you Peeked at is the value you would Get.
It's also useful to have a Capacity function, and a Count as well.
The fun comes when the queue is full - do you discard the element if there is no room, "throw away" the oldest element and overwrite, or raise an error? I've seen all three, and they all have advantages and disadvantages depending on the actual use. I'd be tempted to say that providing an option for what to do on full is the best way.

Posted 5-Mar-16 1:20am

OriginalGriff

Comments

[no name] 5-Mar-16 7:45am

Dear OG in case of c++ and I assume STL (also std::queue) in this case:

Quote: "Generally, when you read a value from a queue, you remove it from the head"

One can have a look to the front element by queue::front() to peek or one can queue::pop the front ;)

Solution 3

For me personally “circular queue” does not exist.

Either it is a queue (no limits theoretically, in praxis of course there are limits) or it is something like a “ring buffer” with a “front” and a “tail” and therefore the difference between the “tail” and the “front” can be limited to something like the “size” of this “ring buffer”.

Now your question:
When you read from the queue, what happens. Does the read item “disappears” or not?

It is up to you what you support.
a.) You can support a “lookFront” (or whatelse) function which does not change the queue
b.) or you let the user of the queue to _pop_ the _front_ item, which really means the item disappears from the queue.

In case of parallel Access to a Queue all this becomes very interesting...
[Edit] and therefore a 5 for your question[/]

I hope it helps.

Posted 5-Mar-16 2:18am

User 11060979

Updated 5-Mar-16 4:01am

v3

Comments

Member 12371341 5-Mar-16 8:41am

In that case we are definitely talking about the "ring buffer" the one with the head and tail.

Thanks for the post

[no name] 5-Mar-16 9:01am

You are welcome.
BTW, accepting only your own answer does not keep us helping ;)

Member 12371341 5-Mar-16 10:45am

Apsolutely, i have no problem anyone checking the topic and if it's even a bit useful to someone else, that's great after all such discussion are probably meant for people to share their knowledge.

Code can be written in many different ways!

[no name] 5-Mar-16 10:49am

? ... it's your choice ;)

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Member 12371341 · Accepted Answer · 2016-03-05T02:31:00

Well I did it this way and generally things work but I'm not sure if it is a conventional concept.

So user creates a queue by passing the size of the queue, and all values are set to 0.
The queue is then empty.

Then we fill the queue so we add in the tail.

We add until the queue is full then :
I got a boolean function that checks if the queue is full and if the user wants to add more elements to it,the program will alert the user that (in case) he continues with the action, some data in the queue will be overwritten, so basically the effect is same if i remove it or overwrite it. ( except i can't get the empty queue once i filled it completely).

The reading from the queue goes like this :
We read the element at which head is positioned and move the head to the next
element, now just the thing is, that once i read all the values i can jump over the tail no problem and keep reading all the elements in the queue as long as
i wish.

Oh and this, i had to use the static array to implement the circular queue.

I can't see a real reason why deleting is better than overwriting or vice versa
generally the program works with all exceptions like (empty queue, full queue...)

Oh and I begin with having the head and the tail positioned at the same index in the queue but make up for it with some thought.

I'm not allowed to use already created structures so no std::queue or similar.

Circular queue implementation and it's basic functions.

3 solutions

Solution 1

Solution 3

Solution 4

Add your solution here

Preview 0

Existing Members

...or Join us