Coders Packet

Finding Next Greater Element In C++ Using Stack

By Ashwini Laxman Jadhav

  • next greater element using stack.cpp
  • next greater element using stack.exe
  • In this tutorial, you will learn stack methods like push(), pop(), and how to use vector over array for avoiding wastage of memory.

    This tutorial will give you the simple method used to find the next greater element using stack. Vector is used over an array because the vector is a dynamic array, whose size can be increased, whereas the array size can not be changed.

    Next Greater Element In C++ Using Stack

    For finding the next greater element you need to check first whether the element present in a stack is smaller or greater than the element which you have entered.

    If the element which you have entered is greater, then you need to pop() your smaller element from the stack and assign that element as the next greater element for that smaller element. and if there is no greater element is found then assign that element as -1. Likewise, you can build the whole program easily. 

    Here is some part of the source code if you want the whole source code, Download it from the below file section.

    Enlightenerint main()
    {
      int n;
      cin>>n;
      vectorj(n);
      for(int i=0;i<n;i++)
      {
        cin>>j[i];
      }
      vectornext_g_e=Next_G_E(j);
      for(int i=0;i<n;i++)
      {
        cout<<j[i]<<" "<<(next_g_e[i]==-1? -1 : j[next_g_e[i]])<<endl;
      }
      return 0;
    }
    

    Example for logic:-

    1) Take one vector of some size, consider the elements are 2 3 1 4 22 4 you need to find the next greater element for these elements.

    2 3 1 4 22 4

    Take one stack, stack works on the last in first out method so we need to follow the same.

    Firstly insert the element in stack i.e:- 2 and then insert 3. Before inserting three checks 3 is greater or smaller than the element present in the stack so, 2<3 here we find 3 as a greater element for 2. Now pop() 2 from the stack, assign it 3 as a greater element and push 3 in the stack. Likewise, check for all elements you will get the following results.

    [               2< 3         

         2    ]    2---3

     

    2----3

    3----4

    1----4

    4---22

    22--- -1

    4---- -1

    Why the elements 22 and 4 have next the greater element as -1?

    Here is the answer, After 22 there is no greater element found so that's why -1 is assigned to 22 & after 4 there is no element to compare or push() in the stack because -1 is assigned to it.

    Download Complete Code

    Comments

    No comments yet