Purpose This assignment is an exercise in implementing the queue ADT using an ar
ID: 3686385 • Letter: P
Question
Purpose
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 back item in the queue (the queue back 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 back 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 back 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 back 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 back 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 back element of the queue array (the one at the queue back 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 back 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 back 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.
Output
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. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2016/Assign6/assign6.cpp.
Output
Output from the correctly functioning driver program should look like the following:
Other Points
A makefile is required. Same as always. Make sure it has appropriate rules for all the pieces involved.
Explanation / Answer
main.cpp
#include <iostream>
#include <stdexcept>
#include "Stack.h"
using std::cin;
using std::cout;
using std::endl;
using std::out_of_range;
int main()
{
cout << "Testing default constructor ";
Stack s1;
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing push() ";
for (int i = 10; i < 80; i+= 10)
s1.push(i);
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
for (int i = 15; i < 85; i+= 10)
s1.push(i);
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing copy constructor() ";
Stack s2 = s1;
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing top() ";
cout << "Top item of s1: " << s1.top() << endl << endl;
cout << "Testing pop() Top item of s1: ";
while (!s1.empty())
{
cout << s1.top() << ' ';
s1.pop();
}
cout << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing assignment operator ";
Stack s3;
s3 = s2;
cout << "s2 (size " << s2.size() << "): " << s2 << endl;
cout << "s3 (size " << s3.size() << "): " << s3 << endl << endl;
cout << "Testing clear() ";
s2.clear();
cout << "s2 (size " << s2.size() << "): " << s2 << endl;
cout << "s3 (size " << s3.size() << "): " << s3 << endl << endl;
cout << "Testing assignment to self and swap ";
s3 = s3;
s2 = s3;
s3.clear();
cout << "s2 (size " << s2.size() << "): " << s2 << endl;
cout << "s3 (size " << s3.size() << "): " << s3 << endl << endl;
cout << "Testing chained assignment ";
Stack s4;
s4 = s3 = s2;
cout << "s2 (size " << s2.size() << "): " << s2 << endl;
cout << "s3 (size " << s3.size() << "): " << s3 << endl;
cout << "s4 (size " << s4.size() << "): " << s4 << endl << endl;
cout << "Testing const correctness ";
const Stack& r4 = s4;
cout << "s4: " << r4 << endl;
cout << "s4 size: " << r4.size() << endl;
cout << "s4 is " << ((r4.empty()) ? "empty " : "not empty ");
cout << "Top item of s4: " << r4.top() << endl << endl;
s1 = r4;
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
s1.clear();
cout << "Testing top() with empty stack ";
try
{
cout << s1.top() << endl;
}
catch (out_of_range orex)
{
cout << "Exception: "<< orex.what() << endl << endl;
}
cout << "Testing pop() with empty stack ";
try
{
s1.pop();
}
catch (out_of_range orex)
{
cout << "Exception: "<< orex.what() << endl;
}
return 0;
}
Stack.cpp
#include "Stack.h"
Stack::Stack()
{
stackCapacity = 8;//initial stack Capacity
stackAR = new int[stackCapacity];//allocate array
stackSize = 0;//empty array
stackTop = -1;
}
Stack::~Stack()
{
delete [] stackAR;
}
Stack::Stack(const Stack& s)
{
stackSize = s.stackSize;//size equal to arg object size
stackAR = new int[stackCapacity];//stack array
stackCapacity = s.stackCapacity;//capacity equal to arg
//object capacity
for(int i = 0; i < stackSize; i++)
{
stackAR[i] = s.stackAR[i];
}//copy arg object array
}
Stack& Stack::operator=(const Stack& rightOp)
{
if(&rightOp != this)//if addresses not equal
{
delete[] stackAR;
stackSize = rightOp.stackSize;//size equals arg size
stackCapacity = rightOp.stackCapacity;//capacities equal
stackTop = rightOp.stackSize - 1;//top subs equal //arg capacity
stackAR = new int[stackCapacity];//allocate array
for(int i = 0; i < stackSize; i++)
{
stackAR[i] = rightOp.stackAR[i];
}//copy arg array
}
return *this;//calling object
}
void Stack::clear()
{
stackSize = 0;//empty array
stackTop = -1;
}
int Stack::size() const
{
return stackSize;
}
bool Stack::empty() const
{
if(stackSize == 0)//if empty
return true;
else//if not empty
return false;
}
int Stack::top() const
{
if(stackSize == 0)//if empty
throw out_of_range("Stack underflow on top()");
else//if not empty
return stackAR[stackTop];
}
void Stack::push(int item)
{
if((stackSize == stackCapacity))//if array needs resizing
{
stackCapacity = stackCapacity * 2 ;//double array capacity
int * tempAR;//new temp pointer to int
tempAR = new int[stackCapacity];//allocate array
for(int i = 0; i < stackSize; i++)
{
tempAR[i] = stackAR[i];
}//copy arg array
delete [] stackAR;//remove array
stackAR = tempAR; //set array to address of temp array
}
//insert new item into stack
stackTop++;
stackAR[stackTop] = item;
stackSize++;
}
void Stack::pop()
{
if(stackSize == 0)//if empty
throw out_of_range("Stack underflow on pop()");
else//if not empty
{
//remove top element of stack
stackTop--;
stackSize--;
}
}
//stand alone functions
ostream& operator<<(ostream& leftOp, const Stack& rightOp)
{
for(int i = 0; i < rightOp.size(); i++)
{
//print stack as standard output
leftOp << rightOp.stackAR[i] << ' ';
}
return leftOp;
}
Stack.h
#ifndef Stack_H
#define Stack_H
#include <iostream>
#include <stdexcept>
using namespace std;
class Stack
{
//friend declarations
friend ostream& operator<<(ostream&, const Stack&);//output operator
private:
// Data members
int * stackAR;
int stackCapacity;
int stackSize;
int stackTop;
public:
//constructors
Stack();
//destructor
~Stack();
//copy constructor
Stack(const Stack& s);
//operator overloads
Stack& operator=(const Stack& rightOp); //assignment operator
//methods
void clear();
int size() const;
bool empty() const;
int top() const;
void push(int item);
void pop();
};
#endif
sample output
Testing default constructor
s1:
s1 size: 0
s1 is empty
Testing push()
s1: 10 20 30 40 50 60 70
s1 size: 7
s1 is not empty
s1: 10 20 30 40 50 60 70 15 25 35 45 55 65 75
s1 size: 14
s1 is not empty
Testing pop()
Top item of s1: 75 65 55 45 35 25 15 70 60 50 40 30 20 10
s1 size: 0
s1 is empty
Testing assignment operator
s2 (size 14): 10 20 30 40 50 60 70 15 25 35 45 55 65 75
s3 (size 14): 10 20 30 40 50 60 70 15 25 35 45 55 65 75
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.