PMG76
asked on
Circular linked Queue using 1 pointer
Please look over my Enqueue, DeQueue and Print methods carefully as these are the 3 methods that I am currently trying to test. In my test driver program if I enter a 9 and then an 8 for example. My cout statement is telling me that 8 was dequeued. In fact, the 9 should be listed as the item dequed since it was entered first. That is my first problem. Also, then after I dequeue an item, I call my Print method and it's telling me that it's empty when there should still be 1 more item in the queue.
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
using namespace std;
#include <new>
using std::bad_alloc;
//int item;
//------------------------ ---------- ---------- ---------- ---------- -
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue Type()
{
rear = NULL;
}
//------------------------ ---------- ---------- ---------- ---------- -
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue Type(const QueueType<ItemType> & right) {
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------ ---------- ---------- ---------- ---------- -
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul l() const
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException )
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu eType()
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE mpty()
{
while (!IsEmpty() )
{
Dequeue(rear->info);
}
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp ty() const
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::Enque ue(ItemTyp e newItem)
{
bool status = false;
NodeType *tempPtr = new NodeType;
tempPtr->info = newItem;
if ( IsEmpty() )
{
rear = tempPtr;
rear->next = tempPtr;
status = true;
}
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
rear = rear->next;
status = true;
}
return status;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::Deque ue(ItemTyp e & item)
{
bool status = false;
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
status = true;
}
else
{
rear->next = tempPtr->next;
status = true;
}
item = tempPtr->info;
}
else
{
cout << "The queue is empty " << endl;
status = false;
}
return status;
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print ()
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
cout << "The queue contains: ";
while ( tempPtr != rear )
{
cout << tempPtr->info << " ";
tempPtr = tempPtr->next;
}
cout << tempPtr->info << endl << endl;
}
else
cout << "The queue is empty." << endl << endl;
}
//assigns one queue to another
template<class ItemType>
QueueType<ItemType>& QueueType<ItemType>::opera tor=(const QueueType<ItemType> &right)
{
MakeEmpty();
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
Enqueue(rightPtr->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
}
#endif
#include <iostream>
using namespace std;
#include "queue.h"
int menu();
int main ()
{
system("clear");
int item;
int opt = 1;
bool status;
QueueType<int> q1, q2;
while ( opt > 0 && opt < 9 )
{
opt = menu();
switch(opt)
{
case 1: //Enqueue an item
cout << "Enter an integer to Enqueue: ";
cin >> item;
q1.Enqueue(item);
cout << item << " is enqueued." << endl << endl;
break;
case 2 : //Dequeue an item
status = q1.Dequeue(item);
if (q1.Dequeue(item))
{
cout << item << " has been removed from the Queue." << endl << endl;
}
else
cout << "There are no items to Dequeue." << endl << endl;
break;
case 3: // check for IsEmpty
break;
case 4: // check for IsFull
break;
case 5: // print the queue
q1.Print();
break;
case 6: //copy the queue
break;
case 7: //assign one queue to another
break;
case 8: // clear all items from the queue
break;
case 0: //quit the program
break;
}
}
return 0;
}
//menu function for the main menu of the program for user selection
int menu()
{
int opt = 1;
do
{
if ( opt < 0 || opt > 8 )
cout << "You have entered an invalid number." << endl;
cout << "Select one of the following options: " << endl;
cout << "\t1. Enqueue an item " << endl;
cout << "\t2. Dequeue an item " << endl;
cout << "\t3. Is queue empty? " << endl;
cout << "\t4. Is queue full? " << endl;
cout << "\t5. Print the queue " << endl;
cout << "\t6. Copy the queue " << endl;
cout << "\t7. Assign one queue to another " << endl;
cout << "\t8. Clear all items from the queue " << endl;
cout << "\t0. Quit the program " << endl;
cin >> opt;
}
while ( opt < 0 || opt > 8 );
return opt;
}
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
using namespace std;
#include <new>
using std::bad_alloc;
//int item;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
while (!IsEmpty() )
{
Dequeue(rear->info);
}
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::Enque
{
bool status = false;
NodeType *tempPtr = new NodeType;
tempPtr->info = newItem;
if ( IsEmpty() )
{
rear = tempPtr;
rear->next = tempPtr;
status = true;
}
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
rear = rear->next;
status = true;
}
return status;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::Deque
{
bool status = false;
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
status = true;
}
else
{
rear->next = tempPtr->next;
status = true;
}
item = tempPtr->info;
}
else
{
cout << "The queue is empty " << endl;
status = false;
}
return status;
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
cout << "The queue contains: ";
while ( tempPtr != rear )
{
cout << tempPtr->info << " ";
tempPtr = tempPtr->next;
}
cout << tempPtr->info << endl << endl;
}
else
cout << "The queue is empty." << endl << endl;
}
//assigns one queue to another
template<class ItemType>
QueueType<ItemType>& QueueType<ItemType>::opera
{
MakeEmpty();
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
Enqueue(rightPtr->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
}
#endif
#include <iostream>
using namespace std;
#include "queue.h"
int menu();
int main ()
{
system("clear");
int item;
int opt = 1;
bool status;
QueueType<int> q1, q2;
while ( opt > 0 && opt < 9 )
{
opt = menu();
switch(opt)
{
case 1: //Enqueue an item
cout << "Enter an integer to Enqueue: ";
cin >> item;
q1.Enqueue(item);
cout << item << " is enqueued." << endl << endl;
break;
case 2 : //Dequeue an item
status = q1.Dequeue(item);
if (q1.Dequeue(item))
{
cout << item << " has been removed from the Queue." << endl << endl;
}
else
cout << "There are no items to Dequeue." << endl << endl;
break;
case 3: // check for IsEmpty
break;
case 4: // check for IsFull
break;
case 5: // print the queue
q1.Print();
break;
case 6: //copy the queue
break;
case 7: //assign one queue to another
break;
case 8: // clear all items from the queue
break;
case 0: //quit the program
break;
}
}
return 0;
}
//menu function for the main menu of the program for user selection
int menu()
{
int opt = 1;
do
{
if ( opt < 0 || opt > 8 )
cout << "You have entered an invalid number." << endl;
cout << "Select one of the following options: " << endl;
cout << "\t1. Enqueue an item " << endl;
cout << "\t2. Dequeue an item " << endl;
cout << "\t3. Is queue empty? " << endl;
cout << "\t4. Is queue full? " << endl;
cout << "\t5. Print the queue " << endl;
cout << "\t6. Copy the queue " << endl;
cout << "\t7. Assign one queue to another " << endl;
cout << "\t8. Clear all items from the queue " << endl;
cout << "\t0. Quit the program " << endl;
cin >> opt;
}
while ( opt < 0 || opt > 8 );
return opt;
}
For information to the other experts. This is a follow-up of :
https://www.experts-exchange.com/questions/22907134/Circular-linked-Queue-using-1-pointer-to-the-rear.html
https://www.experts-exchange.com/questions/22907134/Circular-linked-Queue-using-1-pointer-to-the-rear.html
I see you added this to the else block in the EnQueue method now :
rear = rear->next;
You shouldn't have ... Just this is good :
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::Enque ue(ItemTyp e newItem)
{
bool status = false;
NodeType *tempPtr = new NodeType;
tempPtr->info = newItem;
if ( IsEmpty() )
{
rear = tempPtr;
rear->next = tempPtr;
status = true;
}
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
status = true;
}
return status;
}
rear = rear->next;
You shouldn't have ... Just this is good :
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::Enque
{
bool status = false;
NodeType *tempPtr = new NodeType;
tempPtr->info = newItem;
if ( IsEmpty() )
{
rear = tempPtr;
rear->next = tempPtr;
status = true;
}
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
status = true;
}
return status;
}
ASKER
I guess the first value is actually getting stored, but something in my Dequeue I suspect is not performing correctly and I'm lost as to what it is. It seems to be taking things off two at a time.
The queue contains: 9 8
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
2
8 has been removed from the Queue.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
5
The queue is empty.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
The queue contains: 9 8
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
2
8 has been removed from the Queue.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
5
The queue is empty.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
ASKER
Removing that line made it so that my cout is telling me it is dequing the right item, but it still seems to be taking two items from the queue. If i have a 9 and an 8 and deque 1 item it says it's empty.
The queue contains: 8 9
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
2
9 has been removed from the Queue.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
5
The queue is empty.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
The queue contains: 8 9
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
2
9 has been removed from the Queue.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
5
The queue is empty.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
ASKER
actually I guess it's not returning the right value. it's still not performing correctly.
The queue contains: 6 7 8 9
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
2
7 has been removed from the Queue.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
The queue contains: 6 7 8 9
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
2
7 has been removed from the Queue.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
ASKER
Another thing I noticed is that when I call the print method my items are not listed correctly. It should be listed the other way around. like 9 8 7 , not 7 8 9. Any ideas?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
BTW, if making it a stack you would need to change print function so that it prints rear->info before the loop (not after as it is now).
Did you also make the modification I mentioned ?
ASKER
I have a question about my copy constructor. I'm sure it's in my syntax. I'm not sure exactly how to set up this function in my test program. Here is what I have, but clearly not right.
case 6: //copy the queue
QueueType<int> q2(q1);
cout << "Original queue = " << endl;
q1.print();
cout << "Test of copy constructor: New queue: " << endl;
q2.print();
break;
case 6: //copy the queue
QueueType<int> q2(q1);
cout << "Original queue = " << endl;
q1.print();
cout << "Test of copy constructor: New queue: " << endl;
q2.print();
break;
>>>> Did you also make the modification I mentioned ?
As far as I see (now) your suggestion was to *not* changing the rear (thus making it a LIFO queue).
But the statement
rear = rear->next;
already was added in code of the previous question. It wasn't in the else branch but below the if/else block what had the same effect to turn a LIFO to a FIFO.
As far as I see (now) your suggestion was to *not* changing the rear (thus making it a LIFO queue).
But the statement
rear = rear->next;
already was added in code of the previous question. It wasn't in the else branch but below the if/else block what had the same effect to turn a LIFO to a FIFO.
>>>> Here is what I have, but clearly not right.
You have to turn 'print' by 'Print' and make curly brackets {} around the code of case 6
case 6:
{
...
}
break;
You must put it into a block so that the object q2 can be orderly destroyed.
Regards, Alex
You have to turn 'print' by 'Print' and make curly brackets {} around the code of case 6
case 6:
{
...
}
break;
You must put it into a block so that the object q2 can be orderly destroyed.
Regards, Alex
>> As far as I see (now) your suggestion was to *not* changing the rear (thus making it a LIFO queue).
You are absolutely right ... I got confused by the EnQueue and DeQueue method names lol (I'm more used to the conventional push and pop heh) ... my apologies :)
You are absolutely right ... I got confused by the EnQueue and DeQueue method names lol (I'm more used to the conventional push and pop heh) ... my apologies :)
ASKER
Thank you! Now, I'm trying to test my copy constructor and I get the following compile error with the following code:
case 7: //assign one queue to another
{
q1=q2;
cout << "Original queue = " << endl;
q1.Print();
cout << "Test of copy constructor: New queue: " << endl;
q2.Print();
}
break;
queue.h: In member function `QueueType<ItemType>& QueueType<ItemType>::opera tor=(const QueueType<ItemType>&) [with ItemType = int]':
prog5a.cpp:73: instantiated from here
queue.h:214: warning: control reaches end of non-void function
case 7: //assign one queue to another
{
q1=q2;
cout << "Original queue = " << endl;
q1.Print();
cout << "Test of copy constructor: New queue: " << endl;
q2.Print();
}
break;
queue.h: In member function `QueueType<ItemType>& QueueType<ItemType>::opera
prog5a.cpp:73: instantiated from here
queue.h:214: warning: control reaches end of non-void function
Add this line at the end of the operator= :
return *this;
return *this;
>>>> q1=q2;
I suppose that is the statement which is wrong as q2 wasn't defined yet.
You would need to create an empty queue q2 first and then make the assignment:
QueueType<int> q2; // empty queue
q2 = q1; // now assign q1
>>>> return *this;
The return value of operator= is a reference to the 'this' object. With that you could do
QueueType<int> q2, q3, q4; // empty queues
q2 = q3 = q4 = q1;
cause each of these operations returns a valid 'QueueType<int>&' (beginning from the right).
I suppose that is the statement which is wrong as q2 wasn't defined yet.
You would need to create an empty queue q2 first and then make the assignment:
QueueType<int> q2; // empty queue
q2 = q1; // now assign q1
>>>> return *this;
The return value of operator= is a reference to the 'this' object. With that you could do
QueueType<int> q2, q3, q4; // empty queues
q2 = q3 = q4 = q1;
cause each of these operations returns a valid 'QueueType<int>&' (beginning from the right).
ASKER
The queue contains: 9 8 7 6 5
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
2
8 has been removed from the Queue.
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program
5
The queue contains: 7 6 5
Select one of the following options:
1. Enqueue an item
2. Dequeue an item
3. Is queue empty?
4. Is queue full?
5. Print the queue
6. Copy the queue
7. Assign one queue to another
8. Clear all items from the queue
0. Quit the program