Question

Data Structures using C++

Consider the classes QueueADT and ArrayQueueType:

QueueADT:

#ifndef QUEUEADT_H

#define QUEUEADT_H

template <class ItemType>

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

#include <new>        // for bad_alloc exception

#include <cstdlib>    // for the exit function

#include "QueueADT.h"

using namespace std;

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

template <class ItemType>

class ArrayQueueType: public QueueADT<ItemType>

{

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<ItemType>& 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<ItemType>& operator=

                     (const ArrayQueueType<ItemType>& 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<ItemType>& otherQueue);

          // Function to make a copy of otherQueue.

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

};

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

template <class ItemType>

ArrayQueueType<ItemType>::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!\n";

              exit(EXIT_FAILURE);

       }

}

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

template <class ItemType>

ArrayQueueType<ItemType>::ArrayQueueType

                (const ArrayQueueType<ItemType>& otherQueue)

{

       try

       {

              list = new ItemType[MAX_QUEUE_SIZE];

       }// end try

       catch (bad_alloc)

       {

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

              exit(EXIT_FAILURE);

       }

       copyQueue(otherQueue);

}

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

template <class ItemType>

ArrayQueueType<ItemType>::~ArrayQueueType()

{

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

}

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

template <class ItemType>

void ArrayQueueType<ItemType>::resetQueue()

{

       queueFront = 0;

       queueBack = MAX_QUEUE_SIZE - 1;

       length = 0;

}

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

template <class ItemType>

void ArrayQueueType<ItemType>::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 <class ItemType>

void ArrayQueueType<ItemType>::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 <class ItemType>

bool ArrayQueueType<ItemType>::isEmpty() const

{

       return ( length == 0 );

}

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

template <class ItemType>

bool ArrayQueueType<ItemType>::isFull() const

{

       return ( length == MAX_QUEUE_SIZE );

}

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

template <class ItemType>

ItemType ArrayQueueType<ItemType>::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!\n";

              exit(EXIT_FAILURE);

       }

}

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

template <class ItemType>

ItemType ArrayQueueType<ItemType>::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!\n";

              exit(EXIT_FAILURE);

       }

}

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

template <class ItemType>

const ArrayQueueType<ItemType>& ArrayQueueType<ItemType>::operator=

                    (const ArrayQueueType<ItemType>& otherQueue)

{

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

              copyQueue(otherQueue);

       return *this;

}

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

template <class ItemType>

void ArrayQueueType<ItemType>::copyQueue

                    (const ArrayQueueType<ItemType>& 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<int> newQueue;

(b) ArrayQueueType<double> sales;

(c) ArrayQueueType<string> names;

Answer 1

(a) QueueADT<int> newQueue;
QueueADT is an abstract class. And an abstract class is to provide appropriate base
to the inherited classes. And it is not allowed to have any instances of type Abstract class.

(b) ArrayQueueType<double> sales;
Creates an object sales of type ArrayQueueType which takes a variables of type double.

(c) ArrayQueueType<string> names;
Creates an object names of type ArrayQueueType which takes a variables of type string.