Given an array, print the Next Greater Element (NGE) for every element. The Next Greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.Examples:For any array, rightmost element always has next greater element as -1.For an array which is sorted in decreasing order, all elements have next greater element as -1.For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows:    Element       NGE       4      -->   5       5      -->   25       2      -->   25       25     -->   -1For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.    Element          NGE      13      -->     -1      7       -->     12      6       -->     12      12      -->     -1final class DataSet {    private final int x;    private final int nextX;    public DataSet(int x, int nextX) {        this.x  = x;        this.nextX = nextX;    }    public int getX() {        return x;    }    public int getNextX() {        return nextX;    }    @Override    public String toString() {        return x:  + x +  nextX:  + nextX;    }    @Override    public int hashCode() {        final int prime = 31;        int result = 1;        result = prime * result + nextX;        result = prime * result + x;        return result;    }    @Override    public boolean equals(Object obj) {        if (this == obj)            return true;        if (obj == null)            return false;        if (getClass() != obj.getClass())            return false;        DataSet other = (DataSet) obj;        if (nextX != other.nextX)            return false;        if (x != other.x)            return false;        return true;    }}public final class NextGreatestElement {    private NextGreatestElement() {}    /**     * Computes list of dataset, where dataset is a tuple of     * (currentInt, nextGreatestelement)     *      * @param a     the array     * @return      list of dataset     */    public static List<DataSet> getNextGreatestElement(int[] a) {        final List<DataSet> dataSetList = new ArrayList<DataSet>();        final Stack<Integer> stack = new Stack<Integer>();        for (int i = 0; i < a.length; i++) {            while (!stack.isEmpty() && stack.peek() < a[i]) {                dataSetList.add(new DataSet(stack.pop(), a[i]));            }            stack.push(a[i]);        }        while (!stack.isEmpty()) {            dataSetList.add(new DataSet(stack.pop(), -1));        }        return dataSetList;    }}public class NextGreatestElementTest {    @Test    public void test1() {        int[] a1 = {2, 3, 4, 5};        List<DataSet> ds1 = new ArrayList<DataSet>();        ds1.add(new DataSet(2, 3));        ds1.add(new DataSet(3, 4));        ds1.add(new DataSet(4, 5));        ds1.add(new DataSet(5, -1));        assertEquals(ds1,  NextGreatestElement.getNextGreatestElement(a1));    }    @Test    public void test2() {        int[] a2 = {3, 2, 1};        List<DataSet> ds2 = new ArrayList<DataSet>();        ds2.add(new DataSet(1, -1));        ds2.add(new DataSet(2, -1));        ds2.add(new DataSet(3, -1));        assertEquals(ds2, NextGreatestElement.getNextGreatestElement(a2));    }}
Find the Next Greatest Element
java;algorithm;stack