Please use C++

Please answer question 2 (Thank you!)

You are expected to create a templated Listdatastructure (up to you on implementation). Subsequentlyyou are to create three child classes of this generic Listclass: Set(ensures unique data), Queue (first in first out), and Stack (last in first out) data structures.

Grading Criteria

1. Listclass

o[3 Points] Implementation of basic list interface (e.g. add, remove, find)

o[2 Points] Destructor correctly deletes everything in the list without throwing exception

2. Set class (must inherit from List)

o[3Points] Correctoverride of add/insert (ensures uniqueness)

3. Queueclass (must inherit from List)

o[1 Point] Private inheritance from List

o[2Points] Correct implementation of basic queue interface (e.g. enqueueanddequeue)

4. Stackclass (must inherit from List)

o[1 Point] Private inheritance from List

o[2 Points] Correct implementation of basic stack interface (e.g. push and pop)

5. Demonstration (driver):

oFunctionaltests (positive and negative):

[1 Point] Attempt to add duplicatedata to list

[1 Point] Attempt to add duplicatedata to set (what should happen?)

[1 Point] Demonstrate Enqueue for Queue

[1 Point] Demonstrate Dequeue for Queue

[1 Point] Demonstrate Pushfor Stack

[1 point] Demonstrate Pop for Stack

List class:

#include

#include

#include

using namespace std;

template

class List {

private:

struct Node{

Node *next;

dataType data;

};

public:

List();

List(const List& aList);

List(Node *head);

~List();

bool isEmpty();

int getLength();

void insert(int index, dataType data);

void remove(int index);

dataType retrieve(int index);

dataType extract(int index);

void printList();

void removeDuplicates();

void randomIntFill(int item_num, int max);

void removeNode(Node* node);

Node* find(int index);

Node* sumDigitsWithCarry(Node* head1, Node* head2);

private:

int size;

Node *head;

};

template

List::~List(){

while(!isEmpty())

remove(0);

}

template

List::List(){

size = 0;

head = NULL;

}

template

List::List(Node* aHead){

size = 0;

head = aHead;

for(Node* cur = head; cur != NULL; cur = cur->next){

size++;

}

}

template

List::List(const List& aList){

size = aList.size;

head = new Node;

head -> data = aList.head->data;

Node *cur = head;

for(Node *cp_node = aList.head->next; cp_node != NULL ; cp_node = cp_node->next){

cur -> next = new Node;

cur = cur->next;

cur -> data = cp_node -> data;

}

cur -> next = NULL;

}

template

void List::insert(int index, dataType data){

if (index < 0){

cout << "Negative index!!" << endl;

return;

}

if (index > size){

cout << "Extension is not supported!!" << endl;

return;

}

if(index == 0){

Node *new_head = new Node;

new_head -> next = head;

new_head -> data = data;

head = new_head;

}

else{

Node *prev = find(index-1);

Node *node = new Node;

node -> data = data;

node -> next = prev -> next;

prev -> next = node;

}

size ++;

}

template

dataType List :: extract(int index){

if (index < 0 || index >= size){

cout << "Wrong index value !!!" << endl;

return 0;

}

Node* node = find(index);

dataType ret_data = node -> data;

remove(index);

node = NULL;

return ret_data;

}

template

void List::remove(int index){

if(size == 0){

cout << "No item to remove in list!!" << endl;

return;

}

else if (index >= size || index < 0){

cout << "No item with given index!!" << endl;

return;

}

Node *cur;

if(index == 0){

cur = head;

head = head->next;

}

else{

Node *prev = find(index-1);

cur = prev->next;

prev->next = cur->next;

}

cur->next = NULL;

delete cur;

cur = NULL;

size --;

}

template

void List :: removeDuplicates(){

if(size < 2)

return;

Node* ind = head;

Node* temp = NULL;

for(Node* cur = head->next; cur != NULL; cur = cur->next){

dataType value = cur -> data;

temp = head;

for(temp = head; temp != ind -> next; temp = temp->next ){

if(value == temp -> data)

break;

}

if (temp == ind->next){

ind = ind->next;

ind->data = value;

}

}

while(ind->next != NULL){

size --;

Node* temp = ind->next;

ind -> next = temp -> next;

temp -> next = NULL;

delete temp;

temp = NULL;

}

}

template

void List::removeNode(Node *node){

if(size == 0){

cout << "List is empty!!" << endl;

return;

}

if(node -> next == NULL){

remove(getLength()-1);

}else{

Node * next_node = node -> next;

node -> data = next_node -> data;

node -> next = next_node -> next;

next_node -> next = NULL;

delete next_node;

next_node = NULL;

}

size--;

}

template

typename List::Node* List :: sumDigitsWithCarry(Node* num1,Node* num2){

Node* newHead = new Node;

Node* newCur = newHead;

int carry = 0;

for(Node * cur1 = num1, *cur2 = num2; cur1 != NULL && cur2 != NULL; cur1 = cur1 -> next, cur2 = cur2 -> next){

int val1 = cur1 -> data ;

int val2 = cur2 -> data;

int sum = val1 + val2;

int newDig = (sum % 10) + carry;

newCur -> data = newDig;

newCur -> next = new Node;

newCur = newCur -> next;

carry = (sum / 10) ? 1 : 0;

}

if(carry == 1){

newCur -> data = 1;

newCur -> next = NULL;

}

newCur = NULL;

return newHead;

}

template

void List :: randomIntFill(int item_num, int max){

for(int i = 0; i < item_num; i ++){

int next_val = rand() % max;

insert(0,next_val);

}

}

template

dataType List::retrieve(int index){

if(index > size || index < 0){

cout << "Wrong index value!!!" << endl;

return;

}

Node *ptr = find(index);

return ptr->data;

}

template

typename List::Node* List::find(int index){

Node *cur = head;

for(int i = 0; i < index; i++){

cur = cur->next;

}

return cur;

}

template

void List::printList(){

for(Node *cur = head; cur != NULL; cur = cur->next){

cout << cur->data << ' ';

}

cout << endl;

}

template

bool List::isEmpty(){

return (size == 0) ? true : false;

}

template

int List::getLength(){

return size;

}