Assignment 3 (Programming): Comparison of the Singly and Doubly Linked List-based Implementations of the Stack ADT Due by: March 2nd, 11.59 PM You are given the singly linked list and doubly linked list-based implementations of the Stack ADT. The singly linked list-based implementation treats the head end of the list as the top of the stack and accordingly pushes and pops near the head node of the list. The doubly linked list-based implementation (named as: DoublyLinkedList_Stack_TailPushPop.cpp) considers the tail end of the list as the top of the stack and the push and pop operations are performed with regards to the node previous to the tail node. Your task in this project is to implement the Stack ADT using a doubly linked list-implementation wherein the head end of the list is considered as the top of the stack and the push and pop operations are performed with regards to the node next to the head node. In this pursuit, you are required to modify the code for the following member functions of the class Stack in the DoublyLinkedList_Stack_TailPushPop.cpp file to reflect the above requirement and name the.cpp file as DoublyLinkedlist_Stack_HeadPushPop.cpp. push, pop. peck, PrintTop ToBottom, PrintBottomToTop In both the .cpp files corresponding to the singly linked list and (tail end-based) doubly linked list implementations, the main function has the code to create and maintain a stack of a certain number of randomly generated integers (StackSize), each within the range of [...maxValue). The timers are setup to measure the time to push all the StackSize amount of the integers to the Stack and pop all of them out. The above trials are run numTrials number of times and the average push time and average pop time in micro seconds are then determined. You could retain the main function as it is (provided in the DoublyLinkedList_Stack_TailPushPop.cpp file) in the DoublyLinkedList_Stack_HeadPushPop.cpp file that you will be developing. There is no need to change anything in the singly linked list-based implementation and you could use it just for reference and performance comparison purposes. After you implement the DoublyLinkedList_Stack_HeadPushPop.cpp file (as directed above), you could run this file as well as the DoublyLinkedlist_Stack_TailPushPop.cpp file and the singly linked list-based SinglyLinkedList_Stack.cpp file for the following values of the input variables. Tabulate all your results for the pushing time and popping time that will be printed in micro seconds) StackSize: 100000 and 1000000 max Value: 50000 numTrials = 10 Interpret your results; explain the similarity or differences (as you observe in the results) and come to a conclusion Submission: (1) The DoublyLinkedList_Stack_HeadPushPop.cpp file that implements the Stack ADT using a doubly linked list wherein the head end of the list is considered as the top of the stack. (2) A PDF or Word file containing the table of results (as described above) and the interpretation of the results. #include #include #include #include #include #include using namespace std; // implementing the Stack ADT using a singly linked list 1/ head node region is the top of the stack class Node private: int data; Node* nextNode Ptr; public: Node() { void setData(int d){ data = d; } int getData() { return data; } void setNextNodePtr (Node* nodePtr){ nextNode Ptr = nodePtr; } Node* getNextNodePtr() { return nextNodePtr; } }; class Stack private: Node *headPtr; public: Stack() { headPtr = new Node(); headPtr->setNextNodePtr(0); } public: Stack() { headPtr = new Node(); headPtr->setNextNodePtr(0); } Node* getHeadPtr() { return headPtr; } bool isEmpty() { if (headPtr- >getNextNodePtr() == 0) return true; return false; } void push(int data) { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr- >setNextNodePtr (currentNodePtr); headPtr- >setNextNodePtr(newNodePtr); } int peek () { Node* currentNodePtr = headPtr->getNextNodePtr(); if (currentNodePtr != 0) return currentNodePtr->getData(); else return -1000000; } int pop() { int pop() { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* nextNodePtr = 0; if (currentNodePtr != 0) nextNodePtr - currentNodePtr->getNextNodePtr(); headPtr- >setNextNodePtr (nextNodePtr); if (currentNodePtr != 0) return currentNodePtr->getData(); else return -1000000; } void PrintToptoBottom() { Node* currentNodePtr headPtr->getNextNodePtr(); while (currentNodePtr != 0) { currentNodePtr->getData() getNext NodePtr(); } cout > StackSize; int maxValue; cout > maxValue; int numTrials; cout > numTrials; srand(time(NULL)); i 1/cout pushingTime_micro = t2 - tl; totalPushingTime += pushingTime_micro.count(); tl = high_resolution_clock:: now(); while (!integer Stack.isEmpty()) integer Stack. nan: using namespace std::chrono; double totalPushingtime = 0; double total PoppingTime = 0; for (int trials = 1; trials high_resolution_clock::time_point t2 high_resolution_clock:: now(); duration double, std::micro> pushingTime_micro - t2 - t1; totalPushingTime += pushingtime_micro.count(); t1 = high_resolution_clock::now(); while (!integer Stack.isEmpty() integerStack.pop(); t2 = high_resolution_clock:: now(); duration double, std::micro> poppingTime_micro = t2 - tl; totalPoppingTime += poppingTime_micro.count(); }// trials cout #include #include #include #include #include using namespace std; // implementing Stack using a doubly linked list // with the tail end as the top of the stack class Node private: int data; Node* nextNodePtr; Node* prevNodePtr; public: Node (0) void setData(int d) { data - d; > int getData() return data; > void setNextNodePtr (Node* nodeptr){ next Node Ptr - nodePtr; ) Node* getNextNodePtr() { return nextNodePtr; } void setPrevNodePtr (Node nodeer) { prevNodePtr- node Ptr; > Node* get PrevNodePtr() { return prevNodePtr; } class Stack private: Node* headPtr; Node* tailPtr; public: Stack() { headPtr - new Node(); tailPtr - new Node(); headPtr->set Next Node Ptr(0); tailPtr->set Prev Node Ptr(0); public: Stack() { headPtr = new Node(); tailPtr = new Node(); headPtr->set NextNodePtr(0); tailPtr->set PrevNodePte(0); > Node* get Headptr() { return headPtr; } Node* getTailPtr() { return tailPtr; > bool isEmpty if (headPtr- >getNextNodePtr() -- 0) return true; return false; } void push(int data) { Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr- >set NextNodePtr(0); Node* lastNodePtr - tailPtr->get PrevNodePtr(); if (lastNodePtr == 0){ headPtr- >set NextNodePtr(newNodeptr); newNodePtr- >set PrevNodePtr(0); else{ lastNodePtr- >setNextNodePtr(newNodeptr); newNodePtr- >set PrevNodePtr(lastNodeptr); > tailPtr- >set Prev NodePtr (newNodeptr); } int pop Node. lastNodePtr- UN Node. lastNodePtr- tailPtr->get PrevNodePtr(): Node* prevNodePtr = 0; int poppedData --100000; //empty stack if (lastNodePtr != 0){ lastNodePtr->get PrevNodePtr(); prevNodePtr- poppedData- lastNodePtr->getData(); return poppedData; if (prevNodePtr - 0){ prevNodeftr- >setNextNodePtr(0); tailPtr- >set PrevNodePtr (prevNodeptr); else headPtr- >setNextNodePtr(0); tailPtr- >set PrevNodePtr(0); else return poppedData; int peek() { Node* lastNodePtr- tailPtr->getPrevNodeptr(); if (lastNodePtr != 0) >getData(); else return -100000; 11 empty stack return lastNode Ptr- void PrintBottomtoTop() { Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr :-) cout getData() " currentNodePtr currentNodePtr->getNextNodePtr(); } cout void PrintToptoBottom(){ Node* currentNodePtr = tailPtr->get PrevNodePtr(); while (currentNodePtr != 0) { cout getData() get PrevNodePtr(); cout > StackSize; int maxValue; cout > maxValue; int numTrials; cout > numTrials; srand(time(NULL)); 1/cout > numTrials; srand(time(NULL)); 1/cout pushingtime_micro = t2 - tl; totalPushingtime + pushingTime_micro.count(); t1 = high_resolution_clock:: now(); while (!integerStack.isEmpty) integerStack.pop(); t2 - high_resolution_clock:: now(); duration poppingTime_micro - t2 - t1; total PoppingTime + poppingTime_micro.count(); // trials cout #include #include #include #include #include using namespace std; // implementing the Stack ADT using a singly linked list 1/ head node region is the top of the stack class Node private: int data; Node* nextNode Ptr; public: Node() { void setData(int d){ data = d; } int getData() { return data; } void setNextNodePtr (Node* nodePtr){ nextNode Ptr = nodePtr; } Node* getNextNodePtr() { return nextNodePtr; } }; class Stack private: Node *headPtr; public: Stack() { headPtr = new Node(); headPtr->setNextNodePtr(0); } public: Stack() { headPtr = new Node(); headPtr->setNextNodePtr(0); } Node* getHeadPtr() { return headPtr; } bool isEmpty() { if (headPtr- >getNextNodePtr() == 0) return true; return false; } void push(int data) { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr- >setNextNodePtr (currentNodePtr); headPtr- >setNextNodePtr(newNodePtr); } int peek () { Node* currentNodePtr = headPtr->getNextNodePtr(); if (currentNodePtr != 0) return currentNodePtr->getData(); else return -1000000; } int pop() { int pop() { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* nextNodePtr = 0; if (currentNodePtr != 0) nextNodePtr - currentNodePtr->getNextNodePtr(); headPtr- >setNextNodePtr (nextNodePtr); if (currentNodePtr != 0) return currentNodePtr->getData(); else return -1000000; } void PrintToptoBottom() { Node* currentNodePtr headPtr->getNextNodePtr(); while (currentNodePtr != 0) { currentNodePtr->getData() getNext NodePtr(); } cout > StackSize; int maxValue; cout > maxValue; int numTrials; cout > numTrials; srand(time(NULL)); i 1/cout pushingTime_micro = t2 - tl; totalPushingTime += pushingTime_micro.count(); tl = high_resolution_clock:: now(); while (!integer Stack.isEmpty()) integer Stack. nan: using namespace std::chrono; double totalPushingtime = 0; double total PoppingTime = 0; for (int trials = 1; trials high_resolution_clock::time_point t2 high_resolution_clock:: now(); duration double, std::micro> pushingTime_micro - t2 - t1; totalPushingTime += pushingtime_micro.count(); t1 = high_resolution_clock::now(); while (!integer Stack.isEmpty() integerStack.pop(); t2 = high_resolution_clock:: now(); duration double, std::micro> poppingTime_micro = t2 - tl; totalPoppingTime += poppingTime_micro.count(); }// trials cout #include #include #include #include #include using namespace std; // implementing Stack using a doubly linked list // with the tail end as the top of the stack class Node private: int data; Node* nextNodePtr; Node* prevNodePtr; public: Node (0) void setData(int d) { data - d; > int getData() return data; > void setNextNodePtr (Node* nodeptr){ next Node Ptr - nodePtr; ) Node* getNextNodePtr() { return nextNodePtr; } void setPrevNodePtr (Node nodeer) { prevNodePtr- node Ptr; > Node* get PrevNodePtr() { return prevNodePtr; } class Stack private: Node* headPtr; Node* tailPtr; public: Stack() { headPtr - new Node(); tailPtr - new Node(); headPtr->set Next Node Ptr(0); tailPtr->set Prev Node Ptr(0); public: Stack() { headPtr = new Node(); tailPtr = new Node(); headPtr->set NextNodePtr(0); tailPtr->set PrevNodePte(0); > Node* get Headptr() { return headPtr; } Node* getTailPtr() { return tailPtr; > bool isEmpty if (headPtr- >getNextNodePtr() -- 0) return true; return false; } void push(int data) { Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr- >set NextNodePtr(0); Node* lastNodePtr - tailPtr->get PrevNodePtr(); if (lastNodePtr == 0){ headPtr- >set NextNodePtr(newNodeptr); newNodePtr- >set PrevNodePtr(0); else{ lastNodePtr- >setNextNodePtr(newNodeptr); newNodePtr- >set PrevNodePtr(lastNodeptr); > tailPtr- >set Prev NodePtr (newNodeptr); } int pop Node. lastNodePtr- UN Node. lastNodePtr- tailPtr->get PrevNodePtr(): Node* prevNodePtr = 0; int poppedData --100000; //empty stack if (lastNodePtr != 0){ lastNodePtr->get PrevNodePtr(); prevNodePtr- poppedData- lastNodePtr->getData(); return poppedData; if (prevNodePtr - 0){ prevNodeftr- >setNextNodePtr(0); tailPtr- >set PrevNodePtr (prevNodeptr); else headPtr- >setNextNodePtr(0); tailPtr- >set PrevNodePtr(0); else return poppedData; int peek() { Node* lastNodePtr- tailPtr->getPrevNodeptr(); if (lastNodePtr != 0) >getData(); else return -100000; 11 empty stack return lastNode Ptr- void PrintBottomtoTop() { Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr :-) cout getData() " currentNodePtr currentNodePtr->getNextNodePtr(); } cout void PrintToptoBottom(){ Node* currentNodePtr = tailPtr->get PrevNodePtr(); while (currentNodePtr != 0) { cout getData() get PrevNodePtr(); cout > StackSize; int maxValue; cout > maxValue; int numTrials; cout > numTrials; srand(time(NULL)); 1/cout > numTrials; srand(time(NULL)); 1/cout pushingtime_micro = t2 - tl; totalPushingtime + pushingTime_micro.count(); t1 = high_resolution_clock:: now(); while (!integerStack.isEmpty) integerStack.pop(); t2 - high_resolution_clock:: now(); duration poppingTime_micro - t2 - t1; total PoppingTime + poppingTime_micro.count(); // trials cout