Question
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
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
#include
#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
// 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
(const ArrayQueueType
// 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
// Function to make a copy of otherQueue.
// A deep copy of otherQueue is created and assigned to this queue.
};
//**************************************************************
template
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
(const ArrayQueueType
{
try
{
list = new ItemType[MAX_QUEUE_SIZE];
}// end try
catch (bad_alloc)
{
cout << "ERROR: Cannot allocate memory! ";
exit(EXIT_FAILURE);
}
copyQueue(otherQueue);
}
//**************************************************************
template
ArrayQueueType
{
delete [] list; // Deallocate the memory occupied by the array.
}
//**************************************************************
template
void ArrayQueueType
{
queueFront = 0;
queueBack = MAX_QUEUE_SIZE - 1;
length = 0;
}
//**************************************************************
template
void ArrayQueueType
{
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
{
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
{
return ( length == 0 );
}
//**************************************************************
template
bool ArrayQueueType
{
return ( length == MAX_QUEUE_SIZE );
}
//**************************************************************
template
ItemType ArrayQueueType
{
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
{
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
(const ArrayQueueType
{
if ( this != &otherQueue ) // avoid self-copying
copyQueue(otherQueue);
return *this;
}
//**************************************************************
template
void ArrayQueueType
(const ArrayQueueType
{
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
(b) ArrayQueueType
(c) ArrayQueueType
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started