Questions:

- Implement array based queue (50 pts)

- Implement linked-list based queue (50 pts)

In either of which,

- enqueue(): (15 pts)

- dequeue(): (15 pts)

- Others (constructor, destructor, clear(), isEmpty(), isFull()):

(20 pts)

Note: For linked-list implementation isFull() function must have just one statement which is return false;

_________________________________________________________________________________________

//QueueArray.cpp

#include "QueueArray.h"

template

QueueArray::QueueArray(int maxNumber)

{

dataItems = new DataType[maxNumber];

maxSize = maxNumber;

front = -1;

back = -1;

}

template

QueueArray::QueueArray(const QueueArray& other)

{

maxSize = other.maxSize;

dataItems = new DataType[maxSize];

for (int i = 0; i <= other.back; i++) {

dataItems[i] = other.dataItems[i];

}

front = other.front;

back = other.back;

}

template

QueueArray& QueueArray::operator=(const QueueArray& other)

{

maxSize = other.maxSize;

dataItems = new DataType[maxSize];

for (int i = 0; i <= other.back; i++) {

dataItems[i] = other.dataItems[i];

}

front = other.front;

back = other.back;

return *this;

}

template

QueueArray::~QueueArray()

{

maxSize = 0;

front = -1;

back = -1;

delete[] dataItems;

}

template

void QueueArray::enqueue(const DataType& newDataItem) throw (logic_error)

{

if (isFull()) {

throw logic_error("Queue is Full");

}

if (isEmpty()) {

front = 0;

back = 0;

dataItems[front] = newDataItem;

}

else {

back++;

if (back >= maxSize) {

back = 0;

}

dataItems[back] = newDataItem;

}

}

template

DataType QueueArray::dequeue() throw (logic_error)

{

DataType temp;

temp = dataItems[front];

if (back == front && front == 0) {

front = -1;

back = -1;

}

else {

front++;

}

if (isEmpty()) {

front = -1;

back = -1;

}

else if (front >= maxSize) {

front = 0;

}

return temp;

}

template

void QueueArray::clear()

{

front = -1;

back = -1;

}

template

bool QueueArray::isEmpty() const

{

if (front == -1 && back == -1) {

return true;

}

else if (back == front && back != 0) {

return true;

}

return false;

}

template

bool QueueArray::isFull() const

{

if (back == front - 1) {

return true;

}

if (front == 0 && back == maxSize - 1) {

return true;

}

return false;

}

template

void QueueArray::putFront(const DataType& newDataItem) throw (logic_error)

{

if (isEmpty()) {

throw logic_error("Queue is empty ");

}

dataItems[front] = newDataItem;

}

template

DataType QueueArray::getRear() throw (logic_error)

{

DataType temp;

temp = dataItems[back];

return temp;

}

template

int QueueArray::getLength() const

{

if (isFull()) {

return maxSize;

}

else {

if (back < front) {

return maxSize - front + back;

}

else if (back > front) {

return back - front;

}

}

return -1;

}

//--------------------------------------------------------------------

template

void QueueArray::showStructure() const

// Array implementation. Outputs the data items in a queue. If the

// queue is empty, outputs "Empty queue". This operation is intended

// for testing and debugging purposes only.

{

int j; // Loop counter

if ( front == -1 )

cout << "Empty queue" << endl;

else

{

cout << "Front = " << front << " Back = " << back << endl;

for ( j = 0 ; j < maxSize ; j++ )

cout << j << "\t";

cout << endl;

if ( back >= front )

for ( j = 0 ; j < maxSize ; j++ )

if ( ( j >= front ) && ( j <= back ) )

cout << dataItems[j] << "\t";

else

cout << " \t";

else

for ( j = 0 ; j < maxSize ; j++ )

if ( ( j >= front ) || ( j <= back ) )

cout << dataItems[j] << "\t";

else

cout << " \t";

cout << endl;

}

}

________________________________________________________________________________

//QueueLinked.cpp

#include "QueueLinked.h"

template

QueueLinked::QueueNode::QueueNode(const DataType& nodeData, QueueNode* nextPtr)

{

}

template

QueueLinked::QueueLinked(int maxNumber = Queue::MAX_QUEUE_SIZE)

{

}

template

QueueLinked::QueueLinked(const QueueLinked& other)

{

}

template

QueueLinked& QueueLinked::operator=(const QueueLinked& other)

{

}

template

QueueLinked::~QueueLinked()

{

}

template

void QueueLinked::enqueue(const DataType& newDataItem) throw (logic_error)

{

}

template

DataType QueueLinked::dequeue() throw (logic_error)

{

DataType temp;

return temp;

}

template

void QueueLinked::clear()

{

}

template

bool QueueLinked::isEmpty() const

{

return false;

}

template

bool QueueLinked::isFull() const

{

return false;

}

template

