PLEASE CODE IN C++ AND MAKE IT COPYABLE!

In this project, you will design and implement an algorithm to determine the next greater element of an

element in an array in (n) time, where 'n' is the number of elements in the array. You could use the Stack

ADT for this purpose.

The next greater element (NGE) for an element at index i in an array A is the element that occurs at index

j (i < j) such that A[i] < A[j] and A[i] A[k] for all k [i+1..., j-1]. That is, index j (j > i) is the first index

for which A[j] > A[i]. If no such index j exists for an element at index i, then the NGE for the element

A[i] is considered to be -1.

For example: if an array is {1, 15, 26, 5, 20, 17, 36, 28}, then the next greater element (NGE) of the

elements in the array are as follows:

1 15

15 26

26 36

5 20

20 36

17 36

36 -1

28 -1

Note: Your code need not print the elements and their NGE values in the same order of the appearance of

the elements in the array. An out of order print is also acceptable as long as the correct NGE for an

element is printed out. For example, the following out of order print for the above array is also acceptable.

1 15

15 26

5 20

17 36

20 36

26 36

28 -1

36 -1

You are given the doubly linked list-based implementation code for Stack along with this project

description. Note that the main function in the code given to you already has the code snippet to generate

an array of random elements. You just extend the main function to implement the algorithm.

#include #include //srand, rand #include //clock_t, clock, CLOCKS_PER_SEC using namespace std;

// Doubly Linked List-based Implementation of Stack

class 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 stack if (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(); else return -100000; // empty stack } void IterativePrint(){ Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ cout << currentNodePtr->getData() << " "; currentNodePtr = currentNodePtr->getNextNodePtr(); } cout << endl; } void ReversePrint(){ Node* currentNodePtr = tailPtr->getPrevNodePtr(); while (currentNodePtr != 0){ cout << currentNodePtr->getData() << " "; currentNodePtr = currentNodePtr->getPrevNodePtr(); } cout << endl; } };

int main(){

int arraySize; cout << "Enter the number of elements you want to analyze: "; cin >> arraySize; Stack stack; // Create an empty stack srand(time(NULL)); int maxValue; cout << "Enter the maximum value for an element: "; cin >> maxValue;

int array[arraySize]; for (int i = 0; i < arraySize; i++){ int value = rand() % maxValue; cout << value << " "; array[i] = value; } cout << endl; // Implement a theta(n) algorithm using Stack to find the next greater element of each // element in the array and print them return 0; }