26.5 Project 3: List & Queue ADT

Overview

For this project, you are to implement two abstract data types(ADTs). You will write a doubly linked list (Dll) and a queueclass. The queue will use the dll internally. The class interfacesare downloadable below. You must follow the interfaceexactly. While you can define other public and privatemethods and fields, the class names and methods given must appearas provided, or you will not pass the unit tests. Include theimplementation of the classes in their respective header (.h)files. Please note: Dll is not a node class, as in, a Dll does notpoint to another Dll; it contains nodes internally.

Dll Comments

When inserting into a dll, rank 0inserts at the front of the list and rank size() inserts at theback of the list. If you have the list 0 -> 10 ->30, then after insert(2, 20), the list should be 0 ->10 -> 20 -> 30.

When removing from a dll, rank 0removes from the front of the list and rank size() -1 removes from the back of the list. If you have the list0 -> 10 -> 20 -> 30, then after remove(2), thelist should be 0 -> 10 -> 30.

When building a dll from an array, the array [ 0 1 2 ]should create the list 0 -> 1 -> 2.

Displaying

When displaying a Dll, it should appear with the head onthe left and the tail on the right. Forexample, the list created after insert(0, 3), insert(0, 2),insert(0, 1) should represent the list 1 -> 2 -> 3and should display as follows:

[ 1 2 3 ]

When displaying a queue, it should appear withthe front on the left and the back on theright. For example, the queue created after enqueue(1),enqueue(2), enqueue(3) should display as follows:

[ 1 2 3 ]

When displaying an empty ADT, it should be a single spacesurrounded by brackets:

[ ]

Efficiency

All operations should have an efficientruntime. Besides display(), all queue operations should run inO(1). Because the queue uses a dll internally,this means insert(), remove(), and size() must beO(1) for the appropriate cases (insert back,remove front), which also means size should be stored and notcalculated by looping through the list.

Exceptions

Two exception classes can be found in exceptions.h:InvalidOperationException and IndexOutOfRangeException. Your ADTswill throw exceptions according to the instructions below:

• List: throw IndexOutOfRangeException for the followingoperations:
  • at(): when accessing an index outside the bounds (0 to size-1inclusive) of the linked list with the message \"at(): Index wasoutside the bounds of the linked list.\"
  • insert(): when index is not in the range from 0 to size(inclusive) with the message \"insert(): Index was outside thebounds of the linked list.\"
  • remove(): when removing an index outside the bounds (0 tosize-1 inclusive) of the linked list with the message\"remove(): Index was outside the bounds of the linkedlist.\"
• Queue: throw InvalidOperationException with the message\"Queue empty.\" when dequeuing orpeeking an empty queue.

p3.cpp

p3.cpp is a command-line interface that can be used to test yourdata structures. Review the code before running it and testing yourdata structures. p3.cpp assumes your dll.h and queue.h arecompleted. You must comment out the portions of the code that youhave not implemented (includes and the loops in main pertaining tothe data structure) or create \"empty\" method definitions to make itcompilable.

You can compile your program with g++ p3.cpp.

Notes

• Your data structures will be unit tested separately, meaningDll can be tested accurately without a fully implementedQueue.
• Be sure to print to the ostream os variable and not to cout oryou will fail the test cases.
• Throw the exceptions if the index is negative.
• Be sure to initialize pointers to NULL or nullptr as *nixenvironments do not initialize variables to 0.