Write an array$-$based implementation of a queue that uses a resizable, circular array to represent the items in the queue. Start with the files that I am linking to below. Your class should have a DEFAULT$\_$CAPACITY constant and also a capacity data member. For submission purposes, set the DEFAULT$\_$CAPACITY to $1.$ Your class should double the size of the array when an attempt is made to enqueue an item when the capacity is full. After the first doubling of the array, halve the size of the queue when a pop results in fewer than half of the array's locations being occupied by current queue items. You will need to change the push$()$ and pop$()$ functions to void instead of bool. push$()$ will be void because it is no longer possible to exceed the queue's capacity. pop$()$ will be void because you should throw a PrecondViolatedExcep exception if the queue is empty, instead of returning false. You'll also need to make these two small changes in the Queue$\_$Interface.h file.$$

QueueInterface.h:

#ifndef QUEUE$\_$INTERFACE$\_$

#define QUEUE$\_$INTERFACE$\_$

template

class QueueInterface

$\{$

public:

virtual bool empty$()$ const $=0$;

virtual bool push$($const ItemType& newEntry$)=0$;

virtual ~QueueInterface$()\{\}$

$\}$;

#endif

$$ArrayQueue$.$cpp:

#include

template

ArrayQueue::ArrayQueue$()\{$

qfront $=0$;

back $=$ DEFAULT$\_$CAPACITY $-1$;

numItems $=0$;

$\}$

template

bool ArrayQueue::empty$()$ const $\{$

return numItems $==0$;

$\}$

template

bool ArrayQueue::push$($const ItemType& newEntry$)$

$\{$

bool result $=$ false;

if $($numItems $<$ DEFAULT$\_$CAPACITY$)\{$

back $=($back $+1)\%$ DEFAULT$\_$CAPACITY;

items$[$back$]=$ newEntry;

numItems$++$;

result $=$ true;

$\}$

return result;

$\}$

template

bool ArrayQueue::pop$()$

$\{$

bool result $=$ false;

if $(!$empty$())\{$

qfront $=($qfront $+1)\%$ DEFAULT$\_$CAPACITY;

numItems$--$;

result $=$ true;

$\}$

return result;

$\}$

template

ItemType ArrayQueue::front$()$ const

$\{$

if $($empty$())\{$

throw PrecondViolatedExcep$("$peekFront$()$ called with empty queue"$)$;

$\}$

return items$[$qfront$]$;

$\}$

template

void ArrayQueue::print$()$ const $\{$

std::cout $<<$ "Here is the queue: $"$;

if $($empty$())\{$

std::cout $<<$ "empty";

$\}$ else $\{$

for $($int i $=$ qfront; i $!=$ back; i $=($i $+1)\%$ DEFAULT$\_$CAPACITY$)\{$

std::cout $<<$ items$[$i$]<<""$;

$\}$

std::cout $<<$ items$[$back$]$;

$\}$

$\}$

$$ArrayQueue$.$h$$:

#ifndef ARRAY$\_$QUEUE$\_$H

#define ARRAY$\_$QUEUE$\_$H

#include "QueueInterface.h$"$

#include "PrecondViolatedExcep.h$"$

template

class ArrayQueue : public QueueInterface

$\{$

public:

ArrayQueue$()$;

bool empty$()$ const;

bool push$($const ItemType& newEntry$)$;

bool pop$()$;

ItemType front$()$ const;

void print$()$ const;

private:

static const int DEFAULT$\_$CAPACITY $=100$;

ItemType items$[$DEFAULT$\_$CAPACITY$]$;

int qfront;

int back;

int numItems;

$\}$;

#include "ArrayQueue.cpp$"$

#endif$$

$$PrecondViolatedExcep$.$cpp:

$$#include "PrecondViolatedExcep.h$"$

PrecondViolatedExcep::PrecondViolatedExcep$($const std::string& message$)$

: std::logic$\_$error$("$Precondition Violated Exception: $"+$ message$)$

$\{$

$\}$

PrecondViolatedExcep.h:

#ifndef PRECOND$\_$VIOLATED$\_$EXCEP$\_$H

#define PRECOND$\_$VIOLATED$\_$EXCEP$\_$H

#include

#include

class PrecondViolatedExcep : public std::logic$\_$error

$\{$

public:

PrecondViolatedExcep$($const std::string& message $="")$;

$\}$;

#include "PrecondViolatedExcep.cpp$"$

#endif