NPTEL(WEEK-6.2)

Programming Assignment 6.2 : Nearest Larger Number in Stack

Due on 2016-03-05, 23:55 IST

Nearest larger number (NLN) of  element of stack is defined as the closest greater number that are pushed before the element, if there are no such element then NLN will be -1. Given a stack of unique positive integer, return another stack with NLN of each element in the same order of original stack.

Consider example of stack, where 4 is top-most and 3 bottom-most.

3 7 5 6 8 4

Then NLN of each element is given by

-1 -1 7 7 -1 8

Explanation:

• Number greater than 4 which is closest and below stack is 8,
• Similarly the number greater 7 is greater than 6 and closest to 6
• Since there is no element greater than 8 below the stack NLN is -1

and so on ..

You have complete returnStackWithNearestGreater(Stack inputStack) that return the NLN Stack.

Input

N

a1 a2 a3 a4 .. aN

where N is number of elements in the stack, ai are elements of the stack where aN is top-most element of the stack

Ouput:

b1 b2 b3 b4 .. bN

where b1  is NLN for a1, b2 is NLN for a2 and so on….

PROGRAM:

#include<cstdio>

using namespace std;

#define MAX 200

class Stack{

int top,input[MAX];

public:

Stack(){

top = -1;

}

bool isEmpty(){

return (top == -1);

}

bool isFull(){

return (top==MAX);

}

void push(int element){

if(!isFull()){

input[++top]=element;

}

}

int pop(){

if (!isEmpty()){

return input[top--];

}

return -1;

}

int getTopValue(){

return input[top];

}

                void print();

};

void Stack::print()

{

int index ;

for(index=0;index<top;index++){

printf("%d ",input[index]);

}

if(index == top){

printf("%d",input[index]);

}

}

Stack returnStackWithNearestGreater(Stack inputStack);

int main(){

int N,el;

Stack stack,result;

        scanf("%d",&N);

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

                scanf("%d",&el);

stack.push(el);

}

result  = returnStackWithNearestGreater(stack);

        result.print();

return 0;

}

CODING:

Stack returnStackWithNearestGreater(Stack inputStack)

{

  Stack tempS;

  int arr1[100],arr[100],i=0,l;

  int temp[100],f=0,max;

  while(!inputStack.isEmpty())

  {

    arr1[i++] = inputStack.pop();

  }

  l = i;

  for(int i=0;i<l;i++)

    arr[i]=arr1[l-i-1];

  for(i=0;i<l;i++)

  {

    f=0;

    max = arr[i];

    for(int j=i-1;j>=0;j--)

    {

      if(max < arr[j])

      {

        f=1;

        max = arr[j];

        goto lll;

      }

    }

    lll:

    if(f==1)

    temp[i] = max;

    else

      temp[i] = -1;

  }

for(int i=0;i<l;i++)

    tempS.push(temp[i]);

  return tempS;

}