In C++ Please fill out QueueArray.cpp and QueueLinked.cpp please!! To do: - impl
ID: 3732403 • Letter: I
Question
In C++ Please fill out QueueArray.cpp and QueueLinked.cpp please!!
To do:
- implement the Queue ADT (50 points) using array-based approach and Ex 2 and Ex 3 (100 Points)
- implement the Queue ADT (50 points) using LinkedList -based approach and Ex 2 and Ex 3 (100 Points)
QueueArray.cpp
#include "QueueArray.h"
template
QueueArray::QueueArray(int maxNumber)
{
}
template
QueueArray::QueueArray(const QueueArray& other)
{
}
template
QueueArray& QueueArray::operator=(const QueueArray& other)
{
}
template
QueueArray::~QueueArray()
{
}
template
void QueueArray::enqueue(const DataType& newDataItem) throw (logic_error)
{
}
template
DataType QueueArray::dequeue() throw (logic_error)
{
DataType temp;
return temp;
}
template
void QueueArray::clear()
{
}
template
bool QueueArray::isEmpty() const
{
return false;
}
template
bool QueueArray::isFull() const
{
return false;
}
template
void QueueArray::putFront(const DataType& newDataItem) throw (logic_error)
{
}
template
DataType QueueArray::getRear() throw (logic_error)
{
DataType temp;
return temp;
}
template
int QueueArray::getLength() const
{
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 << " ";
cout << endl;
if ( back >= front )
for ( j = 0 ; j < maxSize ; j++ )
if ( ( j >= front ) && ( j <= back ) )
cout << dataItems[j] << " ";
else
cout << " ";
else
for ( j = 0 ; j < maxSize ; j++ )
if ( ( j >= front ) || ( j <= back ) )
cout << dataItems[j] << " ";
else
cout << " ";
cout << endl;
}
}
QueueArray.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.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 ";
for ( p = front ; p != 0 ; p = p->next )
{
if( p == front )
{
cout << '[' << p->dataItem << "] ";
}
else
{
cout << p->dataItem << " ";
}
}
cout << " rear" << endl;
}
}
QueueLinked.h
// 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;
};
test7.cpp
#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.h
#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
show7.cpp
#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 ";
for ( p = front ; p != 0 ; p = p->next )
{
if( p == front )
{
cout << '[' << p->dataItem << "] ";
}
else
{
cout << p->dataItem << " ";
}
}
cout << " rear" << 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 << " ";
cout << endl;
if ( back >= front )
for ( j = 0 ; j < maxSize ; j++ )
if ( ( j >= front ) && ( j <= back ) )
cout << dataItems[j] << " ";
else
cout << " ";
else
for ( j = 0 ; j < maxSize ; j++ )
if ( ( j >= front ) || ( j <= back ) )
cout << dataItems[j] << " ";
else
cout << " ";
cout << endl;
}
}
config.h
/**
* 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 0 // Programming exercise 2: putFront and getRear
#define LAB7_TEST3 0 // Programming exercise 3: getLength
PLEASE ADD COMMENTS SO I CAN UNDERSTAND WHATS BEING DONE
Explanation / Answer
Please find my answer:
//main.cpp
#include <iostream>
#include "config.h"
using namespace std;
#if LAB7_TEST1
# include "QueueLinked.cpp"
#else
# include "QueueArray.cpp"
#endif
void print_help();
template <typename DataType>
void test_queue(Queue<DataType>& testQueue)
//void test_queue(Queue<char>& 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<char> s1;
test_queue(s1);
#else
cout << "Testing linked implementation" << endl;
QueueLinked<char> 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.h
-------------------------------------------
#ifndef QUEUE_H
#define QUEUE_H
#include <stdexcept>
#include <iostream>
using namespace std;
template <typename DataType>
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;
#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 <typename DataType>
Queue<DataType>::~Queue()
{}
#endif // #ifndef QUEUE_H
--------------------------------------------------------------------------------------------------------
QueueArray.cpp
---------------------------------------
#include "QueueArray.h"
// other headers/namespaces
#include <iostream>
using namespace std;
template <typename DataType>
QueueArray<DataType>::QueueArray(int maxNumber) {
// initialize data members
maxSize = maxNumber;
front = -1; // -1 is the traditional way to indicate that front and back do
back = -1; // not point to valid indices
dataItems = NULL;
// attempt dynamic memory allocation
dataItems = new DataType [maxNumber];
// TODO: catch allocation error if any?
// no return - constructor
}
template <typename DataType>
QueueArray<DataType>::QueueArray(const QueueArray& other) {
// initialize data members
maxSize = NULL;
front = -1;
back = -1;
dataItems = NULL;
// use the overloaded = operator to avoid code replication
*this = other;
// no return - constructor
}
template <typename DataType>
QueueArray<DataType>& QueueArray<DataType>::operator=(const QueueArray<DataType>& other) {
// variables
int cursor = -1;
// check to see if *this is being copied into itself
if( this == &other ) {
// return *this
return *this;
}
// otherwise, copy other
else {
// case: other has different maxSize => deconstruct *this to prepare for
// copying
if( maxSize != other.maxSize ) {
// clone maxSize variable
maxSize = other.maxSize;
if( dataItems != NULL ) {
// return the dynamic memory
delete [] dataItems;
}
// get new dynamic memory
dataItems = new DataType [maxSize];
}
// clone the front and back cursors
front = other.front;
back = other.back;
cursor = front;
// queue up the elements of other until there are no more to copy
// case: other has one element
if( (front == back) && (front > -1) ) {
// copy the data
dataItems[cursor] = other.dataItems[cursor];
}
// case: other has multiple elements
else if( front > -1 ) {
// copy all elements
do {
// check if cursor needs to wrap around the end of array
if( cursor == maxSize ) {
// put cursor at start of array
cursor = 0;
}
// copy element
dataItems[cursor] = other.dataItems[cursor];
// increment cursor
++ cursor;
} while( cursor != (back + 1) );
}
// case: other is empty
// do nothing
}
// return *this
return *this;
}
template <typename DataType>
QueueArray<DataType>::~QueueArray() {
// return the dynamic memory used
delete [] dataItems;
// clean up dangling pointers
dataItems = NULL;
// no other action is needed since there is nothing else to clean up
// no return - destructor
}
template <typename DataType>
void QueueArray<DataType>::enqueue(const DataType& newDataItem)
throw (logic_error) {
// check if queue can't hold any more items
if( isFull() ) {
// display error message
cout << "Error: Queue is full, object cannot be added." << endl;
}
// otherwise, add the item
else {
// case: queue is empty
if( isEmpty() ) {
// update front and back cursors
front = 0;
back = 0;
}
// case: queue has at least one item
else {
// advance the back value
// increment the back value
++ back;
// case: the queue has wrapped around the end of the array
if( back == maxSize ) {
// start back back at start of array
back = 0;
}
}
// place the data in the array at the now updated back position
dataItems[back] = newDataItem;
}
// no return - void
}
template <typename DataType>
DataType QueueArray<DataType>::dequeue() throw (logic_error){
// variables
int return_cursor = front;
// check to see that queue does contain data
if( isEmpty() ) {
// display error message
cout << "Error: dequeue() on empty queue." << endl;
}
// otherwise, pop the item
else {
// adjust front value appropriately
// increment the front cursor
++ front;
// case: front wrapped around the back of the array
if( front == maxSize ) {
// set front to the first element of array
front = 0;
}
if( (front == (back + 1))
|| ((front == 0) && (back == (maxSize - 1))) ) {
// set front and back to values that indicate that the list is empty
front = -1;
back = -1;
}
// return the data item
return dataItems[return_cursor];
}
}
template <typename DataType>
void QueueArray<DataType>::clear() {
// set front and back to values that indicate empty queue
front = -1;
back = -1;
}
template <typename DataType>
bool QueueArray<DataType>::isEmpty() const {
// return the result of checking the value of the front cursor for validity
return (front == -1);
}
template <typename DataType>
bool QueueArray<DataType>::isFull() const {
// make checks to see if the array is full
// case: front is at start, back at end
if( (front == 0) && (back == (maxSize - 1)) ) {
// indicate that queue is full
return true;
}
// case: back is against front
else if( back == (front - 1) ) {
// indicate that queue is full
return true;
}
// otherwise, queue is not full
else {
// indicate that queue is not full
return false;
}
}
template <typename DataType>
void QueueArray<DataType>::putFront(const DataType& newDataItem)
throw (logic_error) {
// check to see if list is full
if( isFull() ) {
// display error message
cout << "Error: putFront() used when queue is full." << endl;
}
// otherwise, add data to queue
else {
// case: queue is empty
if( isEmpty() ) {
// update front and back cursors
front = 0;
back = 0;
}
// case: queue has at least one element
else {
// update front cursor
// decrement front
-- front;
// check to see if front has wrapped around front of array
if( front < 0 ) {
// set front to element at end of array
front = (maxSize - 1);
}
}
// store data to new front position in array
dataItems[front] = newDataItem;
}
// no return - void
}
template <typename DataType>
DataType QueueArray<DataType>::getRear() throw (logic_error) {
// variables
int return_cursor = -1;
// check to see if queue is empty
if( isEmpty () ) {
// display error message
cout << "Error: getRear() on empty queue." << endl;
// TODO: refine by throwing exception
}
// otherwise, get the data item
else {
// save the cursor position
return_cursor = back;
// case: the queue only had one item
if( front == back ) {
// set the front and back values to indicate an empty array
front = -1;
back = -1;
}
// case: the queue had more than one item
else {
// update the back position
// decrement back
-- back;
// check to see if back wrapped around front of array
if( back < 0 ) {
// set back to the last element of the array
back = (maxSize - 1);
}
}
// return the data item
return dataItems[return_cursor];
}
}
template <typename DataType>
int QueueArray<DataType>::getLength() const {
// variables
int length = -8; // garbage clearing/error testing value
int interim = 0; // an intermediate arithmetic variable for modularity
// case: front cursor value is less than that of back
if( front < back ) {
// the length is the difference of front and back + 1
length = (back - front + 1);
}
// case: back cursor value is less than that of front
else if( back < front ) {
// find difference between maxSize and front for end elements of array
interim = (maxSize - front);
// add the value of back for elements at front of array
interim += back;
// length is the intermediate result + 1
length = (interim + 1);
}
// case: front == back and they hold a valid reference
else if( (front == back) && (front >= 0) ) {
// the queue has onyl 1 element
length = 1;
}
// otherwise the list is empty
else {
// length is 0
length = 0;
}
// return length
return length;
}
template <typename DataType>
void QueueArray<DataType>::showStructure() const {
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 << " ";
cout << endl;
if ( back >= front )
for ( j = 0 ; j < maxSize ; j++ )
if ( ( j >= front ) && ( j <= back ) )
cout << dataItems[j] << " ";
else
cout << " ";
else
for ( j = 0 ; j < maxSize ; j++ )
if ( ( j >= front ) || ( j <= back ) )
cout << dataItems[j] << " ";
else
cout << " ";
cout << endl;
}
}
-----------------------------------------------------------------------------------
QueueArray.h
------------------------------------------------
#ifndef QUEUEARRAY_H
#define QUEUEARRAY_H
#include <stdexcept>
#include <iostream>
using namespace std;
#include "Queue.h"
template <typename DataType>
class QueueArray : public Queue<DataType> {
public:
QueueArray(int maxNumber = Queue<DataType>::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.cpp
---------------------------------------
#include "QueueLinked.h"
// other headers/namespaces
#include <iostream>
using namespace std;
template <typename DataType>
QueueLinked<DataType>::QueueLinked(int maxNumber /* ignored */) {
// initialize data members
front = NULL;
back = NULL;
// no return - constructor
}
template <typename DataType>
QueueLinked<DataType>::QueueLinked(const QueueLinked& other) {
// intitalize data members to indicate empty container
front = NULL;
back = NULL;
// use the overloaded = operator to avoid code replication
*this = other;
// no return - constructor
}
template <typename DataType>
QueueLinked<DataType>& QueueLinked<DataType>::operator=(const QueueLinked& other) {
// variables
QueueNode* other_cursor = other.front;
// prevent copying *this into itself
if( this == &other ) {
// end funtion execution
return *this; // TODO: refine by throwing exception?
}
// otherwise, attempt to copy other
else {
// clear *this to start fresh
clear();
// case: other is empty
if( other.isEmpty() ) {
// nothing to copy, return empty queue
return *this;
}
// otherwise, copy nodes
else {
// copy nodes until the end of the list has been reached
while( other_cursor != NULL ) {
// create a node in *this with the data in other
enqueue( other_cursor->dataItem );
// advance other_cursor for the next iteration
other_cursor = other_cursor->next;
}
}
}
// end function, return *this
return *this;
}
template <typename DataType>
QueueLinked<DataType>::QueueNode::QueueNode(const DataType& nodeData, QueueNode* nextPtr) {
// initialize data members with the given parameter data
dataItem = nodeData;
next = nextPtr;
// no return - constructor
}
template <typename DataType>
QueueLinked<DataType>::~QueueLinked() {
// use clear function to remove all nodes and return all dynamic memory
clear();
// no return - destructor
}
template <typename DataType>
void QueueLinked<DataType>::enqueue(const DataType& newDataItem)
throw (logic_error) {
// variables
QueueNode* new_node = NULL;
// ensure that an item can be added
if( isFull() ) {
// display error message
cout << "Error: enqueue() on full queue." << endl;
}
// otherwise, add the data
else {
// create the new node
new_node = new QueueNode( newDataItem, NULL );
// add the node to the queue
// case: queue was empty
if( isEmpty() ) {
// update the front pointer
front = new_node;
// update the back pointer
back = new_node;
}
// otherwise, append the node to the end of the list (queue)
else {
// link the new node to the old back
back->next = new_node;
// update the back
back = new_node;
}
// clean up dangling pointers
new_node = NULL;
}
// no return - void
}
template <typename DataType>
DataType QueueLinked<DataType>::dequeue() throw (logic_error){
// variables
QueueNode* delete_cursor = NULL;
DataType the_data;
// check if queue is empty
if( isEmpty() ) {
// display error message
cout << "Error: dequeue() on empty queue." << endl;
// TODO: refine by throwing exception
}
// otherwise, carry out operation
else {
// save location and data of node to be removed
delete_cursor = front;
the_data = front->dataItem;
// case: front is only node
if( front == back ) {
// set front and back to NULL, indicating queue will be empty
front = NULL;
back = NULL;
}
// case: there are more nodes in queue
else {
// only update the front pointer
front = front->next;
}
// delete the node
delete delete_cursor;
// clean up dangling pointers
delete_cursor = NULL;
// return the data
return the_data;
}
}
template <typename DataType>
void QueueLinked<DataType>::clear() {
// remove nodes until the queue is empty
while( !isEmpty() ) {
// dequeue the current node
dequeue();
}
// no return - void
}
template <typename DataType>
bool QueueLinked<DataType>::isEmpty() const {
// return the result of whether or not front points to anything
return (front == NULL);
}
template <typename DataType>
bool QueueLinked<DataType>::isFull() const {
/* because this is a trivial implementation so we will assume that the
data structure is never full */
// return false
return false;
}
template <typename DataType>
void QueueLinked<DataType>::putFront(const DataType& newDataItem)
throw (logic_error) {
// variables
QueueNode* new_node = NULL;
// check if data can't be added to the queue
if( isFull() ) {
// display error message
cout << "Error: putFront() on full queue." << endl;
// TODO: refine by throwing/catching exception
}
// otherwise, add the new node to the front of the queue
else {
// create the new node
new_node = new QueueNode( newDataItem, NULL );
// case: queue is empty
if( isEmpty() ) {
// update front and back to indicate new, solitary element
front = new_node;
back = new_node;
}
// case: queue not empty
else {
// link new node to the old front
new_node->next = front;
// update front pointer
front = new_node;
}
}
// no return - void
}
template <typename DataType>
DataType QueueLinked<DataType>::getRear() throw (logic_error) {
// variables
QueueNode* delete_cursor = NULL;
QueueNode* previous_node = NULL;
DataType the_data;
// check if queue has no data
if( isEmpty() ) {
// display error message
cout << "Error: getRear() on empty queue." << endl;
// TODO: refine by throwing exception?
}
// otherwise, perform operation
else {
// save back location and data
delete_cursor = back;
the_data = back->dataItem;
// case: queue has only one node
if( front == back ) {
// update front and back to indicate list will be empty
front = NULL;
back = NULL;
}
// case: queue has multiple nodes
else {
// find previous node, starting with the front node
previous_node = front;
// iterate through queue until previous node is found
while( previous_node->next != back ) {
// advance the previous_node pointer
previous_node = previous_node->next;
}
// update the back pointer, be sure to "undangle" next
back = previous_node;
back->next = NULL;
}
// delete the old back node
delete delete_cursor;
// clean up dangling pointers
delete_cursor = NULL;
// return the data
return the_data;
}
}
template <typename DataType>
int QueueLinked<DataType>::getLength() const {
// variables
QueueNode* cursor = NULL;
int length = 0;
// iterate through the queue to find the length
for( length = 0, cursor = front; cursor != NULL;
++ length, cursor = cursor->next ) {}
// return the length
return length;
}
template <typename DataType>
void QueueLinked<DataType>::showStructure() const {
QueueNode* cursor; // Iterates through the queue
if ( isEmpty() )
cout << "Empty queue" << endl;
else
{
cout << "Front ";
for ( cursor = front ; cursor != NULL ; cursor = cursor->next )
{
if( cursor == front )
{
cout << '[' << cursor->dataItem << "] ";
}
else
{
cout << cursor->dataItem << " ";
}
}
cout << " rear" << endl;
}
}
-------------------------------------------------------------------------------------------------------------
QueueLinked.h
---------------------------------------------
#include <stdexcept>
#include <iostream>
using namespace std;
#include "Queue.h"
template <typename DataType>
class QueueLinked : public Queue<DataType> {
public:
QueueLinked(int maxNumber = Queue<DataType>::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;
};
--------------------------------------------------------------------------------------------------------------
config.h
------------------------------------------
#define LAB7_TEST1 1
#define LAB7_TEST2 1
#define LAB7_TEST3 1