The Queue1 class is a naive implementation of a queue using the provided functionality of the MyVector. The Queue2 class will alter the MyVector behavior by introducing a circular array pattern to the array stored. And, the Queue3 class is a naive implementation of a queue using the default behavior of the List class. Provided Files:
proj10-ContainerIfc. h
proj10-Node. h
proj10-ContainerIfc. h
class BADINDEX {};
template
class ContainerIfc {
public:
virtual ContainerIfc & pushFront(T) =0;
virtual ContainerIfc & pushBack(T) =0;
virtual ContainerIfc & popFront(T&) =0; // throws BADINDEX
virtual ContainerIfc & popBack(T&) =0; // throws BADINDEX
virtual int getSize() =0;
virtual bool isEmpty() =0;
virtual T front() =0; // throws BADINDEX
virtual T back() =0; // throws BADINDEX
virtual T& operator [](int) =0; // throws BADINDEX
virtual void erase() =0;
};
proj10-Node. h - notice that this Node. h is different from the previous MyList implementation
template
class Node {
public:
T data;
Node *next;
Node( T d ) {
data = d;
next = NULL;
}
~Node( ) {
delete next;
}
};
Deliverables:
proj10-driver. cpp
proj10-MyVector. h
proj10-MyList. h
proj10-Queue1.h
proj10-Queue2.h
proj10-Queue3.h
proj10-driver. cpp
Your driver should randomly generate and enqueue 100 integer values in each queue implementation. It should then time (using the time() fucnction) the dequeue of all integer values stored for each implementation of the queue independently. I encourage each of you to experiment locally with much larger numbers of integers to demonstrate the performance (efficiency) differences between these different queue implementations. Unfortunately, the upload site limits runtime for your programs to 1 second, and you won't be able to distiguish a difference between the runtimes of the different implementations in less than a second. So, our turned in version of the driver needs to be limited to 100 integers to ensure it completes all three implementations within that second of runtime.
proj10-MyVector. h
#include "proj10-ContainerIfc. h"
template
class MyVector : public ContainerIfc {
public:
MyVector ();
~MyVector ();
MyVector (const MyVector&);
MyVector& operator = (const MyVector&);
MyVector& pushFront(T);
MyVector& pushBack(T);
MyVector& popFront(T&); // throws BADINDEX
MyVector& popBack(T&); // throws BADINDEX
T front(); // throws BADINDEX
T back(); // throws BADINDEX
T& operator [](int); // throws BADINDEX
int getSize();
bool isEmpty();
void erase();
protected:
T *data;
int size;
int capacity;
void grow();
void shiftRight();
void shiftLeft();
};
proj10-MyList. h - notice that we are updating the original MyList implementation by adding a tail
#include "proj10-ContainerIfc. h"
#include "proj10-Node. h"
template
class MyList : public ContainerIfc {
public:
MyList();
~ MyList();
MyList(const MyList &);
MyList & operator = (const MyList &);
MyList & pushFront(T);
MyList & pushBack(T);
MyList & popFront(T&); // throws BADINDEX
MyList & popBack(T&); // throws BADINDEX
int getSize();
bool isEmpty();
T front(); // throws BADINDEX
T back(); // throws BADINDEX
T& operator [](int); // throws BADINDEX
private:
Node *head;
Node *tail;
};
proj10-Queue1.h - naive implementation of queue using your MyVector implementation
#include "proj10-MyVector. h"
template
class Queue1 : public MyVector {
public:
void enqueue( T );
void dequeue( T& ); // throws BADINDEX
};
proj10-Queue2.h - still uses the MyVector, but implemented using "circular" array
#include "proj10-MyVector. h"
template
class Queue2 : public MyVector {
private:
int front, rear;
public:
Queue2();
void enqueue( T );
void dequeue( T& ); // throws BADINDEX
};
proj10-Queue3.h - implementation using your MyList implementation
#include "proj10-MyList. h"
template
class Queue3 : public MyList {
public:
void enqueue( T );
void dequeue( T& ); // throws BADINDEX
};
Expert A