Fixed-size FIFO queue

[Jack]

I want to implement a fixed-size FIFO queue for characters.

I only want to use array not linked list.

For example,

const int N = 10;
char c_array[N];

The question is when the queue is full, there are ten characters in the
queue. When the 11th character comes, c_array[0] will be popped out. I
have to shift all the rest elements in the queue to one slot left. That
is,
c-array[0] = c-array[1];
c-array[1] = c-array[2];
c-array[2] = c-array[3];

...............

c-array[7] = c-array[8];
c-array[8] = c-array[9];

Then I can put the 11th character into c-array[9].

Is there a better way to implement it if only array is allowed?

I know linked list can solve the problem. But all the elements in the
queue have to be consecutive in memory, so linked list can not meet the
requirement.

Thanks.

Jack

[Roberto Waltman]

"Jack" <ju******@gmail.com> wrote:

I want to implement a fixed-size FIFO queue for characters.

I only want to use array not linked list.

For example,

const int N = 10;
char c_array[N];

The question is when the queue is full, there are ten characters in the
queue. When the 11th character comes, c_array[0] will be popped out. I
have to shift all the rest elements in the queue to one slot left. That
is,
c-array[0] = c-array[1];
c-array[1] = c-array[2];
c-array[2] = c-array[3];

...............

c-array[7] = c-array[8];
c-array[8] = c-array[9];

Then I can put the 11th character into c-array[9].

Is there a better way to implement it if only array is allowed?

First of all "c-array" should be c_array.

Use memmove(c_array, c_array+1, N-1);

[Nelu]

Jack <ju******@gmail.com> wrote:

I want to implement a fixed-size FIFO queue for characters.

I only want to use array not linked list.

For example,

const int N = 10;
char c_array[N];

The question is when the queue is full, there are ten characters in the
queue. When the 11th character comes, c_array[0] will be popped out. I
have to shift all the rest elements in the queue to one slot left. That
is,
c-array[0] = c-array[1];
c-array[1] = c-array[2];
c-array[2] = c-array[3];

...............

c-array[7] = c-array[8];
c-array[8] = c-array[9];

Then I can put the 11th character into c-array[9].

Is there a better way to implement it if only array is allowed?

I know linked list can solve the problem. But all the elements in the
queue have to be consecutive in memory, so linked list can not meet the
requirement.

I guess you're looking to do that without shifting the characters each time.
You can implement the queue using circular arrays.

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

[Dann Corbit]

"Jack" <ju******@gmail.com> wrote in message
news:11**********************@f6g2000cwb.googlegro ups.com...

I want to implement a fixed-size FIFO queue for characters.

I only want to use array not linked list.

For example,

const int N = 10;
char c_array[N];

The question is when the queue is full, there are ten characters in the
queue. When the 11th character comes, c_array[0] will be popped out. I
have to shift all the rest elements in the queue to one slot left. That
is,
c-array[0] = c-array[1];
c-array[1] = c-array[2];
c-array[2] = c-array[3];

...............

c-array[7] = c-array[8];
c-array[8] = c-array[9];

Then I can put the 11th character into c-array[9].

Is there a better way to implement it if only array is allowed?

I know linked list can solve the problem. But all the elements in the
queue have to be consecutive in memory, so linked list can not meet the
requirement.

Classical answer is to use a ring buffer. You can use modular arithmetic to
store data in the slots.
That way you don't have to move the data when the array gets full. You will
have to track the head and tail and you will also have to decide how to
handle queue full situations.

[Jack]

> I guess you're looking to do that without shifting the characters each time.

Yes.

You can implement the queue using circular arrays.

But circular array changes the FIFO queue to a LIFO queue, I think.

After the queue is full, i.e., there are 10 elements in the queue, the
11th element will be put at the first slot, c_array[0], other than
c_array[9].

[Dann Corbit]

"Jack" <ju******@gmail.com> wrote in message
news:11**********************@i40g2000cwc.googlegr oups.com...

I guess you're looking to do that without shifting the characters each
time.
Yes.

You can implement the queue using circular arrays.

But circular array changes the FIFO queue to a LIFO queue, I think.

