Data Structures using C++

Consider the classes QueueADT and ArrayQueueType:

QueueADT:

#ifndef QUEUEADT_H

#define QUEUEADT_H

template

class QueueADT

{

public:

// Action responsibilities

virtual void resetQueue() = 0;

// Reset the queue to an empty queue.

// Post: Queue is empty.

virtual void add(const ItemType& newItem) = 0;

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

virtual void remove() = 0;

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

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

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

// removed from the queue.

// Knowledge responsibilities

virtual bool isEmpty() const = 0;

// Function to determine whether the queue is empty.

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

virtual bool isFull() const = 0;

// Function to determin whether the queue is full.

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

// false otherwise.

virtual ItemType front() const = 0;

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

virtual ItemType back() const = 0;

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

};

ArrayQueueType:

#ifndef ARRAYQUEUETYPE_H

#define ARRAYQUEUETYPE_H

#include

#include // for bad_alloc exception

#include // for the exit function

#include "QueueADT.h"

using namespace std;

const int MAX_QUEUE_SIZE = 100; // Maximum number of components

template

class ArrayQueueType: public QueueADT

{

public:

// Constructor

ArrayQueueType();

// Default constructor.

// Post: An empty queue has been created. The variable list holds

// the base address of the array.

ArrayQueueType(const ArrayQueueType& otherQueue);

// Copy constructor for deep copy of the array-based queues.

// Destructor

~ArrayQueueType();

// Delete all the queue items.

// Post: The array (list) holding the queue elements is deleted.

// Action responsibilities

void resetQueue();

// Reset the queue to an empty queue.

// Post: Queue is empty.

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 stack 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 ArrayQueueType& operator=

(const ArrayQueueType& otherQueue);

// Overload the assignment operator.

protected:

int length; // variable to store the number of items in the queue

int queueFront; // variable to store the index of the first item

// of the queue

int queueBack; // variable to store the index of the last item

// of the queue

ItemType *list; // pointer to the array that holds the queue items

private:

void copyQueue(const ArrayQueueType& otherQueue);

// Function to make a copy of otherQueue.

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

};

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

template

ArrayQueueType::ArrayQueueType()

{

try

{

queueFront = 0;

queueBack = MAX_QUEUE_SIZE - 1;

length = 0;

list = new ItemType[MAX_QUEUE_SIZE]; // create the array to

// hold the queue items

}// end try

catch (bad_alloc)

{

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

exit(EXIT_FAILURE);

}

}

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

template

ArrayQueueType::ArrayQueueType

(const ArrayQueueType& otherQueue)

{

try

{

list = new ItemType[MAX_QUEUE_SIZE];

}// end try

catch (bad_alloc)

{

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

exit(EXIT_FAILURE);

}

copyQueue(otherQueue);

}

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

template

ArrayQueueType::~ArrayQueueType()

{

delete [] list; // Deallocate the memory occupied by the array.

}

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

template

void ArrayQueueType::resetQueue()

{

queueFront = 0;

queueBack = MAX_QUEUE_SIZE - 1;

length = 0;

}

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

template

void ArrayQueueType::add(const ItemType& newItem)

{

if ( !isFull() )

{

queueBack = (queueBack + 1) % MAX_QUEUE_SIZE; // use the mod

// operator to advance queueBack because the array is circular

list[queueBack] = newItem; // add newItem to the back

length++;

}

else

cout << "Cannot add to a full queue." << endl;

}

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

template

void ArrayQueueType::remove()

{

if ( !isEmpty() )

{

length--;

queueFront = (queueFront + 1) % MAX_QUEUE_SIZE; // use the mod

// operator to advance queueFront because the array is circular

}

else

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

}

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

template

bool ArrayQueueType::isEmpty() const

{

return ( length == 0 );

}

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

template

bool ArrayQueueType::isFull() const

{

return ( length == MAX_QUEUE_SIZE );

}

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

template

ItemType ArrayQueueType::front() const

{

if ( !isEmpty() )

return list[queueFront]; // the first item is indexed

// by queueFront

else // if queue is empty, terminate the program

{

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

exit(EXIT_FAILURE);

}

}

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

template

ItemType ArrayQueueType::back() const

{

if ( !isEmpty() )

return list[queueBack]; // the last item is indexed

// by queueBack

else // if queue is empty, terminate the program

{

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

exit(EXIT_FAILURE);

}

}

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

template

const ArrayQueueType& ArrayQueueType::operator=

(const ArrayQueueType& otherQueue)

{

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

copyQueue(otherQueue);

return *this;

}

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

template

void ArrayQueueType::copyQueue

(const ArrayQueueType& otherQueue)

{

length = otherQueue.length;

queueFront = otherQueue.queueFront;

queueBack = otherQueue.queueBack;

for (int i = 0; i < length; i++)

list[ (queueFront + i) % MAX_QUEUE_SIZE ]

= otherQueue.list[ (queueFront + i) % MAX_QUEUE_SIZE ];

}

#endif

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

(a) QueueADT newQueue;

(b) ArrayQueueType sales;

(c) ArrayQueueType names;