Question

Data Structures using C++

Consider the following class

#ifndef LINKEDQUEUETYPE_H

#define LINKEDQUEUETYPE_H

#include <iostream>

#include <new>   

#include <cstdlib>

#include "QueueADT.h"

using namespace std;

// Definition of the node

template <class ItemType>

struct NodeType

{

       ItemType info;

       NodeType<ItemType> *next;

};

template <class ItemType>

class LinkedQueueType: public QueueADT<ItemType>

{

public:

       // Constructor

       LinkedQueueType();

          // Default constructor.

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

          //       queueBack = NULL;

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

                     (const LinkedQueueType<ItemType>& otherQueue);

          // Overload the assignment operator.

protected:

       NodeType<ItemType> *queueFront; // pointer to the front of the queue

                                       // (pointing to first node)

       NodeType<ItemType> *queueBack; // pointer to the back of the queue

                                       // (pointing to last node)

private:

       void copyQueue(const LinkedQueueType<ItemType>& otherQueue);

          // Function to make a copy of otherQueue.

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

};

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

template <class ItemType>

LinkedQueueType<ItemType>::LinkedQueueType()

{

       queueFront = NULL;

       queueBack = NULL;

}

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

template <class ItemType>

LinkedQueueType<ItemType>::LinkedQueueType

                (const LinkedQueueType<ItemType>& otherQueue)

{

       queueFront = NULL;

       queueBack = NULL;

       copyQueue(otherQueue);

}

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

template <class ItemType>

LinkedQueueType<ItemType>::~LinkedQueueType()

{

       resetQueue();

}

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

template <class ItemType>

void LinkedQueueType<ItemType>::resetQueue()

{

       NodeType<ItemType> *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 <class ItemType>

void LinkedQueueType<ItemType>::add(const ItemType& newItem)

{

       NodeType<ItemType> *newNode; // pointer to create the new node

       try

       {

              newNode = new NodeType<ItemType>; // 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!\n";

              exit(EXIT_FAILURE);

       }

}

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

template <class ItemType>

void LinkedQueueType<ItemType>::remove()

{

       NodeType<ItemType> *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 <class ItemType>

bool LinkedQueueType<ItemType>::isEmpty() const

{

       return ( queueFront == NULL );

}

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

template <class ItemType>

bool LinkedQueueType<ItemType>::isFull() const

{

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

                                    // is more room

       try

       {

              newNode = new NodeType<ItemType>;

              delete newNode;

              return false; //more room available, not full

       }// end try

       catch (bad_alloc)

       {

              return true; // no more room available

       }

}

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

template <class ItemType>

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

              exit(EXIT_FAILURE);

       }

}

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

template <class ItemType>

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

              exit(EXIT_FAILURE);

       }

}

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

template <class ItemType>

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

                    (const LinkedQueueType<ItemType>& otherQueue)

{

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

              copyQueue(otherQueue);

       return *this;

}

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

template <class ItemType>

void LinkedQueueType<ItemType>::copyQueue

                     (const LinkedQueueType<ItemType>& otherQueue)

{

       NodeType<ItemType> *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<ItemType>; // 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<ItemType>;

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

                     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<int> numQueue;

(b) LinkedQueueType<int> numQueue2(numQueue);

Answer 1

LinkedQueueType class has two constructor:

   // Constructor
LinkedQueueType();
    // Default constructor.
// Post: An empty queue has been created. queueFront = NULL;

LinkedQueueType(const LinkedQueueType<ItemType>& otherQueue);
// Copy constructor for deep copy of the linked implementation
// of queues.

(a) LinkedQueueType<int> numQueue;

   THis sttement create an Object of class LinkedQueueType using default constructor.
   Since LinkedQueueType class has default constructor so this is valid statement

(b) LinkedQueueType<int> numQueue2(numQueue);

THis sttement create an Object of class LinkedQueueType using copy constructor.
   Since LinkedQueueType class has copy constructor so this is valid statement.