HW11: Project OOP – Inheritance and Polymorphism Part 2 Create a queueclass by p
ID: 3916450 • Letter: H
Question
HW11: Project OOP – Inheritance and Polymorphism
Part 2
Create a queueclass by priviate inherting the unorderedArrayListTypeclass. A queue class is a First-In-First-Out data structure. To understand a queue, think of a cafeteria line: the person at the front is served first (removed), and people are added to the line at the back.
class queue : privateunorderedArrayListType
{
public:
bool isEmpty() const; // test whether queue is empty
// Post: returns true if queue is empty, otherwise returns false
int size() const; // return size
// Post: returns the number of elements in the queue
int front() const; // returns the element at the front of the queue. This should be the "oldest" element, the same element that will be removed if deque() is called next
// Pre: the queue is not empty
// Post: returns the element at the front of the queue
int back() const; // returns the element at the back of the queue. This should be the "youngest" element, the same element that was added into the queue most recently using enque()
// Pre: the queue is not empty
// Post: returns the element at the back of the queue
void enque(intnewItem); // insert one element at the back of the queue, after its current last element (the "youngest" element before this enque)
// Post: newItem added at the end of the queue, after the current last element
int deque(); // remove one element from the front of the queue. The "oldest" element should be removed
// Pre: the queue is not empty
// Post: the item at the front of the queue is removed from the queue and returned
queue(int size = 100);
// Post: queue initialized with capacity being size and contains 0 elements.
// if no size is specified, 100 is used for the capacity
};
Overload the output operator <<for the queueclass so you can easily print out a queue (add function prologue, param type and pre-/post- comments). You have to overload it due to the private inheritance.
Add appropriate code into mainto test your queue class (you may delete the existing code in main at this point). Be sure to test each function and print out current content of a queue object.
Additional requirements:
You should not directly access the int* listdata member of the arrayListTypeclass in your implementation (0 credits if you did). Instead, you should call existing functions provided in the .cpp file.
You should not modify the given arrayListType/ unorderedArrayListTypecode (0 credits if you did), except for deleting the given maincode and breaking the code into header + implementation (see next requirement).
Code that needs to be worked is included below:
#include<iostream>
//--------------
// arrayListType (super)
//--------------
classarrayListType
{
friendstd::ostream& operator<<(std::ostream&, constarrayListType&);
public:
boolisEmpty()const;
boolisFull()const;
intlistSize()const;
intmaxListSize()const;
boolisItemAtEqual(intlocation, intitem) const;
voidremoveAt(intlocation);
voidretrieveAt(intlocation, int& retItem) const;
voidclearList();
virtualintseqSearch(intsearchItem) const= 0;
virtualvoidinsertAt(intlocation, intinsertItem) = 0;
virtualvoidinsertEnd(intinsertItem) = 0;
virtualvoidreplaceAt(intlocation, intrepItem) = 0;
virtualvoidremove(intremoveItem) = 0;
arrayListType(intsize = 100);
arrayListType(constarrayListType& otherList);
virtual~arrayListType();
protected:
int*list; //array to hold the list elements
intlength; //length of the list
intmaxSize; //the maximum size of the list
};
//--------------
// unorderedArrayListType (sub)
//--------------
classunorderedArrayListType: publicarrayListType
{
public:
voidinsertAt(intlocation, intinsertItem);
voidinsertEnd(intinsertItem);
voidreplaceAt(intlocation, intrepItem);
intseqSearch(intsearchItem) const;
voidremove(intremoveItem);
unorderedArrayListType(intsize = 100); //Constructor
};
//--------------
// queue (grand-sub)
//--------------
classqueue: privateunorderedArrayListType
{
public:
boolisEmpty()const; // test whether queue is empty
// Post: returns true if queue is empty, otherwise returns false
intsize()const; // return size
// Post: returns the number of elements in the queue
intfront()const; // returns the element at the front of the queue. This should be the "oldest" element, the same element that will be removed if deque() is called next
// Pre: the queue is not empty
// Post: returns the element at the front of the queue
intback()const; // returns the element at the back of the queue. This should be the "youngest" element, the same element that was added into the queue most recently using enque()
// Pre: the queue is not empty
// Post: returns the element at the back of the queue
voidenque(intnewItem); // insert one element at the back of the queue, after its current last element (the "youngest" element before this enque)
// Post: newItem added at the end of the queue, after the current last element
intdeque();// remove one element from the front of the queue. The "oldest" element should be removed
// Pre: the queue is not empty
// Post: the item at the front of the queue is removed from the queue and returned
queue(intsize = 100);
// Post: queue initialized with capacity being size paramand contains 0 elements.
// if no size is specified, 100 is used for the capacity
};
//--------------
// client code
//--------------
intmain()
{
unorderedArrayListTypeintList(25);
for(inti = 0; i < 8; i++)
intList.insertEnd(i * 10 + 5);
std::cout << "intList: "<< intList << std::endl;
//Create tempand initialize it using intList
unorderedArrayListTypetemp(intList);
std::cout << "temp: "<< temp << std::endl;
//Replace the first element of temp.
temp.replaceAt(0, -75);
std::cout << "tempfirst element replaced: "<< temp << std::endl;
std::cout << "intList: "<< intList << std::endl;
return0;
} // end main
//---------------------
// Implementation
//---------------------
boolarrayListType::isEmpty()const
{
return(length== 0);
} //end isEmpty
boolarrayListType::isFull()const
{
return(length== maxSize);
} //end isFull
intarrayListType::listSize()const
{
returnlength;
} //end listSize
intarrayListType::maxListSize()const
{
returnmaxSize;
} //end maxListSize
boolarrayListType::isItemAtEqual(intlocation, intitem) const
{
if(location < 0 || location >= length)
{
std::cout << "The location of the item to be removed "
<< "is out of range. ";
returnfalse;
}
else
return(list[location] == item);
} //end isItemAtEqual
voidarrayListType::removeAt(intlocation)
{
if(location < 0 || location >= length)
std::cout << "The location of the item to be removed "
<< "is out of range. ";
else
{
for(inti = location; i < length- 1; i++)
list[i] = list[i + 1];
length--;
}
} //end removeAt
voidarrayListType::retrieveAt(intlocation, int& retItem) const
{
if(location < 0 || location >= length)
std::cout << "The location of the item to be retrieved is "
<< "out of range ";
else
retItem = list[location];
} //end retrieveAt
voidarrayListType::clearList()
{
length= 0;
} //end clearList
arrayListType::arrayListType(intsize)
{
if(size <= 0)
{
std::cout << "The array size must be positive. Creating "
<< "an array of the size 100. ";
maxSize= 100;
}
else
maxSize= size;
length= 0;
list= newint[maxSize];
//std::cout<< "constructor of alt: " << this << " "; // testing
} //end constructor
arrayListType::~arrayListType()
{
delete[] list;
//std::cout<< "destructorof alt: " << this << " "; // testing
} //enddestructor
arrayListType::arrayListType(constarrayListType& otherList)
{
maxSize= otherList.maxSize;
length= otherList.length;
list= newint[maxSize]; //create the array
for(intj = 0; j < length; j++) //copy otherList
list[j] = otherList.list[j];
//std::cout<< "copy constructor of alt: " << this << " "; // testing
}//end copy constructor
//--------------------
// non-member, friend
//--------------------
std::ostream& operator<<(std::ostream& out, constarrayListType& obj)
{
for(inti = 0; i < obj.length; i++)
out << obj.list[i] << " ";
returnout;
} //end operator<<
//---------------------
//---------------------
voidunorderedArrayListType::insertAt(intlocation,
intinsertItem)
{
if(location < 0 || location >= maxSize)
std::cout << "The position of the item to be inserted "
<< "is out of range. ";
elseif(length>= maxSize) //list is full
std::cout << "Cannot insert in a full list ";
else
{
for(inti = length; i > location; i--)
list[i] = list[i - 1]; //move the elements down
list[location] = insertItem; //insert the item at
//the specified position
length++; //increment the length
}
} //end insertAt
voidunorderedArrayListType::insertEnd(intinsertItem)
{
if(length>= maxSize) //the list is full
std::cout << "Cannot insert in a full list. ";
else
{
list[length] = insertItem; //insert the item at the end
length++; //increment the length
}
} //end insertEnd
intunorderedArrayListType::seqSearch(intsearchItem) const
{
for(intloc = 0; loc < length; loc++)
if(list[loc] == searchItem)
returnloc;
return-1; // not found
} //end seqSearch
voidunorderedArrayListType::remove(intremoveItem)
{
if(length== 0)
std::cout << "Cannot delete from an empty list. ";
else
{
intloc = seqSearch(removeItem);
if(loc != -1)
removeAt(loc);
else
std::cout << "The item to be deleted is not in the list .";
}
} //end remove
voidunorderedArrayListType::replaceAt(intlocation, intrepItem)
{
if(location < 0 || location >= length)
std::cout << "The location of the item to be "
<< "replaced is out of range. ";
else
list[location] = repItem;
} //end replaceAt
unorderedArrayListType::unorderedArrayListType(intsize)
: arrayListType(size)
{
//std::cout<< "constructor of unorderedalt: " << this << " "; // testing
} //end constructor
//---------------------
//---------------------
class queue : privateunorderedArrayListType
{
public:
bool isEmpty() const; // test whether queue is empty
// Post: returns true if queue is empty, otherwise returns false
int size() const; // return size
// Post: returns the number of elements in the queue
int front() const; // returns the element at the front of the queue. This should be the "oldest" element, the same element that will be removed if deque() is called next
// Pre: the queue is not empty
// Post: returns the element at the front of the queue
int back() const; // returns the element at the back of the queue. This should be the "youngest" element, the same element that was added into the queue most recently using enque()
// Pre: the queue is not empty
// Post: returns the element at the back of the queue
void enque(intnewItem); // insert one element at the back of the queue, after its current last element (the "youngest" element before this enque)
// Post: newItem added at the end of the queue, after the current last element
int deque(); // remove one element from the front of the queue. The "oldest" element should be removed
// Pre: the queue is not empty
// Post: the item at the front of the queue is removed from the queue and returned
queue(int size = 100);
// Post: queue initialized with capacity being size and contains 0 elements.
// if no size is specified, 100 is used for the capacity
};
Explanation / Answer
#include<iostream>
//--------------
// arrayListType (super)
//--------------
class arrayListType
{
friend std::ostream& operator<<(std::ostream&, const arrayListType&);
public:
bool isEmpty()const;
bool isFull()const;
int listSize()const;
int maxListSize()const;
bool isItemAtEqual(int location, int item) const;
void removeAt(int location);
void retrieveAt(int location, int& retItem) const;
void clearList();
virtual int seqSearch(int searchItem) const= 0;
virtual void insertAt(int location, int insertItem) = 0;
virtual void insertEnd(int insertItem) = 0;
virtual void replaceAt(int location, int repItem) = 0;
virtual void remove(int removeItem) = 0;
arrayListType(int size = 100);
arrayListType(const arrayListType& otherList);
virtual ~arrayListType();
protected:
int *list; //array to hold the list elements
int length; //length of the list
int maxSize; //the maximum size of the list
};
//--------------
// unorderedArrayListType (sub)
//--------------
class unorderedArrayListType: public arrayListType
{
public:
void insertAt(int location, int insertItem);
void insertEnd(int insertItem);
void replaceAt(int location, int repItem);
int seqSearch(int searchItem) const;
void remove(int removeItem);
unorderedArrayListType(int size = 100); //Constructor
};
//--------------
// queue (grand-sub)
//--------------
class queue: private unorderedArrayListType
{
friend std::ostream& operator<<(std::ostream&, const queue&);
public:
bool isEmpty()const; // test whether queue is empty
// Post: returns true if queue is empty, otherwise returns false
int size()const; // return size
// Post: returns the number of elements in the queue
int front()const; // returns the element at the front of the queue. This should be the "oldest" element, the same element that will be removed if deque() is called next
// Pre: the queue is not empty
// Post: returns the element at the front of the queue
int back()const; // returns the element at the back of the queue. This should be the "youngest" element, the same element that was added into the queue most recently using enque()
// Pre: the queue is not empty
// Post: returns the element at the back of the queue
void enque(int newItem); // insert one element at the back of the queue, after its current last element (the "youngest" element before this enque)
// Post: newItem added at the end of the queue, after the current last element
int deque();// remove one element from the front of the queue. The "oldest" element should be removed
// Pre: the queue is not empty
// Post: the item at the front of the queue is removed from the queue and returned
queue(int size = 100);
// Post: queue initialized with capacity being size paramand contains 0 elements.
// if no size is specified, 100 is used for the capacity
};
//--------------
// client code
//--------------
int main()
{
unorderedArrayListType intList(25);
for(int i = 0; i < 8; i++)
intList.insertEnd(i * 10 + 5);
std::cout << "intList: "<< intList << std::endl;
//Create tempand initialize it using intList
unorderedArrayListType temp(intList);
std::cout << "temp: "<< temp << std::endl;
//Replace the first element of temp.
temp.replaceAt(0, -75);
std::cout << "tempfirst element replaced: "<< temp << std::endl;
std::cout << "intList: "<< intList << std::endl;
queue queueList(10);
for(int i = 0; i < 8; i++)
queueList.enque(i * 10 + 5);
std::cout << "queueList: "<< queueList << std::endl;
queueList.deque();
queueList.deque();
std::cout << "after 2 deque statements; queueList: "<< queueList << std::endl;
return 0;
} // end main
//---------------------
// Implementation
//---------------------
bool arrayListType::isEmpty()const
{
return(length== 0);
} //end isEmpty
bool arrayListType::isFull()const
{
return(length== maxSize);
} //end isFull
int arrayListType::listSize()const
{
return length;
} //end listSize
int arrayListType::maxListSize()const
{
return maxSize;
} //end maxListSize
bool arrayListType::isItemAtEqual(int location, int item) const
{
if(location < 0 || location >= length)
{
std::cout << "The location of the item to be removed "
<< "is out of range. ";
return false;
}
else
return(list[location] == item);
} //end isItemAtEqual
void arrayListType::removeAt(int location)
{
if(location < 0 || location >= length)
std::cout << "The location of the item to be removed "
<< "is out of range. ";
else
{
for(int i = location; i < length- 1; i++)
list[i] = list[i + 1];
length--;
}
} //end removeAt
void arrayListType::retrieveAt(int location, int& retItem) const
{
if(location < 0 || location >= length)
std::cout << "The location of the item to be retrieved is "
<< "out of range ";
else
retItem = list[location];
} //end retrieveAt
void arrayListType::clearList()
{
length= 0;
} //end clearList
arrayListType::arrayListType(int size)
{
if(size <= 0)
{
std::cout << "The array size must be positive. Creating "
<< "an array of the size 100. ";
maxSize= 100;
}
else
maxSize= size;
length= 0;
list= new int[maxSize];
//std::cout<< "constructor of alt: " << this << " "; // testing
} //end constructor
arrayListType::~arrayListType()
{
delete[] list;
//std::cout<< "destructorof alt: " << this << " "; // testing
} //enddestructor
arrayListType::arrayListType(const arrayListType& otherList)
{
maxSize= otherList.maxSize;
length= otherList.length;
list= new int[maxSize]; //create the array
for(int j = 0; j < length; j++) //copy otherList
list[j] = otherList.list[j];
//std::cout<< "copy constructor of alt: " << this << " "; // testing
}//end copy constructor
//--------------------
// non-member, friend
//--------------------
std::ostream& operator<<(std::ostream& out, const arrayListType& obj)
{
for(int i = 0; i < obj.length; i++)
out << obj.list[i] << " ";
return out;
} //end operator<<
//---------------------
//---------------------
void unorderedArrayListType::insertAt(int location,
int insertItem)
{
if(location < 0 || location >= maxSize)
std::cout << "The position of the item to be inserted "
<< "is out of range. ";
else if(length>= maxSize) //list is full
std::cout << "Cannot insert in a full list ";
else
{
for(int i = length; i > location; i--)
list[i] = list[i - 1]; //move the elements down
list[location] = insertItem; //insert the item at
//the specified position
length++; //increment the length
}
} //end insertAt
void unorderedArrayListType::insertEnd(int insertItem)
{
if(length>= maxSize) //the list is full
std::cout << "Cannot insert in a full list. ";
else
{
list[length] = insertItem; //insert the item at the end
length++; //increment the length
}
} //end insertEnd
int unorderedArrayListType::seqSearch(int searchItem) const
{
for(int loc = 0; loc < length; loc++)
if(list[loc] == searchItem)
return loc;
return -1; // not found
} //end seqSearch
void unorderedArrayListType::remove(int removeItem)
{
if(length== 0)
std::cout << "Cannot delete from an empty list. ";
else
{
int loc = seqSearch(removeItem);
if(loc != -1)
removeAt(loc);
else
std::cout << "The item to be deleted is not in the list .";
}
} //end remove
void unorderedArrayListType::replaceAt(int location, int repItem)
{
if(location < 0 || location >= length)
std::cout << "The location of the item to be "
<< "replaced is out of range. ";
else
list[location] = repItem;
} //end replaceAt
unorderedArrayListType::unorderedArrayListType(int size)
: arrayListType(size)
{
//std::cout<< "constructor of unorderedalt: " << this << " "; // testing
} //end constructor
//---------------------
//---------------------
bool queue::isEmpty()const{
return(length== 0);
}
int queue::size()const{
return length;
}
int queue::front()const{
int defaultValue = -99;
if( !isEmpty()){
int location = 0;
int retItem;
retrieveAt(location, retItem);
return(retItem) ;
}
else { std::cout << "queue is empty, no element to retreive, returns -99 (default)"<< std::endl;
return(defaultValue);
}
}
int queue::back()const{
int defaultValue = -99;
if( !isEmpty()){
int location = length -1 ;
int retItem;
retrieveAt(location, retItem);
return(retItem) ;
}
else { std::cout << "queue is empty, no element to retreive, returns -99 (default)"<< std::endl;
return(defaultValue);
}
}
void queue::enque(int newItem){
insertEnd( newItem);
}
int queue::deque(){
int defaultValue = -99;
int location = length -1 ;
if( !isEmpty()){
int retItem;
retrieveAt(location, retItem);
removeAt(location);
return(retItem);
}
else { std::cout << "queue is empty, no element to retreive, returns -99 (default)"<< std::endl;
return(defaultValue);
}
}
queue::queue(int size)
{
if (size < 0){
std::cout << "Queue size should be positive" << std::endl;
}
else{
maxSize= size;
length= 0;
list= new int[maxSize];
}
}
std::ostream& operator<<(std::ostream& out, const queue& obj)
{
for(int i = 0; i < obj.length; i++)
out << obj.list[i] << " ";
return out;
} //end operator<<
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.