NEXT GREATER ELEMENT
next greater element means in an stack if element are {4,5,12,7} then the next greater element of
4 --> 5
5 --> 12
12 --> -1 //Because here no any greater element available so we return -1
7 --> -1 // Because no any element left in stack after 7
So here we are going to creat a stack and function display all input element of stack,And
a function for find Next Greater Element .
#include<stdio.h>
struct stack
{
int top;
int capacity;
int *array;
};
struct stack* creatstack(int cap)
{
struct stack *stack;
stack=(struct stack*)malloc(sizeof(struct stack));
stack->top=-1;
stack->capacity=cap;
stack->array=(int *)malloc(sizeof(int)*stack->capacity);
return(stack);
}
int isfull(struct stack* stack)
{
if(stack->top==stack->capacity-1)
return(0);
else
return(1);
}
int isempty(struct stack *stack)
{
if(stack->top==-1)
return(0);
else
return(1);
}
void push(struct stack *stack,int val)
{
if(isfull(stack))
{
stack->top++;
stack->array[stack->top]=val;
}
else
printf("Stack is Full");
}
int pop(struct stack *stack)
{
int item;
if(isempty(stack))
{
item=stack->array[stack->top];
stack->top--;
}
else
return(-1);
}
//Function for finding next greater element
int nextgreater(struct stack* stack,int val)
{
int item;
while(isempty(stack))
{
item=pop(stack);
if(item==val)
break;
}
while(isempty(stack))
{
item=pop(stack);
if(item>val)
break;
}
if(item>val)
return(item);
else
return(-1);
}
// Function For Display all element of stack
void display(struct stack* stack)
{
while(stack->top!=-1)
{
printf("%d ",stack->array[stack->top]);
stack->top--;
}
}
void main()
{
int n,val,NGE,newtop;
struct stack *stack;
clrscr();
printf("Enter number of Element of in stack");
scanf("%d",&n);
stack=creatstack(n);
while(isfull(stack))
{
system("cls"); // here you can also use clrscr();
printf("Enter Element of stack");
scanf("%d",&val);
push(stack,val);
}
newtop=stack->top;
display(stack);
stack->top=newtop;
printf("\nEnter Element of which you want to find next higher\n");
scanf("%d",&val);
NGE=nextgreater(stack,val);
printf("\nNext greater element of %d is %d",val,NGE);
getch();
}
0 Comments