#include

#include

#include

#include

#include

#include

using namespace std;

// implementing the dynamic List ADT using Linked List

class Node{

private:

int data;

Node* nextNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

};

class Stack{

private:

Node *headPtr;

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){

// This is the direct implementation of the push function without

// calling the insertAtIndex(0, data) function

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(currentNodePtr);

headPtr->setNextNodePtr(newNodePtr);

}

int peek(){

// Implement the peek function directly without calling the readElement function

}

int pop(){

// Implement the pop function directly without calling the deleteElement function

}

};

int main(){

int StackSize;

cout

cin >> StackSize;

int maxValue;

cout

cin >> maxValue;

int numTrials;

cout

cin >> numTrials;

srand(time(NULL));

//cout

using namespace std::chrono;

double totalPushingTime = 0;

double totalPoppingTime = 0;

for (int trials = 1; trials

Stack integerStack; // Create an empty stack

high_resolution_clock::time_point t1 = high_resolution_clock::now();

for (int i = 0; i

int value = 1 + rand() % maxValue;

//cout

integerStack.push(value);

}

high_resolution_clock::time_point t2 = high_resolution_clock::now();

duration pushingTime_micro = t2 - t1;

totalPushingTime += pushingTime_micro.count();

//cout

//cout

//integerStack.PrintToptoBottom();

// to read an element at a particular index (before delete)

//cout

t1 = high_resolution_clock::now();

while (!integerStack.isEmpty())

integerStack.pop();

t2 = high_resolution_clock::now();

duration poppingTime_micro = t2 - t1;

totalPoppingTime += poppingTime_micro.count();

}// trials

cout

cout

//cout

return 0;

}

Q4 25 pts) Implement Stack ADT as a Singly Linked List without using the insertAtlndex, deleteElement, readlndex functions of the Singly Listed List. That is, the push, pop and peek operations should not call insertAtlndex(0, data), deleteElement(0) and readlndex(0) functions. The push, pop and peek operations should be directly implemented to insert an element in the beginning of the linked list, to delete an element from the beginning of the linked list and to read the element value from the beginning of the linked list. To help you out, the implementation of the push function is given in the startup code provided. Your task is to implement the peek and pop functions like this without calling any other function. You can notice that the insertAtIndex, deleteElement and readIndex functions have been removed from the them. After implementing the pop and peek functions, you will be comparing the actual run-time of the push and pop operations of a Stack implemented as a Singly Linked List (with insertions and deletions in the beginning of the Linked List) with that of a Stack implemented as a Doubly Linked List (with insertions and deletions at the tail/end of the Linked List). The main function provided to you has the timers setup r this purpose. Your task is to just run the main functions and measure the average time taken (in microseconds) for the push and pop operations with the Stack as a Singly Linked List and with the Stack as a Doubly Linked List for the following values of the parameters: (i) # elements to be pushed 1000 1000, 100000, 1000000; (ii) maximu m value for any element = 50000 and (iii) # trials = 50 You need to include the following as part of your answer to this question: (i) the code for the Singly Linked List-based implementation of the Stack class (ii) a table presenting the actual run-times for the parameters mentioned above (iii) snapshots of the actual run-times for the above cases (iv) interpretation of the difference/similarity in the actual run-times for the push and pop operations between the Singly Linked List and Doubly Linked List implementation of the Stack ADT