Create two helper methods for the Queue class: 1. Create a method on the Queue c
ID: 3815365 • Letter: C
Question
Create two helper methods for the Queue class:
1. Create a method on the Queue class that calculates the number of times a given value occurs in the queue.
size_t Queue::count( const T & data ) const;
2. Create a method on the Queue class that determines whether the queue is in descending order.
bool Queue::isDecreasing( ) const;
The starter files code is provided below. Do not alter the class definition or driver code in any way. Programs that crash are subject to a 50% penalty. Please submit the class header file only ("Queue.h”). PLEASE NOTE: You may not use any Standard Template Library (STL) classes for this; use code provided below only.
queue.h:
#pragma once
#include
namespace cs20a
{
template
class queue {
public:
queue();
explicit queue(size_t capacity);
queue(const queue &rhs);
~queue();
queue& operator =(const queue & rhs);
bool operator==(queue & rhs) const;
bool operator!=(queue & rhs) const;
void enqueue(const T& val);
T dequeue();
T peek() const;
void clear();
bool empty() const;
bool full() const;
size_t size() const;
void print();
//*** Implement these methods only. ***
size_t count(const T &data) const;
bool isDecreasing() const;
//*** *** *** *** *** *** *** *** ***
private:
T* elements;
size_t _front, _size, _capacity;
void makeEmpty();
void init(size_t capacity = 2);
void copy(const queue& rhs);
void resize(size_t newCapacity);
};
template
queue::queue() {
init();
}
template
queue::queue(size_t capacity) {
init(capacity);
}
template
queue::~queue() {
makeEmpty();
}
template
queue::queue(const queue &rhs) {
init(rhs._capacity);
copy(rhs);
}
template
queue& queue::operator=(const queue& rhs) {
if (this != &rhs) {
clear();
copy(rhs);
}
return *this;
}
template
bool queue::operator==(queue& rhs) const {
if (_size != rhs._size)
return false;
size_t size = 0;
size_t i = _front;
size_t j = rhs._front;
while (size++ < _size) {
if (elements[i] != rhs.elements[j])
return false;
i = ((i + 1) % _capacity);
j = ((j + 1) % rhs._capacity);
}
return true;
}
template
bool queue::operator!=(queue& rhs) const {
return !(this == &rhs);
}
template
void queue::clear() {
makeEmpty();
init();
}
template
bool queue::empty() const {
return _size == 0;
}
template
bool queue::full() const {
return _size == _capacity;
}
template
size_t queue::size() const {
return _size;
}
template
void queue::makeEmpty() {
delete[] elements;
}
template
void queue::init(size_t capacity) {
_front = _size = 0;
_capacity = capacity;
elements = new T[_capacity];
}
template
void queue::copy(const queue& rhs) {
size_t i = rhs._front;
while (_size < rhs._size) {
enqueue(rhs.elements[i]);
i = ((i + 1) % rhs._capacity);
}
}
template
void queue::resize(size_t minCapacity) {
if (minCapacity < _size)
return;
if (minCapacity >= 0)
{
size_t limit = 1;
while (limit <= minCapacity)
limit <<= 1;
T *tarray = new T[limit];
for (size_t i = 0; i < _size; i++)
tarray[i] = elements[(i + _front) % _capacity];
delete[] elements;
elements = tarray;
_capacity = limit;
}
}
template
void queue::enqueue(const T& val) {
if (full())
resize(_size + 1);
elements[(_front + _size) % _capacity] = val;
_size++;
}
template
T queue::dequeue() {
T item = elements[_front];
_front = (_front + 1) % _capacity;
_size--;
return item;
}
template
T queue::peek() const {
return elements[_front];
}
template
void queue::print() {
cout << "front=[" << _front << "]" << " ";
cout << "rear=[" << (_front + _size) % _capacity << "]" << endl;
if (empty())
{
cout << "Empty queue." << endl;
return;
}
size_t i = _front;
size_t rear = (_front + _size) % _capacity;
std::cout << " --> ";
do
{
std::cout << "[" << i << "]:" << elements[i];
i = (i + 1) % _capacity;
if (i != rear)
cout << " --> ";
} while (i != rear);
std::cout << endl;
}
//*** Implement count() and isDecreasing() here. ***
}
QueueMenu.cpp:
// Menu.cpp : Defines the entry point for the console application.
//
#include
#include "Queue.h"
using namespace std;
using namespace cs20a;
enum CHOICE { MAKEEMPTY, ENQUEUE, ISEMPTY, DEQUEUE, GETFRONT, COUNT, DECREASING, QUIT, PRINT, OTHER };
CHOICE menu();
int main(int argc, char* argv[]) {
int value, total;
queue queue;
CHOICE choice;
do {
choice = menu();
switch (choice) {
case MAKEEMPTY:
queue.clear();
break;
case ISEMPTY:
if (queue.empty())
cout << "Queue is empty." << endl;
else
cout << "Queue is not empty" << endl;
break;
case DEQUEUE:
if (queue.empty())
cout << "Queue is empty." << endl;
else
cout << "Here's the value on top that got dequeued: " << queue.dequeue() << "." << endl;
break;
case GETFRONT:
if (queue.empty())
cout << "Queue is empty." << endl;
else
cout << "Here's the value on top: " << queue.peek() << endl;
break;
case ENQUEUE:
cout << "Please provide int to enqueue: ";
cin >> value;
queue.enqueue(value);
break;
case DECREASING:
if (queue.empty()) {
cout << "Queue is empty." << endl;
}
else if (queue.isDecreasing())
cout << "queue is decreasing" << endl;
else
cout << "queue is not decreasing" << endl;
break;
case COUNT:
cout << "Please provide int to count: ";
cin >> value;
total = queue.count(value);
cout << value << " appears " << total << " times. " << endl;
break;
case PRINT:
queue.print();
cout << endl;
break;
case OTHER:
cout << "Not a valid choice." << endl;
}
} while (choice != QUIT);
return(0);
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty I(s)Empty (E)nqueue (D)equeue (G)etFront (C)ount Dec(r)easing (P)rint (Q)uit: " << endl;
cin >> choice;
switch (choice) {
case 'E':
case 'e':
result = ENQUEUE;
break;
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'D':
case 'd':
result = DEQUEUE;
break;
case 'G':
case 'g':
result = GETFRONT;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'C':
case 'c':
result = COUNT;
break;
case 'R':
case 'r':
result = DECREASING;
break;
case 'P':
case 'p':
result = PRINT;
break;
default:
result = OTHER;
break;
}
return(result);
}
Example: count function Result Queue int> count (5) 3 front->(1) (1) (5) (3) (5) (5) (2) K-back count (10) 0 front- (1) (1) (5) (3) (5) (5) (5) (2) -backExplanation / Answer
template
bool queue::isDecreasing() const {
if (empty())
{
return true;
}
T item = elements[_front];
// traverse till last
size_t i = _front;
size_t rear = (_front + _size) % _capacity;
// in each step, we compare current item to the last item found
do
{
i = (i + 1) % _capacity;
// if this element is greater than last element, return false
if (elements[i] > item)
return false;
// update the item to this item
item = elements[i];
} while (i != rear);
// if no violations were found, return true
return true;
}
template
size_t queue::count(const T &data) const {
if (empty())
{
cout << "Empty queue." << endl;
return 0;
}
// initialize the count by 0
size_t count = 0;
size_t i = _front;
size_t rear = (_front + _size) % _capacity;
// loop on all elements.. check if element matches
do
{
i = (i + 1) % _capacity;
if (elements[i] == data)
count++;
} while (i != rear);
// return the count
return count;
}