Day 8 of the 100 Days DSA Challenge: Stacks

Welcome to Day 8 of the 100 Days DSA Challenge! Today, we will explore the concept of stacks, a fundamental data structure. We will implement various stack-related problems using C language. Let's dive in and enhance our understanding of stacks!

1. Implement a Stack Using Arrays

Problem: Implement a stack using arrays with basic operations: push, pop, and display.

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

#define MAX 100

int stack[MAX];
int top = -1;

void push(int value) {
    if (top == MAX - 1) {
        printf("Stack overflow\n");
    } else {
        stack[++top] = value;
    }
}

int pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        return -1;
    } else {
        return stack[top--];
    }
}

void display() {
    if (top == -1) {
        printf("Stack is empty\n");
    } else {
        for (int i = top; i >= 0; i--) {
            printf("%d ", stack[i]);
        }
        printf("\n");
    }
}

int main() {
    push(10);
    push(20);
    push(30);
    display();
    printf("Popped element: %d\n", pop());
    display();
    return 0;
}

2. Check for Balanced Parentheses

Problem: Write a program to check for balanced parentheses using a stack.

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

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) {
    if (top == MAX - 1) {
        printf("Stack overflow\n");
    } else {
        stack[++top] = c;
    }
}

char pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        return '\0';
    } else {
        return stack[top--];
    }
}

int isMatchingPair(char character1, char character2) {
    if (character1 == '(' && character2 == ')')
        return 1;
    if (character1 == '{' && character2 == '}')
        return 1;
    if (character1 == '[' && character2 == ']')
        return 1;
    return 0;
}

int areParenthesesBalanced(char exp[]) {
    for (int i = 0; i < strlen(exp); i++) {
        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[') {
            push(exp[i]);
        }
        if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') {
            if (top == -1 || !isMatchingPair(pop(), exp[i])) {
                return 0;
            }
        }
    }
    return top == -1;
}

int main() {
    char exp[] = "{()}[]";
    if (areParenthesesBalanced(exp)) {
        printf("Balanced\n");
    } else {
        printf("Not Balanced\n");
    }
    return 0;
}

3. Next Greater Element

Problem: Solve the "next greater element" problem using a stack.

#include <stdio.h>

#define MAX 100

void nextGreaterElement(int arr[], int n) {
    int stack[MAX];
    int top = -1;
    int next, element;

    for (int i = 0; i < n; i++) {
        next = arr[i];
        while (top != -1 && stack[top] < next) {
            element = stack[top--];
            printf("%d -> %d\n", element, next);
        }
        stack[++top] = next;
    }

    while (top != -1) {
        element = stack[top--];
        printf("%d -> -1\n", element);
    }
}

int main() {
    int arr[] = {4, 5, 2, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    nextGreaterElement(arr, n);
    return 0;
}

4. Reverse a String Using a Stack

Problem: Write a program to reverse a string using a stack.

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

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) {
    if (top == MAX - 1) {
        printf("Stack overflow\n");
    } else {
        stack[++top] = c;
    }
}

char pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        return '\0';
    } else {
        return stack[top--];
    }
}

void reverseString(char str[]) {
    for (int i = 0; i < strlen(str); i++) {
        push(str[i]);
    }
    for (int i = 0; i < strlen(str); i++) {
        str[i] = pop();
    }
}

int main() {
    char str[] = "Hello";
    reverseString(str);
    printf("Reversed string: %s\n", str);
    return 0;
}

5. Stack with Minimum Element in O(1) Time

Problem: Implement a stack that supports push, pop, and finding the minimum element in O(1) time.

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

#define MAX 100

int stack[MAX];
int minStack[MAX];
int top = -1;
int minTop = -1;

void push(int value) {
    if (top == MAX - 1) {
        printf("Stack overflow\n");
    } else {
        stack[++top] = value;
        if (minTop == -1 || value <= minStack[minTop]) {
            minStack[++minTop] = value;
        }
    }
}

int pop() {
    if (top == -1) {
        printf("Stack underflow\n");
        return -1;
    } else {
        int value = stack[top--];
        if (value == minStack[minTop]) {
            minTop--;
        }
        return value;
    }
}

int getMin() {
    if (minTop == -1) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return minStack[minTop];
    }
}

int main() {
    push(3);
    push(5);
    printf("Minimum element: %d\n", getMin());
    push(2);
    push(1);
    printf("Minimum element: %d\n", getMin());
    pop();
    printf("Minimum element: %d\n", getMin());
    return 0;
}

Conclusion

That wraps up Day 8 of our DSA challenge! We explored various problems related to stacks and implemented solutions in C language. Stacks are a fundamental data structure that can simplify many complex problems. Keep practicing, and you'll become more proficient with stacks and other data structures.

Stay tuned for more exciting problems and solutions as we continue to improve our skills in data structures and algorithms.