void QueueLinked::putFront(const DataType& newDataItem) throw (logic_error)

{

}

template

DataType QueueLinked::getRear() throw (logic_error)

{

DataType temp;

return temp;

}

template

int QueueLinked::getLength() const

{

}

template

void QueueLinked::showStructure() const

{

QueueNode *p; // Iterates through the queue

if ( isEmpty() )

cout << "Empty queue" << endl;

else

{

cout << "Front\t";

for ( p = front ; p != 0 ; p = p->next )

{

if( p == front )

{

cout << '[' << p->dataItem << "] ";

}

else

{

cout << p->dataItem << " ";

}

}

cout << "\trear" << endl;

}

}

________________________________________________________________________

//--------------------------------------------------------------------

// show7.cpp: includes implementation of showStructure

//--------------------------------------------------------------------

//--------------------------------------------------------------------

#include "Queue.h"

#include "QueueArray.h"

#include "QueueLinked.h"

template < class DT >

void Queue

:: showStructure () const

// Linked list implementation. Outputs the elements in a queue. If

// the queue is empty, outputs "Empty queue". This operation is

// intended for testing and debugging purposes only.

{

QueueNode

*p; // Iterates through the queue

if ( isEmpty() )

cout << "Empty queue" << endl;

else

{

cout << "Front\t";

for ( p = front ; p != 0 ; p = p->next )

{

if( p == front )

{

cout << '[' << p->dataItem << "] ";

}

else

{

cout << p->dataItem << " ";

}

}

cout << "\trear" << endl;

}

}

//--------------------------------------------------------------------

template

void QueueArray::showStructure() const

// Array implementation. Outputs the data items in a queue. If the

// queue is empty, outputs "Empty queue". This operation is intended

// for testing and debugging purposes only.

{

int j; // Loop counter

if ( front == -1 )

cout << "Empty queue" << endl;

else

{

cout << "Front = " << front << " Back = " << back << endl;

for ( j = 0 ; j < maxSize ; j++ )

cout << j << "\t";

cout << endl;

if ( back >= front )

for ( j = 0 ; j < maxSize ; j++ )

if ( ( j >= front ) && ( j <= back ) )

cout << dataItems[j] << "\t";

else

cout << " \t";

else

for ( j = 0 ; j < maxSize ; j++ )

if ( ( j >= front ) || ( j <= back ) )

cout << dataItems[j] << "\t";

else

cout << " \t";

cout << endl;

}

}

______________________________________________________________________

//--------------------------------------------------------------------

//

// Laboratory 7 test7.cpp

//

// Test program for the operations in the Queue ADT

//

//--------------------------------------------------------------------

#include

#include "config.h"

using namespace std;

#if LAB7_TEST1

# include "QueueLinked.cpp"

#else

# include "QueueArray.cpp"

#endif

//--------------------------------------------------------------------

void print_help();

//--------------------------------------------------------------------

template

void test_queue(Queue& testQueue)

//void test_queue(Queue& testQueue)

{

char cmd; // Input command

char testData; // Queue data item

print_help();

do

{

try {

testQueue.showStructure(); // Output queue

cout << endl << "Command: "; // Read command

cin >> cmd;

if ( cmd == '+' || cmd == '>' )

cin >> testData;

switch ( cmd )

{

case 'H' : case 'h' :

print_help();

break;

case '+' : // enqueue

cout << "Enqueue " << testData << endl;

testQueue.enqueue(testData);

break;

case '-' : // dequeue

cout << "Dequeued " << testQueue.dequeue() << endl;

break;

case 'C' : case 'c' : // clear

cout << "Clear the queue" << endl;

testQueue.clear();

break;

case 'E' : case 'e' : // empty

if ( testQueue.isEmpty() )

cout << "Queue is empty" << endl;

else

cout << "Queue is NOT empty" << endl;

break;

case 'F' : case 'f' : // full

if ( testQueue.isFull() )

cout << "Queue is full" << endl;

else

cout << "Queue is NOT full" << endl;

break;

#if LAB7_TEST2

case '>' : // Programming Exercise 2

cout << "Put " << testData << " in front " << endl;

testQueue.putFront(testData);

break;

case '=' : // Programming Exercise 2

cout << "Got " << testQueue.getRear() << " from rear "

<< endl;

break;

#endif

#if LAB7_TEST3

case '#' : // Programming Exercise 3

cout << "Length = " << testQueue.getLength() << endl;

break;

#endif

case 'Q' : case 'q' : // Quit test program

break;

default : // Invalid command

cout << "Inactive or invalid command" << endl;

}

}

catch (logic_error e) {

cout << "Error: " << e.what() << endl;

}

}

while ( cin && cmd != 'Q' && cmd != 'q' );

if( !cin ) {

cout << "input error" << endl;

}

}

//--------------------------------------------------------------------

int main()

