Write a C++ program that will implement and test a doubly-linked, doubly-ended queue.

A doubly-ended queue (sometimes called deque for Doubly-Ended QUEue, pronounced "deck") supports the following operations:

• front (returns the front element)
• back (returns the back element)
• push_front (puts something in front of the front element, which becomes the new front)
• push_back (puts something in back of the back element, which becomes the new back)
• pop_front (removes the front element - the "next" element becomes the new front)
• pop_back (removes the back element - the "previous" element becomes the new back)
• empty (returns a boolean if it is empty or not)

You may assume that the deque is not empty for all of the above methods, except for empty(), in which you need to actually figure out and return if it is empty or not.

You will have your implementation of a deque be a templated class, complete with a constructor and destructor. For debugging purposes, I highly recommend an overloaded assignment operator and a copy constructor _or_ a dump method that outputs everything.

Similar to the binary search tree being used to implement a set in the videos linked from from Module 1, you will want to

• have a node struct (you may want to rename it to something else, like deque_node or similar) that has the appropriate next and previous links in it, which you will update and access as you do what you do
• have your templated class (a reasonable name for it would be deque) that has pointers to the front and back nodes in the deque. Note that these might be the same (if there's only one element in the deque) or they might be both NULL (if the deque is empty).

You will want to have your main function test out all of those operations - including constructor and destructor. It should output what it is doing along the way, to help with debugging and to help show that your code works.

Your program should have at least one of the values that is put into the deque be something that is read in from input, and at least one of the values that is retrieved from the deque be something that is output to the screen.

This must be a linked implementation using pointers. Implementations that use arrays will be left ungraded. Test your program in parts. I recommend first the constructor, then pushing stuff on, and then various combinations of accessing the front, back, popping, pushing, and so on, checking empty all along the way, until at the end you pop everything off and empty is true.

Be sure to follow the requirements in the Documentation Requirements handout including a good README file.

I expect that you'll have a working makefile, with the following doing as you would expect:

• make
• make clean
• make test