Queues are a powerful data structure for solving scheduling problems and for enabling backtracking algorithms. A Double$-$Ended Queue or Deque is a data structure that allows for insertion or removal from either end of a queue. It functions as a queue in either direction, with push and pop operations supported at both ends of the queue.

Complete the Deque template class to allow for adding and removing items from both ends of the queue. In particular the class should include:

A default constructor, Deque$(),$ that creates an initially empty queue.

A destructor, ~Deque$(),$ that frees the dynamic memory.

A function to add an item to the back of the queue, PushBack$(),$ that takes as a parameter an item.

A function to add an item to the front of the queue, PushFront$(),$ that takes as a parameter an item.

A function, PopBack$(),$ that removes an item from the back of the queue and returns it$.$ If the queue is empty, throw an InvalidDequeOperation exception.

A function, PopFront$(),$ that removes an item from the front of the queue and returns it$.$ If the queue is empty, throw an InvalidDequeOperation exception.

A function, Back$(),$ that returns the item at the back of the queue without removing it$.$ If the queue is empty, throw an InvalidDequeOperation exception.

A function, Front$(),$ that returns the item at the front of the queue without removing it$.$ If the queue is empty, throw an InvalidDequeOperation exception.

A function, IsEmpty$(),$ that returns true if the stack is empty and false if it is not.

You will need to implement the InvalidDequeOperation as a exception class, and a template Node structure to hold the items in the linked$-$list implementation of the queue.