C$++$ Create a subclass of our Array class in a Deque.h file that is templated for any type and that implements the following methods:

readFront: Returns the value of the first element in the array.

readBack: Returns the value of the last element in the array.

addFront: Inserts a new value at the front of the array.

addBack: Inserts a new value at the end of the array.

removeFront: Removes the first element of the array.

removeBack: Removes the last element of the array.

Deques work a lot like a cross breed between a queue and a stack.

Use this array class:

#ifndef ARRAY$\_$H

#define ARRAY$\_$H

#include

using namespace std;

template

class Array $\{$

protected:

TYPE$*$ values;

int size;

int capacity;

int startingCapacity;

public:

Array$($int capacity$)$ :

size$(0),$

capacity$($capacity$),$

startingCapacity$($capacity$)\{$

values $=$ new TYPE$[$capacity$]$;

$\}$

Array$()$ : Array$(10)\{\}$

~Array$()\{$

delete$[]$ values;

$\}$

int getSize$()\{$

return this$->$size;

$\}$

TYPE$*$ getValues$()\{$

return this$->$values;

$\}$

void resize$()\{$

TYPE$*$ temp $=$ values;

capacity $+=$ startingCapacity;

values $=$ new TYPE$[$capacity$]$;

for$($int i $=0$; i $<$ this$->$size; i$++)\{$

values$[$i$]=$ temp$[$i$]$;

$\}$

delete$[]$ temp;

$\}$

TYPE get$($int index$)\{$

return values$[$index$]$;

$\}$

void add$($TYPE value$)\{$

if$($this$->$size $==$ this$->$capacity$)$

this$->$resize$()$;

values$[$size$]=$ value;

size$++$;

$\}$

void add$($TYPE value, int index$)\{$

if$($this$->$size $==$ this$->$capacity$)$

this$->$resize$()$;

for$($int i $=$ size; i $>$ index; i$--)\{$

values$[$i$]=$ values$[$i $-1]$;

$\}$

values$[$index$]=$ value;

this$->$size$++$;

$\}$

void remove$($int index$)\{$

for$($int i $=$ index; i $<$ this$->$size $-1$; i$++)\{$

values$[$i$]=$ values$[$i $+1]$;

$\}$

this$->$size$--$;

$\}$

int search$($TYPE value$)\{$

for$($int i $=0$; i $<$ this$->$size; i$++)\{$

if$($this$->$values$[$i$]==$ value$)$

return i;

$\}$

return $-1$;

$\}$

friend ostream& operator$<<($ostream& os$,$ Array& array$)\{$

for$($int i $=0$; i $<$ array.size; i$++)\{$

os $<<$ array.get$($i$)<<","$;

$\}$

return os;

$\}$

void swap$($int a$,$ int b$)\{$

TYPE temp $=$ values$[$a$]$;

values$[$a$]=$ values$[$b$]$;

values$[$b$]=$ temp;

$\}$

void bubbleSort$()\{$

int unsorted $=$ this$->$size $-1$;

bool sorted $=$ false;

while$(!$sorted$)\{$

sorted $=$ true;

for$($int i $=0$; i $<$ unsorted; i$++)\{$

if$($values$[$i $+1]<$ values$[$i$])\{$

swap$($i$,$ i $+1)$;

sorted $=$ false;

$\}$

$\}$

unsorted$--$;

$\}$

$\}$

void selectionSort$()\{$

int lowestIndex $=0$;

for$($int i $=0$; i $<$ this$->$size $-1$; i$++)\{$

lowestIndex $=$ i;

for$($int j $=$ i $+1$; j $<$ this$->$size; j$++)\{$

if$($values$[$j$]<$ values$[$lowestIndex$])$

lowestIndex $=$ j;

$\}$

if$($lowestIndex $!=$ i$)\{$

swap$($i$,$ lowestIndex$)$;

$\}$

$\}$

$\}$

void insertionSort$()\{$

TYPE heldValue;

int gap $=1$;

for$($int i $=1$; i $<$ size; i$++)\{$

heldValue $=$ values$[$i$]$;

gap $=$ i $-1$;

while$($gap $>=0$ && values$[$gap$]>$ heldValue$)\{$

values$[$gap $+1]=$ values$[$gap$]$;

gap$--$;

$\}$

values$[$gap $+1]=$ heldValue;

$\}$

$\}$

void shuffle$()\{$

for$($int i $=0$; i $<$ this$->$size; i$++)\{$

swap$($i$,$ rand$()\%$ this$->$size$)$;

$\}$

$\}$

void bogoSort$()\{$

while$(!$this$->$isSorted$())\{$

this$->$shuffle$()$;

$\}$

$\}$

$\}$;

#endif