[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3095
  • Last Modified:

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 fine
QueueClass::~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;
 }

Open in new window

0
george08
Asked:
george08
  • 24
  • 20
5 Solutions
 
josgoodCommented:
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.
0
 
josgoodCommented:
(I'm taking things one at a time)
0
 
george08Author Commented:
Thanks for your answer

This was just a suggestions... since i was not sure.

Queue has to be FiFo

QueueClass::QueueClass():  head(0) , tail(0){}  <<<< done
0
Concerto Cloud for Software Providers & ISVs

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!

Learn how Concerto can help you.

 
josgoodCommented:
For the size method, do you intend this to be the capacity of the queue, which would be SIZE, or the number of elements on the queue?
0
 
george08Author Commented:
With my size(), i want to know how many elements are in my queue.
0
 
josgoodCommented:
OK, then you need to get the difference between the tail and head pointers.  Since the pointers can wrap, you'll need something like this

      int tempTail = (tail >= head) ? tail : tail + SIZE;
      int size = tempTail - head;

Does that make sense or should I explain further?
0
 
george08Author Commented:
please explain further.

But you are aware that i do have a static array and will not change it? with pointers you mean [0],[1]...[19]?

Thanks
0
 
george08Author Commented:
int tempTail = (tail >= head) ? tail : tail + SIZE;
      int size = tempTail - head;


is that the same as

int isEmpty(){

int tempTail

if(tail>=head){
 tmptail=tail;
}
else{
tmptail= tail+SIZE
}

return tmptail
}
0
 
josgoodCommented:
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)

Does that make sense?
   

0
 
george08Author Commented:
better... thanks :-)

is that then the acceptable soltution for

size(), not empty... ;-)

int size(){

int tempTail

if(tail>=head){
 tmptail=tail;
}
else{
tmptail= tail+SIZE
}

return tmptail
}
0
 
josgoodCommented:
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;
}

Open in new window

0
 
josgoodCommented:
That's the way we've defined it -- queue is empty if head == tail.

We don't have to do it that way -- could be defined as empty if the next increment of the tail value (taking wrapping into account) == head.

It's a matter of establishing a convention and then sticking to it.

With the definition we're using, isEmpty() can simply
   return head == tail;

size() needs to return the *difference* between tail and head.
0
 
george08Author Commented:
for verification: size() as posted above is correct?
is Empty() correct too?


bool isEmpty(){
if (head==tail){
return 1;
}
else{
return 0
}
}



I appreciate your good and fast guidance!!
0
 
josgoodCommented:
You're very welcome!

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?

0
 
josgoodCommented:
  int tempTail = tail + SIZE;
   if (tail >= head) tempTail = tail;
is one way.
0
 
josgoodCommented:
Here's an explanation of the ternary operator
http://en.wikipedia.org/wiki/%3F:
0
 
george08Author Commented:
got it.

What about isEmpty?
bool QueueClass::isEmpty()
 {
    if(size()==0) {
    cout << "Queue is empty\n";
    return 1;
    }
    else return 0;
 }

Open in new window

0
 
josgoodCommented:
That works fine.  I wrote it as
 bool QueueClass::isEmpty()
 {
    bool isEmpty = head == tail;
    if (isEmpty) cout << "Queue is empty\n";
    return isEmpty;
 }

but that's mostly a matter of taste.

I do recommend returning bool, as in "bool isEmpty", rather than 0 or 1, which are convertible to bool.

It makes for slightly less code and for slightly clearer code.
0
 
george08Author Commented:
Since I'm a bloddy beginner, i do focus on writing, not optimizing code ;-)

But thanks.

Now please to my bigger problem, the fearfull queue and dequeue...

Please ;-)
bool QueueClass::isEmpty()
 {
    if(size()==0) {
    cout << "Queue is empty\n";
    return isEmpty;
    }
    else return isEmpty;
 }

Open in new window

0
 
josgoodCommented:
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
0
 
josgoodCommented:
This raises the question:  How do I know enqueuing is working?

The answer, of course, is to test it.

I suggest

void Enqueue(QueueClass& q, int value) {
   QueueElement qe;
   qe.setData(value); q.qu(&qe); std::cout << "head = " << q.Head() << ", tail = " << q.Tail() << std::endl;
}


void main() {
   QueueClass q;
   std::cout << "New queue is " << (q.isEmpty() ? "empty" : "not empty") << std::endl;
   std::cout << "New queue size is " << q.size() << std::endl;
   Enqueue(q,10);
   std::cout << "Queue is " << (q.isEmpty() ? "empty" : "not empty") << std::endl;
   Enqueue(q,20);
   Enqueue(q,30);
   Enqueue(q,40);
   Enqueue(q,50);
   ..and so on until the queue is full
}
0
 
josgoodCommented:
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?
0
 
josgoodCommented:
Sorry, I leapt ahead too fast.

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


