C Exercises: Next greater for each element in an array using a stack

Last update on December 20 2024 13:08:53 (UTC/GMT +8 hours)

Write a C program to find the next greater element for each element in an array using a stack. Return -1 if there is no next-larger element.

Sample Solution:

C Code:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Global stack and top variables
int stack[MAX_SIZE];
int top = -1;

// Function to push an element onto the stack
void push(int data) {
    if (top == MAX_SIZE - 1) {
        printf("Overflow stack!\n");
        return;
    }
    top++;
    stack[top] = data;
}

// Function to pop an element from the stack
int pop() {
    if (top == -1) {
        printf("Empty stack!\n");
        return -1;
    }
    int data = stack[top];
    top--;
    return data;
}

// Function to print the next greater elements
void print_next_greater_element(int arr[], int n) {
    int i, next, element;
    // Push the first element onto the stack
    push(arr[0]);

    // Iterate through the array
    for (i = 1; i < n; i++) {
        next = arr[i];
        if (top != -1) {
            element = pop();
            // Find the next greater element
            while (element < next) {
                printf("%d --> %d\n", element, next);
                if (top == -1) {
                    break;
                }
                element = pop();
            }
            if (element > next) {
                push(element);
            }
        }
        // Push the current element onto the stack
        push(next);
    }
    // Remaining elements in the stack have no greater element
    while (top != -1) {
        element = pop();
        next = -1;
        printf("%d --> %d\n", element, next);
    }
}

int main() {
    int n = 6;
    int i = 0;
    int arr[n] = {1, 2, 3, 4, 5, 6};
    printf("Elements in the array are: ");
    for (i = 0; i < 6; i++) {
        printf("%d ", arr[i]);
    }
    printf("\nThe next larger elements are: \n");
    print_next_greater_element(arr, n);

    // More arrays to test
    // ...

    return 0;
}

Sample Output:

Elements in the array are: 1 2 3 4 5 6
The next larger elements are:
1 --> 2
2 --> 3
3 --> 4
4 --> 5
5 --> 6
6 --> -1

Elements in the array are: 6 5 4 3 2 1 0
The next larger elements are:
0 --> -1
1 --> -1
2 --> -1
3 --> -1
4 --> -1
5 --> -1
6 --> -1

Elements in the array are: 3 7 5 9 3 2 4 1 4
The next larger elements are:
3 --> 7
5 --> 9
7 --> 9
2 --> 4
3 --> 4
1 --> 4
4 --> -1
9 --> -1

--------------------------------

Flowchart:

C Programming Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Check a parentheses string is balanced or not using stack.
Next: Implement two stacks using a single array.