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.

The given code is:

import java.util.*;

// Doubly Linked List-based Implementation of Stack

class Node{

private int data;

private Node nextNodePtr;

private Node prevNodePtr;

public Node(){}

public void setData(int d){

data = d;

}

public int getData(){

return data;

}

public void setNextNodePtr(Node nodePtr){

nextNodePtr = nodePtr;

}

public Node getNextNodePtr(){

return nextNodePtr;

}

public void setPrevNodePtr(Node nodePtr){

prevNodePtr = nodePtr;

}

public Node getPrevNodePtr(){

return prevNodePtr;

}

}

class Stack{

private Node headPtr;

private Node tailPtr;

public Stack(){

headPtr = new Node();

tailPtr = new Node();

headPtr.setNextNodePtr(null);

tailPtr.setPrevNodePtr(null);

}

public Node getHeadPtr(){

return headPtr;

}

public Node getTailPtr(){

return tailPtr;

}

public boolean isEmpty(){

if (headPtr.getNextNodePtr() == null)

return true;

return false;

}

public void push(int data){

Node newNodePtr = new Node();

newNodePtr.setData(data);

newNodePtr.setNextNodePtr(null);

Node lastNodePtr = tailPtr.getPrevNodePtr();

if (lastNodePtr == null){

headPtr.setNextNodePtr(newNodePtr);

newNodePtr.setPrevNodePtr(null);

}

else{

lastNodePtr.setNextNodePtr(newNodePtr);

newNodePtr.setPrevNodePtr(lastNodePtr);

}

tailPtr.setPrevNodePtr(newNodePtr);

}

public int pop(){

Node lastNodePtr = tailPtr.getPrevNodePtr();

Node prevNodePtr = null;

int poppedData = -100000; //empty stack

if (lastNodePtr != null){

prevNodePtr = lastNodePtr.getPrevNodePtr();

poppedData = lastNodePtr.getData();

}

else

return poppedData;

if (prevNodePtr != null){

prevNodePtr.setNextNodePtr(null);

tailPtr.setPrevNodePtr(prevNodePtr);

}

else{

headPtr.setNextNodePtr(null);

tailPtr.setPrevNodePtr(null);

}

return poppedData;

}

public int peek(){

Node lastNodePtr = tailPtr.getPrevNodePtr();

if (lastNodePtr != null)

return lastNodePtr.getData();

else

return -100000; // empty stack

}

public void IterativePrint(){

Node currentNodePtr = headPtr.getNextNodePtr();

while (currentNodePtr != null){

System.out.print(currentNodePtr.getData() + " ");

currentNodePtr = currentNodePtr.getNextNodePtr();

}

System.out.println();

}

public void ReversePrint(){

Node currentNodePtr = tailPtr.getPrevNodePtr();

while (currentNodePtr != null){

System.out.print(currentNodePtr.getData() + " ");

currentNodePtr = currentNodePtr.getPrevNodePtr();

}

System.out.println();

}

}

class DoublyLinkedList_Stack_NextGreaterElement{

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int arraySize;

System.out.print("Enter the number of elements you want to analyze: ");

arraySize = input.nextInt();

int maxValue;

System.out.print("Enter the maximum value for an element: ");

maxValue = input.nextInt();

Random randGen = new Random(System.currentTimeMillis());

Stack stack = new Stack(); // Create an empty stack

int array[] = new int[arraySize];

for (int i = 0; i < arraySize; i++){

int value = randGen.nextInt(maxValue);

array[i] = value;

System.out.print(value + " ");

}

System.out.println();

// Implement a theta(n) algorithm (using Stack) to find the next greater element of each

// element in the array and print them

}

}