C++ Queue, Fifo, implementation of queue(0, dequeue(), size() and isEmpty() Urgent

I have to finalize an assignement tommorow and need some guidance with my Queue, especially with the implementation of the following operations

queue()
dequeue()
size()
isEmpty(0

Arround the web, i do not find what can help me...

I do have this (see Code Snippet) , but i do not believe that this can help me any further..... Since that is a timing issue on that, I ask for all the help i can get. Thanks

#include <iostream>using namespace std;#define SIZE 20#include "queueel.h"class QueueClass { QueueElement* queue[SIZE]; int head, tail;public:QueueClass(); ~QueueClass(); void qu(QueueElement* newElement); QueueElement* dequ(); int size(); bool isEmpty();};QueueClass::QueueClass(): head(0) , tail(19){} // -1 is not correct init list is fineQueueClass::~QueueClass () {}void QueueClass::qu(QueueElement* newElement) //ok{ //if(isEmpty()){ //queue[head]=queue[tail]=newElement; //} //else{ tail++; queue[tail] = newElement;}QueueElement* QueueClass::dequ(){ if (isEmpty()) {return NULL;} else { head++; return queue[head]; }}int QueueClass::size(){ int counter =0; int s; for(s =0; s<SIZE; s++){ if (queue[s] ==queue[!NULL]){ counter++; } } std::cout <<"Queue has "<<counter <<" Elements" <<std::endl; return counter; } bool QueueClass::isEmpty() { if(size()==0) { cout << "Queue is empty\n"; return 1; } else return 0; }

You have a fixed size queue with the head pointer initially set to zero and the tail pointer set to 19.

This means that the queue is empty when the tail pointer is 1 less than the head pointer, where subtraction is cyclic.
That is, 0 - 1 == 19.

I suggest it is simpler to consider a queue to be empty when the head and tail pointers are equal. This would mean the constructor sets them both to the same value, likely 0.

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Sorry, I was being sloppy. I'm thinking in terms of pointers, but should be talking in terms of subscripts.

Since this is a static array, let me use the word subscript.

Subscripts count from 0 through SIZE-1. Once a subscript has the value SIZE-1, the next subscript value is 0.

Using a 3-element queue as an example, with the head and tail subscripts initially zero, consider
add the value 20 to the queue. That is, queue[0] = 20. It would actually be
queue[head] = 20;
Since we've defined an empty queue as head==tail, and the queue is no longer empty, we need to head++
now head == 1 and tail == 0;
Adding two more elements to the queue
queue[head++] = 30; // head now == 2
queue[head++] = 40; // head now == 3
But 3 > SIZE-1
So head needs to wrap to 0.

(I recognize that this gives head == tail, and the queue is not empty, but let me skip that for the moment)

Almost. In that example, you can return a value greater than SIZE.

I would write it as
int tempTail = (tail >= head) ? tail : tail + SIZE;
int size = tempTail - head;
return size;

BTW, the example I gave previously, with statements such as
queue[head++] = 30;
should really use tail, as in
queue[tail++] = 30;
since one adds to the tail of the queue.

0

george08Author Commented:

Great.

in my isEmpty()

I do understand that if head=tail its empty?

int QueueClass::size(){int tmpTail;int size;if(tail>=head){ tmpTail=tail;size=tmpTail;return size;}else{tmpTail= tail+SIZE;size=tmpTail;}return size;}

size() as posted above is not correct because
tmpTail= tail+SIZE;
size=tmpTail;
return size;
can return a value greater than SIZE.

In my example,
int tempTail = (tail >= head) ? tail : tail + SIZE;
int size = tempTail - head;
return size;
the returned value is always the difference between the tail and head values.

Consider a queue with 1 element
queue[0] = anElement;
In this case, head == 0 and tail == 1;

After enqueuing and dequeuing several values, you could have the tail at zero (having just added an element at queue[SIZE-1] and that be the only element on the queue. So head == SIZE-1 and tail == 0; In that case, you need to subtact
(tail+SIZE) - head, or
(0 + SIZE) - (SIZE-1), to get the proper answer of
1

I'm assuming that the logic for adding and removing items from the queue is something like
Add: queue[head++] = queueElement
Remove: queueElement = queue[tail++]
where I'm not considering wrapping in this statement

0

george08Author Commented:

since i'm not familie with the ? : operator, do you mind putting it in an if else way?

There are two keys to the queue method:
1) Recognize when the queue is already full, and
2) Be able to increment with wrap.

I suggest an Increment method of QueueClass, something like
int QueueClass::Increment(int offset) {
offset++;
if (offset >= SIZE) offset = 0;
return offset;
}

and then use it in the qu method, such as (pseudocode)
if the incremented tail value == the head value
then the queue is full (might give an error mesage)
else
increment the tail value
queue[tail] = queue element
end if

We can talk about dequeuing once enqueuing is working

And, of course, two methods on QueueClass:
int Head() { return head; }
int Tail() { return tail; }

0

george08Author Commented:

Stop stop stop... your are too fast ;-)

1. Posting

>>There are two keys to the queue method:
>>1) Recognize when the queue is already full, and
>>2) Be able to increment with wrap.

int QueueClass::Increment(int offset) {
offset++; //offset is the element we wanna put in our queue? why do we increment it then?
if (offset >= SIZE) offset = 0; //SIZE is just how big our array is, isn't it? Would be size()<SIZE better. Because then only we do // can put our offset in the queue....
return offset;
}

