Next greater element in an array

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:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) 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     -->   -1

Algorithm

1. If the stack is empty or the current element is smaller than top element of the stack, then push the current element on the stack.
2. If the current element is greater than top element of the stack, then this is the next greater element of the top element. Keep poping elements from the stack till a larger element than the current element is found on the stack or till the stack becomes empty. Push the current element on the stack.
3. Repeat steps 1 and 2 till the end of array is reached.
4. Finally pop remaining elements from the stack and print null for them.

Please note that at any instance, the stack will always be in sorted order having least element at the top and largest element at the bottom.