3. Both a stack and a queue can be implemented using a data structure called a "Double Ended Queue also called a deque (pronounced deck). A deque allows fast storage and retrieval at both ends of the list Write the necessary functions to complete the program deque.cpp. You can assume that the queue is not empty when writing the get -front and getback methods. For marking purposes put front 1, 2 and 3; print the deque; put back 4, 5 and 6; print the deque; get front; print the deque; get back; print the deque File: deque.cpp This program implements a double ended queue of integers as a doubly linked list / #include #include using namespace std; class node 0 friend class deque; private: int data; // this is the data in a list element node *next; // pointer to the next node in the list node *prev; // pointer to the previous node in the list public node (int x); // data x, prev "next NULL class deque private: node* front; node* back // pointer to the front of the list // pointer to the back of the list public: deque (void); void put_front (int x); // put x at the front of the list void put_back(int x); // put x at the back of the list int get front (void); int get_back (void); bool empty(void) const; void write (ostream out) const; // write data stored to out // constructor of an empty queue // get the node at the front of the list // get the node at the back of the list / check for empty deque 1: /*A deque looks like I data I l data | dataI | data I l next | >l next | next | > l next | >NULL NULL