Why do we return an offset? Better nothing to return?

If we didn't have to worry about wrapping from SIZE-1 to 0, then we could simply write head++ or tail++.

However, we do have to worry about wrapping, and so encapsulate that worry in a method, which I called Increment.

Maybe I should have used the word "value". offset is the value we want to increment. We'll pass either head or tail to Increment, as in Increment(head) or Increment(tail).

To actually increment head, for example, we'd write
head = Increment(head).
To merely see if tail is one less than head, we'd write
if (Increment(tail) == head) {
// do something in this case
}

>> if (offset >= SIZE) offset = 0; //SIZE is just how big our array is, isn't it? Would be size()<SIZE better...
If tail, for example, is SIZE-1, then it is already at the physical end of the queue. The code begins by incrementing offset, so tail would == SIZE after the increment.

0

george08Author Commented:

That was tooo much.

If you can just post the queue(), from which i can go on? The offset() at the moment is too much.

I do understand the problem with wrapping and I do understand that this is a worry.

Maybe i do understand the combination of my queue() method together with the offset() better

We've said that a queue is empty if head == tail. Therefore, enqueue must not make head == tail. If the next position after the current tail position is == the head position, then there is no more room in the queue.

void QueueClass::qu(QueueElement* newElement) //ok
{
// Recognize a full queue
if (Increment(tail) == head) {
std::cout << "The queue is full" << std::endl;
// Add to a not-full queue
} else {
tail = Increment(tail);
queue[tail] = newElement;
}
}

0

george08Author Commented:

>>We've said that a queue is empty if head == tail. Therefore, enqueue must not make head == tail. If the next position after the >>current tail position is == the head position, then there is no more room in the queue.

OK, understood.

int QueueClass::Increment(int offset) {
offset++;
if (offset >= SIZE) offset = 0;
return offset;
}

void QueueClass::qu(QueueElement* newElement) //ok
{
// Recognize a full queue
if (Increment(tail) == head) {
std::cout << "The queue is full" << std::endl;
// Add to a not-full queue
} else {
tail = Increment(tail);
queue[tail] = newElement;
}
}

Got also that - looking good :-)
I do more study about the subject later on, you are giving excellent examples...

0

george08Author Commented:

Now to dequ()

if its empty, i do return i.e. a 0
else i do return the element which i dequeued?

Yes, you'll need to make a temporary copy of the head subscript, as you say.

>>headtmp==head;
This statement does comparison, not assignment. You need assignment.

As written, dequ returns the value of the head subscript, not the QueueElement. You want a
QueueElement* QueueClass::dequ()
that returns a queue element. So the code should
return queue[headtmp]
I would also use
head = Increment(head)
rather than
head++
due to the wrapping problem.

Since Int == QueueElement*, the statement
int QueueClass::dequ()
will probably work. However, it is confusing to the reader (or at least to me) and I suggest keeping your types consistent.

0

george08Author Commented:

Great

So this should be working?

#include <iostream>using namespace std;#define SIZE 20#include "queueel.h"class QueueClass { QueueElement* queue[SIZE]; int head, tail;public:QueueClass(); ~QueueClass(); void qu(QueueElement* newElement); QueueElement* dequ(); int size(); bool isEmpty(); int Increment(int offset);};QueueClass::QueueClass(): head(0) , tail(0){} // -1 is not correct init list is fineQueueClass::~QueueClass () {}int QueueClass::Increment(int offset) { offset++; if (offset >= SIZE) offset = 0; return offset;}void QueueClass::qu(QueueElement* newElement) //ok{ // Recognize a full queue if (Increment(tail) == head) { std::cout << "The queue is full" << std::endl; // Add to a not-full queue } else { tail = Increment(tail); queue[tail] = newElement; }}QueueElement* QueueClass::dequ(){ if (isEmpty()) {return NULL;} else { head++; return queue[head]; }}int QueueClass::size(){ int tempTail = (tail >= head) ? tail : tail + SIZE; int size = tempTail - head; return size; } bool QueueClass::isEmpty() { bool isEmpty = head == tail; if (isEmpty) cout << "Queue is empty\n"; return isEmpty; }

Problem 1. My qu example was incorrect. Need to reverse two lines
void QueueClass::qu(QueueElement* newElement) //ok
{
// Recognize a full queue
if (Increment(tail) == head) {
std::cout << "The queue is full" << std::endl;
// Add to a not-full queue
}
else {
queue[tail] = newElement; // Reversed this one
tail = Increment(tail); // ..with this one
}
}

because we want the first queue element to go into queue[0]

Last problem, dequ is incrementing head, without checking for wrapping, and then uses the incremented subscript to return
queue[head]
The immediate problem is that the value of head can become == SIZE, which makes it an invalid subscript value (out of range).

So the correct code would be

QueueElement* QueueClass::dequ()
{
if (isEmpty()) {return NULL;}
else
{
//head++;
//
//return queue[head];
int tempHead = head;
head = Increment(head);
return queue[tempHead];
}
}

This means that the queue is empty when the tail pointer is 1 less than the head pointer, where subtraction is cyclic.

That is, 0 - 1 == 19.

I suggest it is simpler to consider a queue to be empty when the head and tail pointers are equal. This would mean the constructor sets them both to the same value, likely 0.