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, peek, PrintTopToBottom, 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 [1...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.

This is the reference code

#include #include #include #include #include #include using namespace std;// implementing Stack using a doubly linked list// with the tail end as the top of the stackclass Node{private:int data;Node* nextNodePtr;Node* prevNodePtr;public:Node(){}void setData(int d){data = d;}int getData(){return data;}void setNextNodePtr(Node* nodePtr){nextNodePtr = nodePtr;}Node* getNextNodePtr(){return nextNodePtr;}void setPrevNodePtr(Node* nodePtr){prevNodePtr = nodePtr;}Node* getPrevNodePtr(){return prevNodePtr;}};class Stack{private:Node* headPtr;Node* tailPtr;public:Stack(){headPtr = new Node();tailPtr = new Node();

headPtr->setNextNodePtr(0);tailPtr->setPrevNodePtr(0);}Node* getHeadPtr(){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->setNextNodePtr(0);Node* lastNodePtr = tailPtr->getPrevNodePtr();if (lastNodePtr == 0){headPtr->setNextNodePtr(newNodePtr);newNodePtr->setPrevNodePtr(0);}else{lastNodePtr->setNextNodePtr(newNodePtr);newNodePtr->setPrevNodePtr(lastNodePtr);}tailPtr->setPrevNodePtr(newNodePtr);}int pop(){Node* lastNodePtr = tailPtr->getPrevNodePtr();Node* prevNodePtr = 0;int poppedData = -100000; //empty stackif (lastNodePtr != 0){prevNodePtr = lastNodePtr->getPrevNodePtr();poppedData = lastNodePtr->getData();}else

return poppedData;if (prevNodePtr != 0){prevNodePtr->setNextNodePtr(0);tailPtr->setPrevNodePtr(prevNodePtr);}else{headPtr->setNextNodePtr(0);tailPtr->setPrevNodePtr(0);}return poppedData;}int peek(){Node* lastNodePtr = tailPtr->getPrevNodePtr();if (lastNodePtr != 0)return lastNodePtr->getData();elsereturn -100000; // empty stack}void PrintBottomToTop(){Node* currentNodePtr = headPtr->getNextNodePtr();while (currentNodePtr != 0){cout << currentNodePtr->getData() << " ";currentNodePtr = currentNodePtr->getNextNodePtr();}cout << endl;}void PrintTopToBottom(){Node* currentNodePtr = tailPtr->getPrevNodePtr();while (currentNodePtr != 0){cout << currentNodePtr->getData() << " ";currentNodePtr = currentNodePtr->getPrevNodePtr();}cout << endl;}

};int main(){int StackSize;cout << "Enter the number of elements you want to push: ";cin >> StackSize;int maxValue;cout << "Enter the max. value: ";cin >> maxValue;int numTrials;cout << "Enter the number of trials: ";cin >> numTrials;srand(time(NULL));//cout << "Integers pushed to the Stack: ";using namespace std::chrono;double totalPushingTime = 0;double totalPoppingTime = 0; for (int trials = 1; trials <= numTrials; trials++){Stack integerStack; // Create an empty stackhigh_resolution_clock::time_point t1 = high_resolution_clock::now();for (int i = 0; i < StackSize; i++){int value = 1 + rand() % maxValue;//cout << value << " ";integerStack.push(value);}high_resolution_clock::time_point t2 = high_resolution_clock::now();duration pushingTime_micro = t2 - t1;totalPushingTime += pushingTime_micro.count();t1 = high_resolution_clock::now();while (!integerStack.isEmpty())integerStack.pop();t2 = high_resolution_clock::now();duration poppingTime_micro = t2 - t1;totalPoppingTime += poppingTime_micro.count();

}// trialscout << "Avg. Pushing time (microseconds): " << (totalPushingTime/numTrials) << endl;cout << "Avg. Popping time (microseconds): " << (totalPoppingTime/numTrials) << endl;//cout << endl;system("pause");return 0;}