{

#if !LAB7_TEST1

cout << "Testing array implementation" << endl;

QueueArray s1;

test_queue(s1);

#else

cout << "Testing linked implementation" << endl;

QueueLinked s2;

test_queue(s2);

#endif

return 0;

}

//--------------------------------------------------------------------

void print_help()

{

cout << endl << "Commands:" << endl;

cout << " H : Help (displays this message)" << endl;

cout << " +x : Enqueue x" << endl;

cout << " - : Dequeue" << endl;

cout << " C : Clear the queue" << endl;

cout << " E : Empty queue?" << endl;

cout << " F : Full queue?" << endl;

cout << " >x : Put x at front ("

#if LAB7_TEST2

<< " Active "

#else

<< "Inactive "

#endif

<< ": Programming Exercise 2)"

<< endl;

cout << " = : Get x from rear ("

#if LAB7_TEST2

<< " Active "

#else

<< "Inactive "

#endif

<< ": Programming Exercise 2)"

<< endl;

cout << " # : Length ("

#if LAB7_TEST3

<< " Active "

#else

<< "Inactive "

#endif

<< ": Programming Exercise 3)"

<< endl;

cout << " Q : Quit the test program" << endl;

cout << endl;

}

_______________________________________________________________________________________

/**

* Queue class (Lab 7) configuration file.

* Activate test #N by defining the corresponding LAB7_TESTN to have the value 1.

*/

#define LAB7_TEST1 0 // 0 => use array implementation, 1 => use linked impl.

#define LAB7_TEST2 1 // Programming exercise 2: putFront and getRear

#define LAB7_TEST3 1 // Programming exercise 3: getLength

________________________________________________________________________

//--------------------------------------------------------------------

//

// Laboratory 7 Queue.h

//

// Class declaration of the abstract class interface to be used as

// the basis for implementations of the Queue ADT.

//

//--------------------------------------------------------------------

#ifndef QUEUE_H

#define QUEUE_H

#include

#include

using namespace std;

#pragma warning( disable : 4290 )

//--------------------------------------------------------------------

template

class Queue {

public:

static const int MAX_QUEUE_SIZE = 8;

virtual ~Queue();

virtual void enqueue(const DataType& newDataItem) throw (logic_error) = 0;

virtual DataType dequeue() throw (logic_error) = 0;

virtual void clear() = 0;

virtual bool isEmpty() const = 0;

virtual bool isFull() const = 0;

// The conditional compilation tests below are very important.

// Because the functions declared are pure virtual functions, if they

// are declared in the base class, then they MUST be implemented in any

// derived classes. But they are supposed to be optional implementations.

// Consequently, they must only be declared here if they are being

// implemented in the derived classes.

#if LAB7_TEST2

virtual void putFront(const DataType& newDataItem) throw (logic_error) = 0;

virtual DataType getRear() throw (logic_error) = 0;

#endif

#if LAB7_TEST3

virtual int getLength() const = 0;

#endif

virtual void showStructure() const = 0;

};

template

Queue::~Queue()

// Not worth having a separate class implementation file for the destuctor

{}

#endif // #ifndef QUEUE_H

_________________________________________________________________________

// QueueArray.h

#ifndef QUEUEARRAY_H

#define QUEUEARRAY_H

#include

#include

using namespace std;

#include "Queue.h"

template

class QueueArray : public Queue {

public:

QueueArray(int maxNumber = Queue::MAX_QUEUE_SIZE);

QueueArray(const QueueArray& other);

QueueArray& operator=(const QueueArray& other);

~QueueArray();

void enqueue(const DataType& newDataItem) throw (logic_error);

DataType dequeue() throw (logic_error);

void clear();

bool isEmpty() const;

bool isFull() const;

void putFront(const DataType& newDataItem) throw (logic_error);

DataType getRear() throw (logic_error);

int getLength() const;

void showStructure() const;

private:

int maxSize;

int front;

int back;

DataType* dataItems;

};

#endif

_____________________________________________________________________________

// QueueLinked.h

#include

#include

using namespace std;

#include "Queue.h"

template

class QueueLinked : public Queue {

public:

QueueLinked(int maxNumber = Queue::MAX_QUEUE_SIZE);

QueueLinked(const QueueLinked& other);

QueueLinked& operator=(const QueueLinked& other);

~QueueLinked();

void enqueue(const DataType& newDataItem) throw (logic_error);

DataType dequeue() throw (logic_error);

void clear();

bool isEmpty() const;

bool isFull() const;

// Programming Exercise 2

void putFront(const DataType& newDataItem) throw (logic_error);

DataType getRear() throw (logic_error);

// Programming Exercise 3

int getLength() const;

void showStructure() const;

private:

class QueueNode {

public:

QueueNode(const DataType& nodeData, QueueNode* nextPtr);

DataType dataItem;

QueueNode* next;

};

QueueNode* front;

QueueNode* back;

};