Next Greater Element

version.cpp

	
// A Stack based C++ program to find next 
// greater element for all array elements. 
#include <bits/stdc++.h> 
using namespace std; 

/* prints element and NGE pair for all 
elements of arr[] of size n */
void printNGE(int arr[], int n) { 
stack < int > s; 

/* push the first element to stack */
s.push(arr[0]); 

// iterate for rest of the elements 
for (int i = 1; i < n; i++) { 

	if (s.empty()) { 
	s.push(arr[i]); 
	continue; 
	} 

	/* if stack is not empty, then 
	pop an element from stack. 
	If the popped element is smaller 
	than next, then 
	a) print the pair 
	b) keep popping while elements are 
	smaller and stack is not empty */
	while (s.empty() == false && s.top() < arr[i]) 
	{		 
		cout << s.top() << " --> " << arr[i] << endl; 
		s.pop(); 
	} 

	/* push next to stack so that we can find 
	next greater for it */
	s.push(arr[i]); 
} 

/* After iterating over the loop, the remaining 
elements in stack do not have the next greater 
element, so print -1 for them */
while (s.empty() == false) { 
	cout << s.top() << " --> " << -1 << endl; 
	s.pop(); 
} 
} 

/* Driver program to test above functions */
int main() { 
int arr[] = {11, 13, 21, 3}; 
int n = sizeof(arr) / sizeof(arr[0]); 
printNGE(arr, n); 
return 0; 
}

version.py

# Python program to print next greater element using stack 

# Stack Functions to be used by printNGE() 
def createStack(): 
	stack = [] 
	return stack 

def isEmpty(stack): 
	return len(stack) == 0

def push(stack, x): 
	stack.append(x) 

def pop(stack): 
	if isEmpty(stack): 
		print("Error : stack underflow") 
	else: 
		return stack.pop() 

'''prints element and NGE pair for all elements of 
arr[] '''
def printNGE(arr): 
	s = createStack() 
	element = 0
	next = 0

	# push the first element to stack 
	push(s, arr[0]) 

	# iterate for rest of the elements 
	for i in range(1, len(arr), 1): 
		next = arr[i] 

		if isEmpty(s) == False: 

			# if stack is not empty, then pop an element from stack 
			element = pop(s) 

			'''If the popped element is smaller than next, then 
				a) print the pair 
				b) keep popping while elements are smaller and 
				stack is not empty '''
			while element < next : 
				print(str(element)+ " -- " + str(next)) 
				if isEmpty(s) == True : 
					break
				element = pop(s) 

			'''If element is greater than next, then push 
			the element back '''
			if element > next: 
				push(s, element) 

		'''push next to stack so that we can find 
		next greater for it '''
		push(s, next) 

	'''After iterating over the loop, the remaining 
	elements in stack do not have the next greater 
	element, so print -1 for them '''

	while isEmpty(s) == False: 
			element = pop(s) 
			next = -1
			print(str(element) + " -- " + str(next)) 

# Driver program to test above functions 
arr = [11, 13, 21, 3] 
printNGE(arr) 

# This code is contributed by Sunny Karira