C++ Program please - Implement array based queue ( 50 pts ) - Implement linked-l
ID: 3724303 • Letter: C
Question
C++ Program please
- 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)
Queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <stdexcept>
#include <iostream>
using namespace std;
#pragma warning( disable : 4290 )
//--------------------------------------------------------------------
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;
// 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 <typename DataType>
Queue<DataType>::~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 <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.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;
};
QueueArray.cpp
#include "QueueArray.h"
template <typename DataType>
QueueArray<DataType>::QueueArray(int maxNumber)
{
}
template <typename DataType>
QueueArray<DataType>::QueueArray(const QueueArray& other)
{
}
template <typename DataType>
QueueArray<DataType>& QueueArray<DataType>::operator=(const QueueArray& other)
{
}
template <typename DataType>
QueueArray<DataType>::~QueueArray()
{
}
template <typename DataType>
void QueueArray<DataType>::enqueue(const DataType& newDataItem) throw (logic_error)
{
}
template <typename DataType>
DataType QueueArray<DataType>::dequeue() throw (logic_error)
{
DataType temp;
return temp;
}
template <typename DataType>
void QueueArray<DataType>::clear()
{
}
template <typename DataType>
bool QueueArray<DataType>::isEmpty() const
{
return false;
}
template <typename DataType>
bool QueueArray<DataType>::isFull() const
{
return false;
}
template <typename DataType>
void QueueArray<DataType>::putFront(const DataType& newDataItem) throw (logic_error)
{
}
template <typename DataType>
DataType QueueArray<DataType>::getRear() throw (logic_error)
{
DataType temp;
return temp;
}
template <typename DataType>
int QueueArray<DataType>::getLength() const
{
return -1;
}
//--------------------------------------------------------------------
template <typename DataType>
void QueueArray<DataType>::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;
}
}
QueueLinked.cpp
#include "QueueLinked.h"
template <typename DataType>
QueueLinked<DataType>::QueueNode::QueueNode(const DataType& nodeData, QueueNode* nextPtr)
{
}
template <typename DataType>
QueueLinked<DataType>::QueueLinked(int maxNumber = Queue<DataType>::MAX_QUEUE_SIZE)
{
}
template <typename DataType>
QueueLinked<DataType>::QueueLinked(const QueueLinked& other)
{
}
template <typename DataType>
QueueLinked<DataType>& QueueLinked<DataType>::operator=(const QueueLinked& other)
{
}
template <typename DataType>
QueueLinked<DataType>::~QueueLinked()
{
}
template <typename DataType>
void QueueLinked<DataType>::enqueue(const DataType& newDataItem) throw (logic_error)
{
}
template <typename DataType>
DataType QueueLinked<DataType>::dequeue() throw (logic_error)
{
DataType temp;
return temp;
}
template <typename DataType>
void QueueLinked<DataType>::clear()
{
}
template <typename DataType>
bool QueueLinked<DataType>::isEmpty() const
{
return false;
}
template <typename DataType>
bool QueueLinked<DataType>::isFull() const
{
return false;
}
template <typename DataType>
void QueueLinked<DataType>::putFront(const DataType& newDataItem) throw (logic_error)
{
}
template <typename DataType>
DataType QueueLinked<DataType>::getRear() throw (logic_error)
{
DataType temp;
return temp;
}
template <typename DataType>
int QueueLinked<DataType>::getLength() const
{
}
template <typename DataType>
void QueueLinked<DataType>::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;
}
}
Show7.cpp
#include "Queue.h"
#include "QueueArray.h"
#include "QueueLinked.h"
template < class DT >
void Queue<DT>:: 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<DT> *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 <typename DataType>
void QueueArray<DataType>::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;
}
}
test7.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;
}
Explanation / Answer
#include "QueueArray.h"
template <typename DataType>
QueueArray<DataType>::QueueArray(int maxNumber)
{
dataItems = new DataType[maxNumber];
maxSize = maxNumber;
front = -1;
back = -1;
}
template <typename DataType>
QueueArray<DataType>::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 <typename DataType>
QueueArray<DataType>& QueueArray<DataType>::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 <typename DataType>
QueueArray<DataType>::~QueueArray()
{
maxSize = 0;
front = -1;
back = -1;
delete[] dataItems;
}
template <typename DataType>
void QueueArray<DataType>::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 <typename DataType>
DataType QueueArray<DataType>::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 <typename DataType>
void QueueArray<DataType>::clear()
{
front = -1;
back = -1;
}
template <typename DataType>
bool QueueArray<DataType>::isEmpty() const
{
if(front == -1 && back == -1){
return true;
}else if(back == front && back != 0){
return true;
}
return false;
}
template <typename DataType>
bool QueueArray<DataType>::isFull() const
{
if(back == front-1){
return true;
}
if(front == 0 && back == maxSize-1){
return true;
}
return false;
}
template <typename DataType>
void QueueArray<DataType>::putFront(const DataType& newDataItem) throw (logic_error)
{
if(isEmpty()){
throw logic_error("Queue is empty ");
}
dataItems[front] = newDataItem;
}
template <typename DataType>
DataType QueueArray<DataType>::getRear() throw (logic_error)
{
DataType temp;
temp = dataItems[back];
return temp;
}
template <typename DataType>
int QueueArray<DataType>::getLength() const
{
if(isFull()){
return maxSize;
}else{
if(back < front){
return maxSize - front + back;
}else if(back > front){
return back - front;
}
}
return -1;
}
//--------------------------------------------------------------------
template <typename DataType>
void QueueArray<DataType>::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;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.