Data Structures using C++

Consider the following class

#ifndef LINKEDQUEUETYPE_H

#define LINKEDQUEUETYPE_H

#include

#include

#include

#include "QueueADT.h"

using namespace std;

// Definition of the node

template

struct NodeType

{

ItemType info;

NodeType *next;

};

template

class LinkedQueueType: public QueueADT

{

public:

// Constructor

LinkedQueueType();

// Default constructor.

// Post: An empty queue has been created. queueFront = NULL;

// queueBack = NULL;

LinkedQueueType(const LinkedQueueType& otherQueue);

// Copy constructor for deep copy of the linked implementation

// of queues.

// Destructor

~LinkedQueueType();

// Delete all the queue items.

// Post: All the items of the queue are removed.

// Action responsibilities

void resetQueue();

// Reset the queue to an empty queue.

// Post: Queue is empty. queueFront = NULL; queueBack = NULL;

void add(const ItemType& newItem);

// Function to add newItem to the queue.

// Pre: The queue exists and is not full.

// Post: The queue is changed and newItem is added to the

// back of the queue.

void remove();

// Function to remove the first element of the queue.

// Pre: The queue exists and is not empty.

// Post: The queue is changed and the first (i.e., front) item is

// removed from the queue.

// Knowledge responsibilities

bool isEmpty() const;

// Post: Returns true if queue is empty; false otherwise.

bool isFull() const;

// Post: Returns true if there is room for another item;

// false otherwise.

ItemType front() const;

// Function to return the first element of the queue.

// Pre: The queue exists and is not empty.

// Post: If the queue is empty, the program terminates; otherwise,

// the first element of the queue is returned.

ItemType back() const;

// Function to return the last element of the queue.

// Pre: The queue exists and is not empty.

// Post: If the queue is empty, the program terminates; otherwise,

// the last element of the queue is returned.

// Operator overloading

const LinkedQueueType& operator=

(const LinkedQueueType& otherQueue);

// Overload the assignment operator.

protected:

NodeType *queueFront; // pointer to the front of the queue

// (pointing to first node)

NodeType *queueBack; // pointer to the back of the queue

// (pointing to last node)

private:

void copyQueue(const LinkedQueueType& otherQueue);

// Function to make a copy of otherQueue.

// A deep copy of otherQueue is created and assigned to this queue.

};

//**************************************************************

template

LinkedQueueType::LinkedQueueType()

{

queueFront = NULL;

queueBack = NULL;

}

//**************************************************************

template

LinkedQueueType::LinkedQueueType

(const LinkedQueueType& otherQueue)

{

queueFront = NULL;

queueBack = NULL;

copyQueue(otherQueue);

}

//**************************************************************

template

LinkedQueueType::~LinkedQueueType()

{

resetQueue();

}

//**************************************************************

template

void LinkedQueueType::resetQueue()

{

NodeType *temp; // pointer to delete the node

while ( queueFront != NULL ) // while there are items in queue

{

temp = queueFront; // set temp to point to the current node

queueFront = queueFront->next; // advance queueFront to the next

// node

delete temp; // deallocate memeory occupied by temp

}

queueBack = NULL;

}

//**************************************************************

template

void LinkedQueueType::add(const ItemType& newItem)

{

NodeType *newNode; // pointer to create the new node

try

{

newNode = new NodeType; // create the node

newNode->info = newItem; // store newItem in the node

newNode->next = NULL;

if (queueFront == NULL) // if initially the queue is empty

{

queueFront = newNode;

queueBack = newNode;

}

else

{

queueBack->next = newNode;

queueBack= queueBack->next;

}

}

catch(bad_alloc)

{

cout << "ERROR: Cannot allocate memory! ";

exit(EXIT_FAILURE);

}

}

//**************************************************************

template

void LinkedQueueType::remove()

{

NodeType *temp; // pointer to deallocate memory

if ( !isEmpty() )

{

temp = queueFront; // set temp to point to the first node

queueFront = queueFront->next; // advance queueFront to the

// next node

delete temp; // delete the first node

if ( queueFront == NULL ) // if after deletion the queue is empty

queueBack = NULL; // set queueBack to NULL

}

else

cout << "Cannot remove from an empty queue." << endl;

}

//**************************************************************

template

bool LinkedQueueType::isEmpty() const

{

return ( queueFront == NULL );

}

//**************************************************************

template

bool LinkedQueueType::isFull() const

{

NodeType *newNode; // a testing node to see if there

// is more room

try

{

newNode = new NodeType;

delete newNode;

return false; //more room available, not full

}// end try

catch (bad_alloc)

{

return true; // no more room available

}

}

//**************************************************************

template

ItemType LinkedQueueType::front() const

{

if ( !isEmpty() )

return queueFront->info; // return the first item

else // if queue is empty, terminate the program

{

cout << "ERROR: Cannot return first item from an empty queue! ";

exit(EXIT_FAILURE);

}

}

//**************************************************************

template

ItemType LinkedQueueType::back() const

{

if ( !isEmpty() )

return queueBack->info; // return the last item

else // if queue is empty, terminate the program

{

cout << "ERROR: Cannot return last item from an empty queue! ";

exit(EXIT_FAILURE);

}

}

//**************************************************************

template

const LinkedQueueType& LinkedQueueType::operator=

(const LinkedQueueType& otherQueue)

{

if ( this != &otherQueue ) // avoid self-copying

copyQueue(otherQueue);

return *this;

}

//**************************************************************

template

void LinkedQueueType::copyQueue

(const LinkedQueueType& otherQueue)

{

NodeType *newNode, *current;

if ( queueFront != NULL ) // if queue is nonempty, make it empty

resetQueue();

if ( otherQueue.queueFront != NULL ) // if otherQueue is nonempty

{

try

{

current = otherQueue.queueFront; // set current to point to

// the queue to be copied

// copy the queueFront item of the queue

queueFront = new NodeType; // create the node

queueFront->info = current->info; // copy the info

queueFront->next = NULL; // set next to NULL

queueBack = queueFront; // set queueBack to point to

// the node

current = current->next; // set current to point

// to the next node

// copy the remaining of the queue

while ( current != NULL)

{

newNode = new NodeType;

newNode->info = current->info;

newNode->next = NULL;

queueBack->next = newNode;

queueBack = newNode;

current = current->next;

}//end while

}// end try

catch (bad_alloc)

{

cout << "ERROR: Cannot allocate memory! ";

exit(EXIT_FAILURE);

}

}//end else

}

#endif

What is the effect of the following statements? If a statement is invalid, explain why it is invalid.

(a) LinkedQueueType numQueue;

(b) LinkedQueueType numQueue2(numQueue);