Given:

queueType.h

//************************************************************* // Author: D.S. Malik // // This class specifies the basic operation on a queue as an // array. //************************************************************* template class queueType { public: bool isEmptyQueue() const; //Function to determine whether the queue is empty. //Postcondition: Returns true if the queue is empty, // otherwise returns false.

bool isFullQueue() const; //Function to determine whether the queue is full. //Postcondition: Returns true if the queue is full, // otherwise returns false.

void initializeQueue(); //Function to initialize the queue to an empty state. //Postcondition: The queue is empty.

Type front() const; //Function to return the first element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: If the queue is empty, the program // terminates; otherwise, the first element of the // queue is returned.

Type back() const; //Function to return the last element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: If the queue is empty, the program // terminates; otherwise, the last element of the queue // is returned.

void addQueue(const Type& queueElement); //Function to add queueElement to the queue. //Precondition: The queue exists and is not full. //Postcondition: The queue is changed and queueElement is // added to the queue.

void deleteQueue(); //Function to remove the first element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: The queue is changed and the first element // is removed from the queue.

queueType(int queueSize = 100); //Constructor

~queueType(); //Destructor void printQueue() const; void moveNthFront(int);

private: int maxQueueSize; //variable to store the maximum queue size int count; //variable to store the number of elements in the queue int queueFront; //variable to point to the first element of the queue int queueRear; //variable to point to the last element of the queue Type *list; //pointer to the array that holds the queue elements };

template bool queueType::isEmptyQueue() const { return (count == 0); } //end isEmptyQueue

template bool queueType::isFullQueue() const { return (count == maxQueueSize); } //end isFullQueue

template void queueType::initializeQueue() { queueFront = 0; queueRear = maxQueueSize - 1; count = 0; } //end initializeQueue

template Type queueType::front() const { assert(!isEmptyQueue()); return list[queueFront]; } //end front

template Type queueType::back() const { assert(!isEmptyQueue()); return list[queueRear]; } //end back

