Working With Queue (COMPLETE EITHER 2B OR 2C) Complete the following exercises u
ID: 3808528 • Letter: W
Question
Working With Queue (COMPLETE EITHER 2B OR 2C)
Complete the following exercises using the cs20::Queue class presented in class.
1. Create a QueueIterator class that can be used to iterate thru the contents of a Queue. Using the ListIterator class as a guide, the QueueIterator class should support the following public interface by you adding the following methods to the QueueIterator class:
Modify the Queue class so instances have the ability to create iterators by adding the method to the Queue class:
Create a test driver program that exercises each of these exercises to satisfy yourself that your implementation is correct. For example, you should print the Queue before and after invoking the operation.
2. Create a new method on the Queue class which can be used to determine if a value on the Queue has been duplicated. That means this new operation should return true when the parameter passed is found more than once on the Queue. This new operation of the Queue class should have the signature:
Because it has been marked const, this method is saying that it is read-only. When your implementation runs, you won't be able to actually change any data members of the Queue passed to your method. Create a test driver program that exercises each of these exercises to satisfy yourself that your implementation is correct. For example, you should print the Queue before and after invoking the operation.
TESTING HINT:
Run the methods: enqueue( 3 ); enqueue( 2 ); enqueue( 1 ); Print the queue. What should it look like?
Run the method: isDuplicated( 1 ). It should return false. Does it?
Run the method: isDuplicated( 3 ). It should return false. Does it?
Run the methods: enqueue( 4 ); enqueue( 100 ); enqueue( 1 ); Print the queue. What should it look like?
Run the method: isDuplicated( 1 ). It should return true. Does it?
Run the method: isDuplicated( 0 ). It should return false. Does it?
Run the methods: dequeue(); dequeue();
Print the queue. What should it look like?
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
here is the code:
QueueNode.cpp
#ifndef QUEUENODE_CPP
#define QUEUENODE_CPP
#include "QueueNode.h"
namespace cs20 {
template <class Object>
QueueNode<Object>::QueueNode( const Object& theElement,
QueueNode<Object> * node ) {
element = theElement;
next = node;
}
template <class Object>
const Object& QueueNode<Object>::getElement() const {
return( element );
}
template <class Object>
QueueNode<Object>* QueueNode<Object>::getNext() const {
return( next );
}
template <class Object>
void QueueNode<Object>::setNext( QueueNode<Object> * node ) {
next = node;
}
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
QueueMenu.cpp
// Menu.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include "Queue.h"
#include "EmptyQueue.h"
#include "QueueNode.h"
#include "Queue.cpp"
#include "QueueNode.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, ENQUEUE, ISEMPTY, DEQUEUE, GETFRONT, QUIT, PRINT };
CHOICE menu();
int main(int argc, char* argv[]) {
int value;
Queue<int> q;
CHOICE choice;
do {
choice = menu();
switch( choice ) {
case MAKEEMPTY:
q.makeEmpty();
break;
case ISEMPTY:
if (q.isEmpty()) {
cout << "queue is empty" << endl;
}
else {
cout << "queue is not empty" << endl;
}
break;
case DEQUEUE:
try {
value = q.dequeue();
cout << "Here's the value dequeued: ";
cout << value << endl;
} catch( EmptyQueue eq ) {
cout << "You silly... don't try dequeueing an empty queue!" << endl;
}
break;
case GETFRONT:
try {
value = q.getFront();
cout << "Here's the value returned from getFront: ";
cout << value << endl;
} catch( EmptyQueue eq ) {
cout << "You silly... don't try gettingFront an empty queue!" << endl;
}
break;
case ENQUEUE:
cout << "Please provide int to enqueue: ";
cin >> value;
q.enqueue( value );
break;
case PRINT:
q.printQueue( cout );
cout << endl;
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty I(s)Empty (E)nqueue (D)equeue (G)etFront (P)rint (Q)uit: " << endl;
cin >> choice;
switch( choice ) {
case 'E':
case 'e':
result = ENQUEUE;
break;
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'D':
case 'd':
result = DEQUEUE;
break;
case 'G':
case 'g':
result = GETFRONT;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'P':
case 'p':
result = PRINT;
break;
}
return( result );
}
void sample() {
Queue<int> q1;
Queue<int> q2;
cout << "making q1" << endl;
q1.enqueue( 1 );
q1.enqueue( 2 );
cout << "print q1" << endl;
q1.printQueue( cout );
cout << endl;
cout << "q2 = q1" << endl;
q2 = q1;
cout << "print q2" << endl;
q2.printQueue( cout );
cout << endl;
q1.dequeue();
cout << "dequeue q1" << endl;
cout << "print q2" << endl;
q2.printQueue( cout );
cout << endl;
cout << "print q1" << endl;
q1.printQueue( cout );
cout << endl;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Queue.cpp
#ifndef QUEUE_CPP
#define QUEUE_CPP
#include "Queue.h"
namespace cs20 {
template <class Object>
Queue<Object>::Queue() {
frontNode = nullptr;
backNode = nullptr;
}
template <class Object>
Queue<Object>::Queue( const Queue<Object>& rhs ) {
frontNode = nullptr;
backNode = nullptr;
*this = rhs;
}
template <class Object>
Queue<Object>::~Queue() {
makeEmpty();
// when empty, frontNode and backNode will already be null
}
template <class Object>
bool Queue<Object>::isEmpty() const {
return( (frontNode == nullptr) );
}
template <class Object>
void Queue<Object>::makeEmpty() {
while (!isEmpty()) {
dequeue();
}
}
template <class Object>
void Queue<Object>::enqueue( const Object& data ) {
QueueNode<Object>* newNode = new QueueNode<Object>( data );
if (isEmpty()) {
frontNode = newNode;
backNode = newNode;
}
else {
backNode->setNext( newNode );
backNode = backNode->getNext();
}
}
template <class Object>
const Object Queue<Object>::dequeue() {
Object frontData = getFront();
QueueNode<Object> * oldFront = frontNode;
frontNode = frontNode->getNext();
delete oldFront;
return( frontData );
}
template <class Object>
const Object& Queue<Object>::getFront() const {
if (isEmpty()) {
throw EmptyQueue();
}
return( frontNode->getElement() );
}
// Deep copy of linked Queue
template <class Object>
const Queue<Object>& Queue<Object>::operator =( const Queue<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
QueueNode<Object> * rhsFrontNode = rhs.frontNode;
while( rhsFrontNode != nullptr) {
enqueue( rhsFrontNode->getElement() );
rhsFrontNode = rhsFrontNode->getNext();
}
}
return( *this );
}
template <class Object>
std::ostream& Queue<Object>::printQueue( std::ostream& outs ) {
if (isEmpty()) {
outs << "Empty Queue";
}
else {
outs << "FRONT: ";
QueueNode<Object> * node = frontNode;
while( node != nullptr) {
outs << node->getElement();
outs << " ";
node = node->getNext();
}
outs << ":BACK";
}
return( outs );
}
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
#include "QueueNode.h"
#include "EmptyQueue.h"
namespace cs20 {
template <class Object>
class Queue {
public:
Queue();
Queue( const Queue& rhs );
~Queue();
bool isEmpty() const;
void makeEmpty();
void enqueue( const Object& data );
const Object dequeue();
const Object& getFront() const;
const Queue& operator =( const Queue& rhs );
std::ostream& printQueue( std::ostream& outs );
private:
QueueNode<Object> * frontNode;
QueueNode<Object> * backNode;
};
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
QueueNode.h
#ifndef QUEUENODE_H
#define QUEUENODE_H
#include <iostream>
namespace cs20 {
template <class Object>
class QueueNode {
public:
QueueNode( const Object& theElement = Object(), QueueNode * node = nullptr );
// these accessors and mutators are called
// from Queue class
// no public methods expose QueueNode instances
// outside the Queue class
const Object& getElement() const;
QueueNode* getNext() const;
void setNext( QueueNode * node );
private:
Object element;
QueueNode* next;
};
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
EmptyQueue.cpp
#include "EmptyQueue.h"
namespace cs20 {
EmptyQueue::EmptyQueue( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
EmptyQueue.h
#ifndef EMPTYQUEUE_H
#define EMPTYQUEUE_H
#include <iostream>
#include <string>
namespace cs20 {
class EmptyQueue : public std::logic_error {
public:
EmptyQueue( const std::string& msg = "" );
};
}
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Explanation / Answer
template<class Object>
int compare(Object a, Object b)
{
if (a < b) return -1;
if (b < a) return 1;
return 0;
}
bool isDuplicated( const Object & o ) const {
int cnt = 0;
QueueNode<Object> * node = frontNode;
// loop through complete queue and check if there is a match
while( node != nullptr) {
if(compare(node->getElement(), o) == 0) {
cnt++;
// if cnt is more than one, then duplicate
if(cnt > 1) {
return true;
}
}
node = node->getNext();
}
return false;
}
We need to add one more case in switch case of QueueMenu.cpp as
Case CHECK_DUPLICATE:
cout << “Please provide int value to check for duplicate “;
cin >> value;
bool ans = isDuplicated(value);
if(ans) {
cout << “Given value is duplicate in queue.”;
} else {
cout << “Given value is not duplicate in queue.”;
}
break;
For testing purpose, run
>> g++ queue.cpp
>> ./a.out
You will be given a menu, select enqueue to insert few values and then select check_duplicate to check if any value is duplicate or not.
Also, use print from time to time to see contents of queue.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.