Description

The purpose of this challenge is to implement a double-ended queue (deque) using a doubly-linked list as a backing data structure.

Requirements

1. Write the following struct

   struct DataNode
   {
     string value;
     DataNode * next;
     DataNode * prev;
   };

2. Create a class called Deque. In this class, create protected variables DataNode * head and tail . This will keep track of the location of the head and tail nodes respectively. Initialize both of these variables to NULL.
3. Add the following protected function. This function will be used to dynamically create new nodes for the linked list.

   DataNode * create()
   {
     DataNode * newnode;
     try
     {
       newnode = new DataNode;
       newnode->prev = NULL;
       newnode->next = NULL;
     }
     catch (bad_alloc)
     {
       newnode = NULL;
     }
     return newnode;
   }
   
   // USAGE: To create a new node, use as follows
   // DataNode * newnode = create();

4. Create a protected function called void deallocate(). This function will traverse the entire list and delete each node. You may start traversal either at head or tail. Remember to make a copy of whichever pointer you will use to start the traversal. Also, realize that if you delete the current node as you’re traversing, you may lose the reference to the next node.
5. Create a destructor which will call deallocate() and set head and tail to NULL.
6. Create a protected function, void add_to_head(string value). This function will:
   1. create a new node (DataNode) using the create() function you wrote earlier. The new node will be assigned value from the function’s parameter.
   2. add the new node to the front of the linked list (where head points). Remember to deal with two possible scenarios: 1) The list is still empty and this is the first node to be added and 2) The list is not empty
   3. Remember to set the prev pointer appropriately as well
   4. point head to the newly-added node
7. Create a protected function, string remove_from_tail(). This function will
   1. Identify the node at the end of the list (if not empty). Use the tail pointer to go directly to the end.
   2. Copy the value of the node’s value property into a temporary variable
   3. Point the next-to-last node to NULL. You will also have to account for if there is only one node in the actual queue — removing the only node in the queue would mean head and tail would need to point to NULL.
   4. delete the last node
   5. Return the value stored in the temporary variable. Return a blank string if the linked list is empty
8. Create a protected function void add_to_tail(string value). This function behaves similar to the function on Step 6, except all of the changes happen at the tail.
9. Create a protected function string remove_from_head(). This function behaves similar to the function on Step 7, except all of the changes happen at the head.
10. Create a class Queue that publicly inherits from Deque.
11. In Queue, create public functions enqueue and dequeue which will use the  appropriate add_xyz or remove_xyz functions defined in Steps 6-9
12. OPTIONAL: Create a class Stack that inherits from Deque. In Stack, create public functions push and pop which will use the  appropriate add_xyz or remove_xyz functions defined in Steps 6-9
13. Create a friend function void show(Deque & Q). This will display all the values of all the nodes one per line. Traverse the entire linked list to show the node values. If you show the list from head to NULL, it will display in reverse order of the queue — this is fine to display it this way. OR, you can display it in queue order starting from tail. 
14. For main(), write driver code that will instantiate objects for Queue (or optionally, Stack). Also, write code to test the enqueue/dequeue/push/pop functions.

Sample main()

int main()
{
  Queue q;

  q.enqueue("Heaven");
  q.enqueue("Hell");
  q.enqueue("Limbo");
  show(q);
  // additional driver code

  // Optional
  Stack s;

  s.push("Humpty");
  s.push("Dumpty");
  show(S);
  // additional driver code 
  return 0;
}