Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Explanation about Queues

Posted on 1999-06-27
11
Medium Priority
?
418 Views
Last Modified: 2010-04-02
I have the following program  or function to count, that receives a queue and returnsan integer count of the number of elements in the queue. The queue should not be destroyed, and the walls of the ADT should not be violated.

// ********************************************************
// Implementation file QueueA.cpp for the ADT queue.
// Circular array-based implementation.
// The array has indexes to the front and rear of the
// queue. A counter tracks the number of items currently
// in the queue.
// ********************************************************

#include "QueueA.h"  // header file

// constructors and destructor:
queueClass::queueClass():
                                 Front(0), Rear(MAX_QUEUE-1), Count(0)
{
}  // end default constructor

queueClass::queueClass(const queueClass& Q):
                                 Front(Q.Front), Rear(Q.Rear),
Count(Q.Count)
{  for (int Index = 0; Index < Q.Count; ++Index)
                Items[Index] = Q.Items[Index];
}  // end copy constructor

queueClass::~queueClass()
{
}  // end destructor

boolean queueClass::QueueIsEmpty()
{
        return boolean(Count == 0);
}

void queueClass::QueueAdd(queueItemType NewItem,

boolean& Success)
{
        Success = boolean(Count < MAX_QUEUE);

        if (Success)
        {  // queue is not full; insert item
                Rear = (Rear+1) % MAX_QUEUE;
                Items[Rear] = NewItem;
                ++Count;
        }  // end if
}  // end QueueAdd

void queueClass::QueueRemove(boolean& Success)
{
        Success = boolean(!QueueIsEmpty());

        if (Success)
        {  // queue is not empty; remove front
                Front = (Front+1) % MAX_QUEUE;
                --Count;
        }  // end if
}  // end QueueRemove

void queueClass::GetQueueFront(queueItemType& QueueFront,

boolean& Success)
{
        Success = boolean(!QueueIsEmpty());

        if (Success)
                // queue is not empty; retrieve front
                QueueFront = Items[Front];
}  // end GetQueueFront

void queueClass::QueueCount(queueItemType& QueueFront,

boolean& Success)
{
        Success = boolean(Count == 0);

        if (Success)
                // queue is not empty; retrieve front
                QueueFront = Items[Front];
                ++Count
}  // end QueueCount
// End of implementation file.

This program or implementation is right???
So, if the pointer-based queueClass were used , would the queue be destroyed by my code??? I need an explanation.please...

Thanks for your support,

Jairo Cardenas
Network Manager
Cucuta - Colombia
South America
0
Comment
Question by:jcardenas
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 3
  • 2
11 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 1198562
Since this is for an assingment, we can provide only limited help, but that seems to be all you are asking for anyways.
*************************
It would help if you posted the declaration of the queue class, which is probably in the .h file.
*************************
The copy constructor has a flaw.  It sets Frpnt and Rear to be copies of the Front and Rear from the source queue. That is fine, but it copies the items into its array starting at the first position (index 0).  Thus the items might be moved to a different location from where they were in the source array.  (That also is fine, but if you do that, you have to set front and rear differently.  i.e. either could okay, but then the other is wrong.)
**********************
The count function seems strange.  what is it suposed to do?  I would think it would be supposed to return the number of items in the queue.  It doesn't do that at all.
*************************
>>  So, if the pointer-based queueClass were used
What do you mean by that.?  What pointer based queueclass?

0
 

Author Comment

by:jcardenas
ID: 1198563
That is not a assingment, i am studying C++ by self,  i put the .h file for this implementation.

/ ********************************************************
// Header file QueueA.h for the ADT queue.
// Array-based implementation.
// ********************************************************
const int MAX_QUEUE = 50;   // maximum-size-of-queue;
#ifndef QTYPE
typedef int queueItemType;  // desired-type-of-queue-item
#define QTYPE
#endif

#include "boolean.h"

class queueClass
{
public:
// constructors and destructor:
      queueClass();
      queueClass(const queueClass& Q);
      ~queueClass();

// queue operations:
      boolean QueueIsEmpty();
   void QueueAdd(queueItemType NewItem, boolean& Success);
      void QueueRemove(boolean& Success);
   void GetQueueFront(queueItemType& QueueFront,
                                           boolean& Success);

private:
   queueItemType Items[MAX_QUEUE];
   int           Front;
      int           Rear;
   int           Count;
};  // end class
// End of header file.

This program is in my C++ Book, and have some coments in the same page so:
The function Count receives a queue and returns an integer count of the number of elements in the queue. And have a question or coments, so if the pointer-based queueClass were used, would the queue be destroyed by the code??

The program for pointer-based queueClass exist in my book and is the following:

// *********************************************************
// Implementation file QueueP.cpp for the ADT queue.
// Pointer-based implementation.
// *********************************************************
#include "QueueP.h"  // header file
#include <stddef.h>  // for NULL

// The queue is implemented as a circular linked list
// with one external pointer to the rear of the queue.
struct queueNode
{  queueItemType Item;
   ptrType       Next;
};  // end struct

queueClass::queueClass() : Rear(NULL)
{
}  // end constructor

queueClass::queueClass(const queueClass& Q)
{  // Implementation left as an exercise (Exercise 5).
}  // end copy constructor

queueClass::~queueClass()
{
      boolean Success;

      while (!QueueIsEmpty())
      QueueRemove(Success);
  // Assertion: Rear == NULL
}  // end destructor

boolean queueClass::QueueIsEmpty()
{
   return boolean(Rear == NULL);
}  // end QueueIsEmpty

