Obiectives The objective of this programming assignment are Practice using templates and inheritance Implement a data structure (Linked Lists) Use the data structure to mimic and enhance STL data structures and implement Abstract Data Types (Stacks and Queues) Practice error handling. Write code to a specification that someone else will use Introduction C++ includes a Standard Template Library (STL) that contains pre-built code for many data structures. Examples of these data structures would be linked lists, stacks, queues, double ended queues, pairs, vectors, etc. Using STL containers allows for quick implementation of data structures as well as increasing portability of code. Each data structure has its own interface that allows access to the methods and storage, standardizing their use STL containers do have shortcomings and one is error handling. STL containers expect you, as the programmer, to protect your code and not induce errors. This includes doing things like asking for the next item, using Top) on an empty stack. (Nothing there!!) This programming project will replicate two of the STL containers (stacks and queues) and enhance them to protect against common errors in use This project is also designed for you to program to a specification. This means you will writeia data structure based on the included specification but you will not implement this into a larger part of the project. At times other people will use the code you write and you will not have the ability to fix it along the way. These means you need to write solid code to the specification and ensure that code works via testing Linked List Structure There are different ways to build a linked list: singly, doubly, with or without dummy nodes internal and external to the data etc. For this project a doubly linked list without dummy nodes is required. This means the linked list will be traversable either forward or backwards and that the head and tail nodes will contain data. There will be no empty head or tail nodes You will construct this type of Linked List. Head Node Tail Node NULL Data Data Data Data NULL Methods Along with appropriate constructors, destructor AND COPY CONSTRUCTORS (hint, hint) this class must present the following methods virtual int Size0 const o; \Returns the size of a list virtual bool Empty() const = 0; \\Returns whether a list has data or not virtual bool Push(T obi)-o virtual bool Pop() o; virtual bool ClearOo Clears a list Pushes data into the list Pops data from a list 2 Stack221 Class (Stack221.h and Stack221.cpp) This class will be a child class for List221 and use public access control. It must be a C++ template The virtual methods inherited will need to be defined in this class' implementation file. The following will also need to be defined and implemented: T TopO: //Returns the top item on the stack As a hint, you will need a copy constructor for the Stack. But there's an... issue. The stack needs to be copied, but that's impossible using another stack, so dump the stack into a queue temporarily. In essence use the queue to manage the stack copy and a stack to manage the queue copy. Queue221 Class (Queue221.h and Queue221.cpp) This class will be a child class for List221 and use public access control. It must be a C++ template The virtual methods inherited will need to be defined in this class' implementation file. The following will also need to be defined and implemented: T Eront0;//Returns the item at the front of the queue T Back0 //Returns the item at the back of the queue Exceptions221 Class (Exceptions221.h) This class is provided and must be used. To use the provided class you simply create the object with a string that describes the exception that is being raised. Example: throw Exceptions221("Stack- Could not determine if the stack is full") catch (Exceptions221 &E) cout