0
 
josgoodCommented:
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?

Correct?
0
 
josgoodCommented:
Yes.

The head subscript points to the element to return.  You'll have also have to increment head in preparation for the next dequ.
0
 
george08Author Commented:
Do I have to make a tmp copy of the "old" head to return it? because the "pointer" shows to the next element, not the old head...
Below correct?

int QueueClass::dequ()
{
  if (isEmpty()) {return 0;}
  else
  {
int headtmp;
headtmp==head;
 head++;
  return headtmp;
  }
}


0
 
george08Author Commented:
Int= QueueElement*

0
 
josgoodCommented:
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 fine
QueueClass::~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;
 }
 
 

Open in new window

0
 
josgoodCommented:
I'm looking at it.  There are a couple of problems...Be with you shortly.
0
 
george08Author Commented:
Thanks!
0
 
josgoodCommented:
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]
0
 
josgoodCommented:
Second problem.  You were right and I was wrong.  The Increment comparison should be
   offset > SIZE

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

My way cut the queue off one element short, so that we didn't put an element in queue[SIZE-1].
0
 
josgoodCommented:
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];
  }
}
0
 
josgoodCommented:
So you might ask, "How did he figure that out?"

The answer, again, is testing.  I have

void main() {
   QueueClass q;
   std::cout << "New queue is " << (q.isEmpty() ? "empty" : "not empty") << std::endl;
   std::cout << "New queue size is " << q.size() << std::endl;
   QueueElement qe1, qe2, qe3, qe4, qe5, qe6;
   qe1.setData(10);
   qe2.setData(20);
   qe3.setData(30);
   qe4.setData(40);
   qe5.setData(50);
   qe6.setData(60);
   
   q.qu(&qe1); std::cout << "head = " << q.Head() << ", tail = " << q.Tail() << ", value = " << qe1.getData() << std::endl;
   std::cout << "Queue is " << (q.isEmpty() ? "empty" : "not empty") << std::endl;
   q.qu(&qe2); std::cout << "head = " << q.Head() << ", tail = " << q.Tail() << ", value = " << qe2.getData() << std::endl;
   q.qu(&qe3); std::cout << "head = " << q.Head() << ", tail = " << q.Tail() << ", value = " << qe3.getData() << std::endl;
   q.qu(&qe4); std::cout << "head = " << q.Head() << ", tail = " << q.Tail() << ", value = " << qe4.getData() << std::endl;
   q.qu(&qe5); std::cout << "head = " << q.Head() << ", tail = " << q.Tail() << ", value = " << qe5.getData() << std::endl;
   q.qu(&qe6); std::cout << "head = " << q.Head() << ", tail = " << q.Tail() << ", value = " << qe6.getData() << std::endl;
   
   std::cout << "-------------------" << std::endl;
   Dequeue(q);
   Dequeue(q);
   Dequeue(q);
   Dequeue(q);
   Dequeue(q);
   Dequeue(q);
}

that runs the code through its paces -- I set SIZE = 5 for my testing.

This is an important thing to learn.  I cannot over stress it.

You don't know the code is working until you have test code to test it.
0
 
george08Author Commented:
Thanks.

As a last step, i do have to make a template out of it. I do open a new question, you want to help me there too, please?

This is the code i do have to transform


See below



#include <iostream>
using namespace std;
 
#define SIZE 20
 
class QueueClass {
  int queue[SIZE];
      int head, tail;
public:
 
 QueueClass(int, int);
  ~QueueClass();
 
 
  void qu(int num);
  int dequ();
  int size();
  bool isEmpty();
  int Increment(int offset);
  
};
QueueClass::~QueueClass () {}
QueueClass::QueueClass (int a, int b) {
  head = a;
  tail = b;
 
}
 
 
int QueueClass::Increment(int offset) {
   offset++;
   if (offset > SIZE) offset = 0;
   return offset;
}
 
void QueueClass::qu(int num) 
{
      // 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] = num;   // Reversed this one
         tail = Increment(tail);            // ..with this one
      }
}
 
 
int QueueClass::dequ()
{
  if (isEmpty()) {return 0;}
  else
  {
  //head++;
  //
  //return queue[head];
     int tempHead = head;
     head = Increment(head);
     return queue[tempHead];
  }
}
 
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;
 }
 
 
int main()
{
  QueueClass queue1(0,0);
 
	
	queue1.isEmpty();
	cout <<"size is " <<queue1.size() <<std::endl;
	queue1.qu(1);
	queue1.isEmpty();
	cout <<"size is " <<queue1.size() <<std::endl;
 
 
}

Open in new window

0
 
josgoodCommented:
Sure I can help you with that.

I appreciate you making it a new question.

0
 
george08Author Commented:
Helping each other is important....
;-)
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 24
  • 20
Tackle projects and never again get stuck behind a technical roadblock.
Join Now