LIFO just means you pull out the last (newest) thing you put in instead of
the first (oldest) thing still in the queue.
If you keep track of where you put it, and you know the head and tail, then
pulling the right item is not difficult.
The issue with a ring buffer which uses an array is that you must handle the
queue full condition somehow. It might be as simple as to write over top
of an existing element or it may be very complex, depending on what the
queue is supposed to accomplish.
After the queue is full, i.e., there are 10 elements in the queue, the
11th element will be put at the first slot, c_array[0], other than
c_array[9].

You either have to write over top of something or pause the queue (in any
case) when the queue is full. If it is OK to stomp on items, then smash
'em. If not, then pause the queue until a slot becomes available.

What is the queue for?

[Nelu]

Jack <ju******@gmail.com> wrote:

I guess you're looking to do that without shifting the characters each time.
Yes.

You can implement the queue using circular arrays.

But circular array changes the FIFO queue to a LIFO queue, I think.

No. LIFO is a stack and operations are done at one end. In a circular
queue (is ring buffer a synonim?) push and pop work at two different
ends that chase each other.
A circular queue uses modulo to find the position of the next element
so, instead of shifting everything you wrap around.

After the queue is full, i.e., there are 10 elements in the queue, the
11th element will be put at the first slot, c_array[0], other than
c_array[9].

If you are using a circular array you'll have to have a way of telling
when the queue is full (either by having an extra position in the array
that you do not use or by using a counter in a queue structure). What
you do when the queue is full depends entirely on the problem you are
trying to solve. You could just overwrite elements if you don't care
about it, or, you could wait for something to pull an element from the
queue to make space for another.

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

[deepak]

I hope Dann answered it.
The operation may not be look like FIFO.
But when trying to get o/p u will feel like a FIFO.

Dann Corbit wrote:

"Jack" <ju******@gmail.com> wrote in message
news:11**********************@f6g2000cwb.googlegro ups.com...

I want to implement a fixed-size FIFO queue for characters.

I only want to use array not linked list.

For example,

const int N = 10;
char c_array[N];

The question is when the queue is full, there are ten characters in the
queue. When the 11th character comes, c_array[0] will be popped out. I
have to shift all the rest elements in the queue to one slot left. That
is,
c-array[0] = c-array[1];
c-array[1] = c-array[2];
c-array[2] = c-array[3];

...............

c-array[7] = c-array[8];
c-array[8] = c-array[9];

Then I can put the 11th character into c-array[9].

Is there a better way to implement it if only array is allowed?

I know linked list can solve the problem. But all the elements in the
queue have to be consecutive in memory, so linked list can not meet the
requirement.

Classical answer is to use a ring buffer. You can use modular arithmetic to
store data in the slots.
That way you don't have to move the data when the array gets full. You will
have to track the head and tail and you will also have to decide how to
handle queue full situations.

[Malcolm]

"Jack" <ju******@gmail.com> wrote in message
news:11**********************@f6g2000cwb.googlegro ups.com...

I want to implement a fixed-size FIFO queue for characters.

I only want to use array not linked list.

For example,

const int N = 10;
char c_array[N];

The question is when the queue is full, there are ten characters in the
queue. When the 11th character comes, c_array[0] will be popped out. I
have to shift all the rest elements in the queue to one slot left. That
is,
c-array[0] = c-array[1];
c-array[1] = c-array[2];
c-array[2] = c-array[3];

...............

c-array[7] = c-array[8];
c-array[8] = c-array[9];

Then I can put the 11th character into c-array[9].

Is there a better way to implement it if only array is allowed?

I know linked list can solve the problem. But all the elements in the
queue have to be consecutive in memory, so linked list can not meet the
requirement.

You need to firm up on your requirement.
It may be that you can use a "circular buffer", whereby you store a start
position.
It is hardly worth doing for a queue of only 10 characters, since the
memove() variety is easier to read and maintain. However if we were talking
of a million characters it would be much faster.
The problem is that there is a discontinuity because we are starting the
array from, say, postion five and then wrapping round. This may or may not
violate your requirements.

If the elements have to be contiguous and in order, you could consider
making the queue of an arbitrarily-sized capacity, say 100. Then you add
characters to the end of the queue, until you exhaust your memory buffer.
The call memove() to shift it up to the top. This cuts the number of calls
to memove() by a factor of nearly 100.

--
Buy my book 12 Common Atheist Arguments (refuted)
$1.25 download or $7.20 paper, available www.lulu.com/bgy1mm