void queueClass::QueueAdd(queueItemType NewItem,
                          boolean& Success)
{
   // create a new node
      ptrType NewFrontPtr = new queueNode;

   Success = boolean(NewFrontPtr != NULL);
   if (Success)
      {  // allocation successful; set data portion of new node
      NewFrontPtr->Item = NewItem;

      // insert the new node
            if (QueueIsEmpty())
         // insertion into empty queue
         NewFrontPtr->Next = NewFrontPtr;

            else
      {  // insertion into nonempty queue
         NewFrontPtr->Next = Rear->Next;
         Rear->Next = NewFrontPtr;
            }  // end if

      Rear = NewFrontPtr;  // new node is at rear
   }  // end if
}  // end QueueAdd

void queueClass::QueueRemove(boolean& Success)
{
      Success = boolean(!QueueIsEmpty());

   if (Success)
   {  // queue is not empty; remove front
            ptrType FrontPtr = Rear->Next;
      if (FrontPtr == Rear)   // special case?
         Rear = NULL;         // yes, one node in queue
      else
                  Rear->Next = FrontPtr->Next;

      FrontPtr->Next = NULL;  // defensive strategy
      delete FrontPtr;
      }  // end if
}  // end QueueRemove

void queueClass::GetQueueFront(queueItemType& QueueFront,
                                                             boolean& Success)
{
   Success = boolean(!QueueIsEmpty());

      if (Success)
      // queue is not empty; retrieve front
      QueueFront = Rear->Next->Item;
}  // end GetQueueFront
// End of implementation file.

I need a explanation about that. This code is right???

Thanks,

Jairo
0
 
LVL 22

Expert Comment

by:nietod
ID: 1198564
>> And have a question or coments, so if the
>> pointer-based queueClass were used, would
>> the queue be destroyed by the code??
This doesn't make any sense.  There is no universal term like "pointer-based queueClass".  so I don't know what you mean by that.  You might mean a queue that stores pointers to the data, rather than storing the data directly.  You might mean a queue that stores the data using a linked list, which uses pointers, rather than an array.  I have no Idea what you mean.  Can you be more specific?

>>would the queue be destroyed by the code
Do you really mean "destroyed".  No.  an object is destroyed only when it is no longer needed.  You pretty much can't mess that up in C++.  But do you mean something else?  do you mean does the data in the queue get destroyed?  when? it does when the queue object itself is destroyed.
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 22

Expert Comment

by:nietod
ID: 1198565
Oh I see.  The queue you posted the 2nd time uses a linked list.  (pointers are used to maintain the linked list.)

The destructor for that queue will correctly destroy all the items in the queue.

some suggestions:

make QueueAdd() return a boolean value instead of taking it as parameter, like
boolean queueClass::QueueAdd(queueItemType NewItem)

Same with QueueRemove() and GetQueueFront().
0
 

Author Comment

by:jcardenas
ID: 1198566
Mr Nietod, thanks for your excellent support,  is clear now that the pointer based queue uses a linked list and the destructor for that queue destroy the queue.

About the code 1(queue array-based in my example) the function Count is right??
Really this function returns an integer count of the number of elements in the queue??

void queueClass::QueueCount(queueItemType& QueueFront,

                boolean& Success)
                {
                        Success = boolean(Count == 0);

                        if (Success)
                                // queue is not empty; retrieve front
                                QueueFront = Items[Front];
                                ++Count
                }  // end QueueCount

Thanks,


Jairo
0
 
LVL 22

Expert Comment

by:nietod
ID: 1198567
I'm not sure what you are asking/telling me.  (we have a bit of a language barrier).  But as I said before I don't think that function is right.  here are some problems I see.

A.  The function does not return the count in any way.  It should do this by returning "int" instead of "void"  but it could also do this by having an int parameter passed as a reference ("int &").  But I would recommend returning an "int"

B the function has a "QueueItemType &" parameter.  This does not seem to be needed for the purpose of this procedure.  This procedure is called to determine the number of items in the queue.  Why would the caller need to pass a QueueItemType in order to determine the number of items in the queue?

C.  The logic of the procedure seems incorrect.  First of all the queue has a member called "Count".  This is the number of items in the queue, so you just need to return this member.  It seemd weird that you would try to: get an item from the arrray in this process and alter count in this process.

********************
Another thing to consider about the linked list-based queue class.  It will have a memory leak if you use its copy constructor or use its operator =.  This is often the case when classes maintain pointers.  The default copy construtor and the default operator =, usually work well for classes without pointers and usually work incorrectly for classes with pointers.  Such is the case here.  You may want to write a copy constructor (already started in your code) and an operator = for this class.
0
 

Author Comment

by:jcardenas
ID: 1198568
Mr. Nietod, i am telling about your explanation and asking for the count function; excuse me please...Ok, your explanation is good and as exercise i will write the new code for the function Count.

Thanks for your time,

Jairo
0
 
LVL 3

Accepted Solution

by:
Laminamia063099 earned 240 total points
ID: 1198569
El algorithm que esta usando parece bien.  La funcion "count" necesita seguir el siguiente:
 
int queueClass::QueueCount()
{
    return count;
}  

Puede devolver este numero. Es por esta razon "the class" esta guardando el numero "count"
0
 
LVL 22

Expert Comment

by:nietod
ID: 1198570
laminamia, what are you doing.  I already mentioned that--and lots more.    I said

"First of all the queue has a member called "Count".  This is the
number of items in the queue, so you just need to return this member."

You don't post another expert's answer as your own.    Do you honestly think you deseve credit for this question?
0
 
LVL 3

Expert Comment

by:Laminamia063099
ID: 1198571
Sorry, I missed that.  I'm not trying to steal your answer, just stating the obvious that I saw.  (Their were a lot of comments, I didn't want to read them all when I saw an answer).

Laminamia
0
 
LVL 22

Expert Comment

by:nietod
ID: 1198572
Alright.  In the future, be sure to read all the comments before responding....
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
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 learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

721 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