For this question, you will implement the Stack ADT as a Singly Linked List without directly using the insertAtIndex, deleteElement, readIndex functions of the Singly Listed List. That is, the push, pop and peek operations should not call insertAtIndex(0, data), deleteElement(0) and readIndex(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 (and return its value) from the beginning of the linked list and to read the element value from the beginning of the linked list. Your task is to implement the push, pop and peek functions (as explained above) without calling any other function. You can notice that the insertAtIndex, deleteElement and readIndex functions have been removed from the Stack class code assigned for this question and you should not include the code for these three functions (insertAtIndex, deleteElement and readIndex functions) to use them.

After implementing the three functions push, pop and peek, you will be comparing the actual run-times of the push and pop operations; the main function provided to you has the timers setup for this purpose. Your task is to just run the main function and measure the average time taken (in microseconds) for the push and pop operations with the Stack as a Singly Linked List for the following values of the parameters: (i) # elements to be pushed = 10000,

100000, 1000000; (ii) maximum value for any element = 50000 and (iii) # trials = 50.

Screenshots of the execution of the code for each of the three values for the number of elements to be pushed.

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

// Implement the push function directly without calling any other function } int peek(){ // Implement the peek function directly without calling any other function

} int pop(){ // Implement the pop function directly without calling any other function }

};

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 stack high_resolution_clock::time_point t1 = high_resolution_clock::now(); for (int i = 0; i < StackSize; i++){ int value = 1 + rand() % maxValue; 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(); }// trials cout << "Avg. Pushing time (microseconds): " << (totalPushingTime/numTrials) << endl; cout << "Avg. Popping time (microseconds): " << (totalPoppingTime/numTrials) << endl;

system("pause"); //cout << endl; return 0; }