Solved

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

Posted on 2008-06-22
44
3,030 Views
Last Modified: 2010-08-05
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
Comment
Question by:george08
  • 24
  • 20
44 Comments
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
(I'm taking things one at a time)
0
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
With my size(), i want to know how many elements are in my queue.
0
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

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

0
 
LVL 13

Expert Comment

by:josgood
Comment Utility
  int tempTail = tail + SIZE;
   if (tail >= head) tempTail = tail;
is one way.
0
 
LVL 13

Expert Comment

by:josgood
Comment Utility
Here's an explanation of the ternary operator
http://en.wikipedia.org/wiki/%3F:
0
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 
LVL 13

Expert Comment

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

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Accepted Solution

by:
josgood earned 500 total points
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
>>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
 

Author Comment

by:george08
Comment Utility
Now to dequ()

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

Correct?
0
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
Int= QueueElement*

0
 
LVL 13

Assisted Solution

by:josgood
josgood earned 500 total points
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
I'm looking at it.  There are a couple of problems...Be with you shortly.
0
 

Author Comment

by:george08
Comment Utility
Thanks!
0
 
LVL 13

Assisted Solution

by:josgood
josgood earned 500 total points
Comment Utility
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
 
LVL 13

Assisted Solution

by:josgood
josgood earned 500 total points
Comment Utility
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
 
LVL 13

Assisted Solution

by:josgood
josgood earned 500 total points
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
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
 

Author Comment

by:george08
Comment Utility
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
 
LVL 13

Expert Comment

by:josgood
Comment Utility
Sure I can help you with that.

I appreciate you making it a new question.

0
 

Author Comment

by:george08
Comment Utility
Helping each other is important....
;-)
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

763 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now