template void queueType::addQueue(const Type& newElement) { if (!isFullQueue()) { queueRear = (queueRear + 1) % maxQueueSize; //use the //mod operator to advance queueRear //because the array is circular count++; list [queueRear] = newElement; } else cout << "Cannot add to a full queue." << endl; } //end addQueue

template void queueType::deleteQueue() { if (!isEmptyQueue()) { count--; queueFront = (queueFront + 1) % maxQueueSize; //use the //mod operator to advance queueFront //because the array is circular } else cout << "Cannot remove from an empty queue" << endl; } //end deleteQueue

template queueType::queueType(int queueSize) { if (queueSize <= 0) { cout << "Size of the array to hold the queue must " << "be positive." << endl; cout << "Creating an array of size 100." << endl; maxQueueSize = 100; } else maxQueueSize = queueSize; //set maxQueueSize to queueSize

queueFront = 0; //initialize queueFront queueRear = maxQueueSize - 1; //initialize queueRear count = 0; list = new Type [maxQueueSize]; //create the array to //hold the queue elements } //end constructor

template queueType::~queueType() { delete [] list; }

template void queueType::printQueue() const { for (int i = 0; i < count; i++) { cout << list[(queueFront + i) % maxQueueSize] << " "; } cout << endl; return; }

template void queueType::moveNthFront(int newFront) {

return; }

&

linkedQueueType.h

//Header file linkedQueue.h

#ifndef NodeType #define NodeType

//Definition of the node template struct nodeType { Type info; nodeType *link; };

#endif

#ifndef H_linkedQueue #define H_linkedQueue

#include #include

using namespace std;

//************************************************************* // Author: D.S. Malik // // This class specifies the basic operations on a queue as a // linked list. //*************************************************************

template class linkedQueueType { public: const linkedQueueType& operator= (const linkedQueueType&); //Overload the assignment operator. bool isEmptyQueue() const; //Function to determine whether the queue is empty. //Postcondition: Returns true if the queue is empty, // otherwise returns false. bool isFullQueue() const; //Function to determine whether the queue is full. //Postcondition: Returns true if the queue is full, // otherwise returns false. void initializeQueue(); //Function to initialize the queue to an empty state. //Postcondition: queueFront = NULL; queueRear = NULL Type front() const; //Function to return the first element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: If the queue is empty, the program // terminates; otherwise, the first element of the // queue is returned. Type back() const; //Function to return the last element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: If the queue is empty, the program // terminates; otherwise, the last element of the // queue is returned. void addQueue(const Type& queueElement); //Function to add queueElement to the queue. //Precondition: The queue exists and is not full. //Postcondition: The queue is changed and queueElement is // added to the queue. void deleteQueue(); //Function to remove the first element of the queue. //Precondition: The queue exists and is not empty. //Postcondition: The queue is changed and the first element // is removed from the queue. void printQueue() const; // Output the content of the queue to the screen linkedQueueType(); //Default constructor linkedQueueType(const linkedQueueType& otherQueue); //Copy constructor ~linkedQueueType(); //Destructor void copyQueue(const linkedQueueType& otherQueue); // copy queue written by Yoav Kadosh (Therefore, be carefull!) void moveNthFront(int); private: nodeType *queueFront; //pointer to the front of the queue nodeType *queueRear; //pointer to the rear of the queue };

//Default constructor template linkedQueueType::linkedQueueType() { queueFront = NULL; //set front to null queueRear = NULL; //set rear to null } //end default constructor

template bool linkedQueueType::isEmptyQueue() const { return(queueFront == NULL); } //end

template bool linkedQueueType::isFullQueue() const { return false; } //end isFullQueue

template void linkedQueueType::initializeQueue() { nodeType *temp; while (queueFront!= NULL) //while there are elements left //in the queue { temp = queueFront; //set temp to point to the //current node queueFront = queueFront->link; //advance first to //the next node delete temp; //deallocate memory occupied by temp } queueRear = NULL; //set rear to NULL } //end initializeQueue

template void linkedQueueType::addQueue(const Type& newElement) { nodeType *newNode; newNode = new nodeType; //create the node newNode->info = newElement; //store the info newNode->link = NULL; //initialize the link field to NULL if (queueFront == NULL) //if initially the queue is empty { queueFront = newNode; queueRear = newNode; } else //add newNode at the end { queueRear->link = newNode; queueRear = queueRear->link; } }//end addQueue

template Type linkedQueueType::front() const { assert(queueFront != NULL); return queueFront->info; } //end front

template Type linkedQueueType::back() const { assert(queueRear!= NULL); return queueRear->info; } //end back

template void linkedQueueType::deleteQueue() { nodeType *temp; if (!isEmptyQueue()) { temp = queueFront; //make temp point to the //first node queueFront = queueFront->link; //advance queueFront delete temp; //delete the first node if (queueFront == NULL) //if after deletion the //queue is empty queueRear = NULL; //set queueRear to NULL } else cout << "Cannot remove from an empty queue" << endl; }//end deleteQueue

//Destructor template linkedQueueType::~linkedQueueType() { initializeQueue(); } //end destructor

template void linkedQueueType::copyQueue (const linkedQueueType& otherQueue) { nodeType *newNode, *current, *last; if (queueFront != NULL) //if stack is nonempty, make it empty initializeQueue(); if (otherQueue.queueFront == NULL) queueFront = NULL; else { current = otherQueue.queueFront; //set current to point //to the stack to be copied //copy the stackTop element of the stack queueFront = new nodeType; //create the node queueFront->info = current->info; //copy the info queueFront->link = NULL; //set the link field of the //node to NULL last = queueFront; //set last to point to the node current = current->link; //set current to point to //the next node //copy the remaining stack while (current != NULL) { newNode = new nodeType; newNode->info = current->info; newNode->link = NULL; last->link = newNode; last = newNode; current = current->link; }//end while queueRear = last; }//end else }

template void linkedQueueType::printQueue() const { nodeType *temp; temp = queueFront; while(temp != NULL) { cout << temp->info << " "; temp = temp->link; } cout << endl; }

template const linkedQueueType& linkedQueueType::operator= (const linkedQueueType& otherQueue) { if (this != &otherQueue) //avoid self-copy copyQueue(otherQueue); return *this; } //end assignment operator

//copy constructor template linkedQueueType::linkedQueueType(const linkedQueueType& otherQueue) { queueFront = NULL; copyQueue(otherQueue); }//end copy constructor

template void linkedQueueType::moveNthFront(int newFront) {

return; }

#endif

&

main.cpp

//*************************************************************** // Put the program prologue comments here. // // Your new methods in the two classes should // also be well documented. //*************************************************************** #include #include "linkedQueueType.h" #include "queueType.h"

using namespace std;

int main() { // *********** Array based *********** queueType array_queue1(5); array_queue1.addQueue(2); array_queue1.addQueue(4); array_queue1.addQueue(6); array_queue1.addQueue(8); array_queue1.addQueue(10); array_queue1.deleteQueue(); array_queue1.deleteQueue(); array_queue1.deleteQueue(); array_queue1.addQueue(12); array_queue1.addQueue(14); array_queue1.addQueue(16); array_queue1.printQueue(); // Complete the new version of the moveNthFront // method in the array based class and test it below. // What should the print statement display? array_queue1.moveNthFront(3); array_queue1.printQueue();

// *********** Link based *********** linkedQueueType linked_queue1; linked_queue1.addQueue(1); linked_queue1.addQueue(3); linked_queue1.addQueue(5); linked_queue1.addQueue(7); linked_queue1.addQueue(9); linked_queue1.printQueue(); // Complete the new version of the moveNthFront // method in the link based class and test it below. // What should the print statement display? linked_queue1.moveNthFront(3); linked_queue1.printQueue(); return 0; }

Write versions for both the array based and link based classes that do not use a temporary queue. Hint: In the array based class, you can directly manipulate the array elements to accomplish this task. Hint: In the link based class, you can update the pointers of individual nodes as well as the queueFront pointer.