Your task for this project is to design a program to help a videorental store operatorrecord clients' transactions.  TheMenu would look like this:

Select one of the following

1: To check if a particular video is in store

2: To check out a video

3: To check in a video

4: To print the titles of all videos

5: To print a list of all videos

6: To exit

Your project has to provide the underlying software to support the functionsgiven in the menu above.The project (process) is outlined below:

1. Design a primitive database indicating

• what you want to store (videos, customers, etc),
• what processes you want to allow on it (update, add, and delete, etc) and
• what transactions you want it to perform (rent and return).

2. Design classes (class video, class customer, etc) based on your analysis above, using LINKED LISTSfor the database elements read into the main memory.

3. Implement your design, together with a main program,that performs all the functions shown in the menu above.

4. Generate inputs and test the program you have written.

5. Now add a QUEUE to process customers.  Pretend that there are severalcustomers waiting to be processed, by randomly generating a number n, picking some n customers from the database to put into this queue and then processing the queue members with a randomly generated task that they "request" (instead of just looping through the main menu till flagged for a finish, as was done above).

6. Now design a BINARY SEARCH TREE data structure to bring the video database into the main memory and document any improvement in performance over the flat linked list used earlier.

7. Finally, make the BST be a balanced tree (AVL) tree, and document performance improvements.