Queues in C

[mike79]

Hi all,

I have attempted to implement a queue in C.

So far all is well, but I have a question to ask you experts in
regards to my implementation.

Say I have a queue of integers. My queue will be an array of integers
which could hold 100 elements for example.

I have two variables namely firstElement and lastElement. When I add
an integer to the queue, the lastElement variable will be incremented
and the integer stored at this index (lastElement) into the queue
array.

When I remove an element from the queue, the integer stored at
"firstElement" will be returned and the variable firstElement will
also be incremented.

If I keep doing this, soon the lastElement will reach the end of the
queue, and I will run out of space. Should I shift all the elements
back to the start of the queue array everytime I get a value from the
queue, or should this be how a queue is implemented? But if I shift
everytime i retrieve data from the queue, wouldn't this slow down the
program alot?

Thank you for all the help and support,
mike79

 

[Thomas Matthews]

Hi all,

I have attempted to implement a queue in C.

So far all is well, but I have a question to ask you experts in
regards to my implementation.

Say I have a queue of integers. My queue will be an array of integers
which could hold 100 elements for example.

I have two variables namely firstElement and lastElement. When I add
an integer to the queue, the lastElement variable will be incremented
and the integer stored at this index (lastElement) into the queue
array.

When I remove an element from the queue, the integer stored at
"firstElement" will be returned and the variable firstElement will
also be incremented.

Yes, this is queue in action, first in last out.

If I keep doing this, soon the lastElement will reach the end of the
queue, and I will run out of space. Should I shift all the elements
back to the start of the queue array everytime I get a value from the
queue, or should this be how a queue is implemented? But if I shift
everytime i retrieve data from the queue, wouldn't this slow down the
program alot?

Thank you for all the help and support,
mike79

Perhaps you want a _circular_ queue or a.k.a. ring buffer.

In a circular queue, based on an array, when the pointers go past
the end of the array, they are moved to the beginning of the array.
One technique for implementing a circular queue is to have two
pointers, first and last; and a boolean variable to indicate full
or empty. When first == last, the queue is either full or empty
which the boolean variable is used for.

For more information about this and other data structures,
read
--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Ema]

Hi all,

I have attempted to implement a queue in C.

So far all is well, but I have a question to ask you experts in
regards to my implementation.

Say I have a queue of integers. My queue will be an array of integers
which could hold 100 elements for example.

I have two variables namely firstElement and lastElement. When I add
an integer to the queue, the lastElement variable will be incremented
and the integer stored at this index (lastElement) into the queue
array.

When I remove an element from the queue, the integer stored at
"firstElement" will be returned and the variable firstElement will
also be incremented.

If I keep doing this, soon the lastElement will reach the end of the
queue, and I will run out of space. Should I shift all the elements
back to the start of the queue array everytime I get a value from the
queue, or should this be how a queue is implemented? But if I shift
everytime i retrieve data from the queue, wouldn't this slow down the
program alot?

You can implement a circular buffer for the queue.
In practice, it means that you increment firstElement and
lastElement module (%) the lenght of the array.

You must also pay attention not to reach lastElement with firstElement,
that is "to dequeue elements that are not been enqueued".

Bye,
Ema

PS. Sorry for my English...

 

[Fogus]

If I keep doing this, soon the lastElement will reach the end of the

queue, and I will run out of space. Should I shift all the elements
back to the start of the queue array everytime I get a value from the
queue, or should this be how a queue is implemented?

Why not just make the array circular. That is, when you get to the
index length-1 loop the index back around to zero. The only problem
with this is that if you keep adding elements then the firstElement and
lastElement indexes will cross... but such is life with static
structures.

-m

 

[Peter Ammon]

Yes, this is queue in action, first in last out.

*cough*

[...]

-Peter

 

[Default User]

Yes, this is queue in action, first in last out.

That would be a stack. Queues are FIFO.



Brian Rodenborn