LINKED BASED AND ARRAY BASED QUEUES IN C++ (1 DRIVER FILE) Please show ran through a terminal

One example of a moveNthFront method which moved a particular element in the queue to the first position. For example, if queue1 object contained the elements {5, 11, 34, 67, 43, 55}, then after this call:

queue1.moveNthFront(3);

the order of elements would be {34, 5, 11, 67, 43, 55}. In that function, we utilized a temporary queue and the other built-in methods of the class to write code that was very generic and reusable. In fact, with only one slight change, the code worked for both the array based and link based classes.

In order to improve the efficiency of the moveNthFront method, write new versions of this method for both the array based and link based classes that do not use a temporary queue. In the array based class, you can directly manipulate the array elements to accomplish this task. In the link based class, you can update the pointers of individual nodes as well as the queueFront pointer.

You are provided with the class implementations for the array based and linked based queue. A driver file has also been provided with the same sequence of additions and deletions to the array based queue that were used in lab. You can do some preliminary testing with other data but that sequence will be used to test your code. The printQueue function is already available in both classes for testing. The function prototype and a blank definition of the function have been added to both classes. You just need to fill in the function.

Format your output so that the user of your program understands the values that were input and what was output for each operation. Make sure your program is properly documented and good programming standards are followed. You are required to follow C++ Style guide, which is available on Blackboard. Your program should have a user-friendly interface. Try your program with a variety of input values to determine it works properly.

//////////////////////////////////////// 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

///////////////////////////////////////////////// queueType.h ////////////////////////////////////////////////////

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;

}

////////////////////////////////////////////////// main.cpp //////////////////////////////////////////////////////////////

#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;

}