This assignment is an exercise in implementing the queue ADT using an array-base
ID: 3757940 • Letter: T
Question
This assignment is an exercise in implementing the queue ADT using an array-based data structure.
Assignment
This program creates and implements a class to represent the Queue ADT using an array.
A driver program is provided for this assignment to test your implementation. You don't have to write the tests.
Program
You will need to write a single class for this assignment, the Queue class. You will need to implement several methods and functions associated with this class.
The class should be implemented as two separate files. The class definition should be placed in an appropriately named header (.h) file. The implementations of the class methods and any other associated functions should be placed in a separate .cpp file for the class.
class Queue
Data members
This class contains a pointer to an integer that will point to the first element of a dynamically allocated array of integers (the queue array). Because the array is allocated dynamically, a data member is also maintained inside the class to determine the maximum number of elements that may be stored in the array (the queue capacity). Another data member is used to keep track of the number of data items currently stored in the vector (the queue size). Both of these data members should be declared as data type size_t (which corresponds to an unsigned integer).
The class also requires two integer data members: the subscript of the front item in the queue (the queue front subscript) and the subscript of the rear item in the queue (the queue rear subscript).
Methods and associated functions
As usual, methods that do not alter the data members of the object that called the method should be declared to be const.
Constructor
The class should have a default constructor that takes no arguments. The constructor should set the queue size and queue capacity to 0 and the queue array pointer to nullptr. The queue front subscript should be initialized to 0. The queue rear subscript should be initialized to the queue capacity - 1. Alternately, the data members can be initialized in the class declaration, in which case this method's body can be empty.
Destructor
The class should have a destructor that deletes the dynamic memory for the queue array. The destructor should NOT call the clear() method.
Copy Constructor
The class should also have a proper copy constructor. This will be similar to the copy constructor you wrote for the Vector class for Assignment 5. The main difference is that you will need to copy the contents of the entire queue array (elements 0 to queue capacity - 1), not just elements 0 to queue size - 1.
Copy Assignment Operator
The copy assignment operator should be properly overloaded to allow one Queue to be assigned to another. Once again, the code here will be similar to what you wrote for Assignment 5. As with the copy constructor, you will need to copy the contents of the entire queue array.
operator<<
The output operator should be overloaded so that a Queue can be printed on the standard output. As in Assignments 4 and 5, this will need to be a standalone friend rather than a method.
Looping through the queue array to print the elements is complicated by the fact that the queue front subscript will not necessarily be less than the queue rear subscript. One way to make this work is to have a counter that controls how many times the loop is done, and a subscript that starts at the front of the queue and is incremented until it reaches the rear of the queue:
clear()
This method takes no arguments and returns nothing. It should properly set the queue back to the empty state (set the queue size to 0, the queue front subscript to 0, and the queue rear subscript to the queue capacity - 1).
size()
This method takes no arguments and returns a size_t. It should return the queue size.
capacity()
This method takes no arguments and returns a size_t. It should return the queue capacity.
empty()
This method takes no arguments and returns a boolean value. It should return true if the queue size is 0; otherwise it should return false.
front()
This method takes no arguments and returns an integer. If the queue is empty, this method should throw an underflow_error exception. Otherwise, it should return the front element of the queue array (the one at the queue front subscript).
back()
This method takes no arguments and returns an integer. If the queue is empty, this method should throw an underflow_error exception. Otherwise, it should return the rear element of the queue array (the one at the queue rear subscript).
push()
This method takes an integer argument, the item to insert into the queue. If the queue is full (the queue size is equal to the queue capacity), this method will need to call the reserve() method to increase the capacity of the queue array and make room for the item to insert. If the queue capacity is currently 0, pass a new capacity of 1 to the reserve() method. Otherwise, pass a new capacity of twice the current queue capacity to the reserve() method.
To insert an item, the method should increment the queue rear subscript (wrapping around to the front of the queue array if needed) and then copy the method argument into the queue array as the new rear item in the queue. The queue size should be incremented by 1.
pop()
This method takes no arguments and returns nothing. If the queue is empty, this method should throw an underflow_error exception. Otherwise, it should increment the queue front subscript (wrapping around to the front of the queue array if needed) to effectively remove the front item in the queue array. The queue size should be decremented by 1.
reserve()
This method takes an unsigned integer argument, the new capacity to allocate for the queue array. It returns nothing. It should reserve additional capacity for the queue array equal to the new capacity passed in.
Note that the "circular" nature of the queue array complicates copying the items from the queue array to the new temporary array. You will need to modify your code from Assignment 5 accordingly.
A driver program, assign6.cpp is provided for this assignment. The purpose of a driver program is to test other pieces that you code. You do not need to write the driver program yourself.
Output
Output from the correctly functioning driver program should look like the following:
Explanation / Answer
Answer:
Program code to copy:
#ifndef Queue_H
#define Queue_H
#include <iostream>
using namespace std;
class Queue
{
private:
int *queueArray;
size_t queueCapacity;
size_t queueSize;
int queueFront;
int queueRear;
public:
Queue();
~Queue();
Queue(const Queue &queue);
Queue& operator=(const Queue &queue);
friend ostream& operator<<(ostream &out, const Queue &queue);
void clear();
size_t size() const;
size_t capacity() const;
bool empty() const;
int front() const;
int back() const;
void push(int item);
void pop();
void reserve(size_t newSize);
};
#endif
#include "stdafx.h"
#include "Queue.h"
#include <iostream>
using namespace std;
Queue::Queue()
{
queueArray = new int[0];
queueSize = 0;
queueCapacity = 0;
queueFront = 0;
queueRear = queueCapacity - 1;
}
Queue::~Queue()
{
delete queueArray;
}
Queue::Queue(const Queue &queue)
{
this->queueArray = queue.queueArray;
this->queueFront = queue.queueFront;
this->queueRear = queue.queueRear;
this->queueSize = queue.queueSize;
this->queueCapacity = queue.queueCapacity;
}
Queue& Queue::operator=(const Queue &queue)
{
this->queueArray = queue.queueArray;
this->queueFront = queue.queueFront;
this->queueRear = queue.queueRear;
this->queueSize = queue.queueSize;
this->queueCapacity = queue.queueCapacity;
return *this;
}
ostream& operator<<(ostream &out, const Queue &queue)
{
size_t current, i;
for (current = queue.queueFront, i = 0; i < queue.queueSize; ++i)
{
// Print queue element at subscript i
out << queue.queueArray[current] << ' ';
// Increment i, wrapping around to front of queue array if necessary
current = (current + 1) % queue.queueCapacity;
}
return out;
}
void Queue::clear()
{
queueSize = 0;
queueCapacity = 0;
queueFront = 0;
queueRear = queueCapacity - 1;
}
size_t Queue::size() const
{
return queueSize;
}
size_t Queue::capacity() const
{
return queueCapacity;
}
bool Queue::empty() const
{
return (queueSize == 0);
}
int Queue::front() const
{
if(empty())
throw underflow_error("underflow error");
else
return queueArray[queueFront];
}
int Queue::back() const
{
if(empty())
throw underflow_error("underflow error");
else
return queueArray[queueRear];
}
void Queue::push(int item)
{
int old = queueCapacity;
if(queueSize == queueCapacity)
{
if(queueSize == 0)
reserve(queueCapacity + 1);
else
reserve(queueCapacity * 2);
}
queueRear = (queueRear + 1 )% (queueCapacity) ;
queueArray[queueRear] = item;
queueSize++;
}
void Queue::pop()
{
if(empty())
throw underflow_error("underflow error");
else
{
queueFront = (queueFront + 1)%queueCapacity;
queueSize--;
}
}
void Queue::reserve(size_t newSize)
{
//queueArray = new int[queueCapacity];
int *newArray = new int[newSize];
if(queueFront > queueRear)
{
int i = 0;
for(i = queueFront; i < queueCapacity ; i++)
{
newArray[i-(queueRear+1)] = queueArray[i];
}
for(int j = 0;j<=queueRear; j++)
{
newArray[i-(queueRear+1)] = queueArray[j];
i++;
}
queueFront = 0;
queueRear = queueCapacity-1;
}
else
{
for(int i = queueFront; i < queueSize; i++)
{
newArray[i] = queueArray[i];
}
}
delete[] queueArray;
queueArray = newArray;
queueCapacity = newSize;
}
// QueuesADTUsingArrays.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <stdexcept>
#include "Queue.h"
using std::cout;
using std::endl;
using std::underflow_error;
int main()
{
cout << "Testing default constructor ";
Queue q1;
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing push() ";
for (int i = 10; i < 80; i+= 10)
q1.push(i);
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing pop() ";
for (int i = 0; i < 3; ++i)
{
q1.pop();
}
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing wrap-around on push() ";
for (int i = 2; i <= 8; i+= 2)
q1.push(i);
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing wrap-around on pop() ";
for (int i = 0; i < 6; ++i)
{
q1.pop();
}
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing queue resize on push() ";
for (int i = 5; i < 70; i+= 5)
q1.push(i);
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing copy constructor() ";
Queue q2 = q1;
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "q2: " << q2 << endl;
cout << "q2 size: " << q2.size() << endl;
cout << "q2 capacity: " << q2.capacity() << endl;
cout << "q2 is " << ((q2.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing front() and back() ";
cout << "Front item of q1: " << q1.front() << endl;
cout << "Front item of q2: " << q2.front() << endl << endl;
cout << "Rear item of q1: " << q1.back() << endl;
cout << "Rear item of q2: " << q2.back() << endl << endl;
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "q2: " << q2 << endl;
cout << "q2 size: " << q2.size() << endl;
cout << "q2 capacity: " << q2.capacity() << endl;
cout << "q2 is " << ((q2.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing pop() to empty ";
while (!q1.empty())
{
cout << q1.front() << ' ';
q1.pop();
}
cout << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 capacity: " << q1.capacity() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing assignment operator ";
Queue q3;
q3 = q2;
cout << "q2 (size " << q2.size() << "): " << q2 << endl;
cout << "q3 (size " << q3.size() << "): " << q3 << endl << endl;
cout << "Testing clear() ";
q2.clear();
cout << "q2 (size " << q2.size() << "): " << q2 << endl;
cout << "q3 (size " << q3.size() << "): " << q3 << endl << endl;
cout << "Testing assignment to self and swap ";
q3 = q3;
q2 = q3;
q3.clear();
cout << "q2 (size " << q2.size() << "): " << q2 << endl;
cout << "q3 (size " << q3.size() << "): " << q3 << endl << endl;
cout << "Testing chained assignment ";
Queue q4;
q4 = q3 = q2;
cout << "q2 (size " << q2.size() << "): " << q2 << endl;
cout << "q3 (size " << q3.size() << "): " << q3 << endl;
cout << "q4 (size " << q4.size() << "): " << q4 << endl << endl;
cout << "Testing const correctness ";
const Queue& r4 = q4;
cout << "q4: " << r4 << endl;
cout << "q4 size: " << r4.size() << endl;
cout << "q4 capacity: " << r4.capacity() << endl;
cout << "q4 is " << ((r4.empty()) ? "empty " : "not empty ");
cout << "Front item of q4: " << r4.front() << endl;
cout << "Rear item of q4: " << r4.back() << endl << endl;
q1 = r4;
cout << "q1: " << q1 << endl;
cout << "q1 size: " << q1.size() << endl;
cout << "q1 is " << ((q1.empty()) ? "empty " : "not empty ");
cout << endl;
q1.clear();
cout << "Testing front() with empty queue ";
try
{
cout << q1.front() << endl;
}
catch (underflow_error e)
{
cout << "Caught "<< e.what() << endl << endl;
}
cout << "Testing back() with empty queue ";
try
{
cout << q1.back() << endl;
}
catch (underflow_error e)
{
cout << "Caught "<< e.what() << endl << endl;
}
cout << "Testing pop() with empty queue ";
try
{
q1.pop();
}
catch (underflow_error e)
{
cout << "Caught "<< e.what() << endl;
}
system("pause");
return 0;
}
Sample output:
Testing default constructor
q1:
q1 size: 0
q1 capacity: 0
q1 is empty
Testing push()
q1: 10 20 30 40 50 60 70
q1 size: 7
q1 capacity: 8
q1 is not empty
Testing pop()
q1: 40 50 60 70
q1 size: 4
q1 capacity: 8
q1 is not empty
Testing wrap-around on push()
q1: 40 50 60 70 2 4 6 8
q1 size: 8
q1 capacity: 8
q1 is not empty
Testing wrap-around on pop()
q1: 6 8
q1 size: 2
q1 capacity: 8
q1 is not empty
Testing queue resize on push()
q1: 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q1 size: 15
q1 capacity: 16
q1 is not empty
Testing copy constructor()
q1: 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q1 size: 15
q1 capacity: 16
q1 is not empty
q2: 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q2 size: 15
q2 capacity: 16
q2 is not empty
Testing front() and back()
Front item of q1: 6
Front item of q2: 6
Rear item of q1: 65
Rear item of q2: 65
q1: 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q1 size: 15
q1 capacity: 16
q1 is not empty
q2: 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q2 size: 15
q2 capacity: 16
q2 is not empty
Testing pop() to empty
6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q1 size: 0
q1 capacity: 16
q1 is empty
Testing assignment operator
q2 (size 15): 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q3 (size 15): 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
Testing clear()
q2 (size 0):
q3 (size 15): 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
Testing assignment to self and swap
q2 (size 15): 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q3 (size 0):
Testing chained assignment
q2 (size 15): 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q3 (size 15): 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q4 (size 15): 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
Testing const correctness
q4: 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q4 size: 15
q4 capacity: 16
q4 is not empty
Front item of q4: 6
Rear item of q4: 65
q1: 6 8 5 10 15 20 25 30 35 40 45 50 55 60 65
q1 size: 15
q1 is not empty
Testing front() with empty queue
Caught underflow error
Testing back() with empty queue
Caught underflow error
Testing pop() with empty queue
Caught underflow error
Press any key to continue . . .