Kanchan Rai

Day 8: 100 Days of DSA

Stacks

Kanchan Rai's photo
Kanchan Rai
·

4 min read

Hey everyone! Welcome to day 8 of my 100 days of DSA challenge. Today I’ll be solving 5 problems related to stacks. The code for each problem along with the output is given below. Stacks are very useful data structure which can help us solve many problem. Stacks are a fundamental data structure based on the Last-In-First-Out (LIFO) principle, widely used in various algorithmic problems.

1. To implement stack using array

Code:

// To implement stack using arrays
#include<iostream>
using namespace std;

#define MAX 1000

class Stack {
    int top;
    public:
    int a[MAX]; // Maximum size of Stack

    Stack() { top = -1; }
    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
};

bool Stack::push(int x) {
    if(top >= (MAX-1)) {
        cout << "Stack Overflow" << endl;
        return false;
    } else {
        a[++top] = x;
        cout << x << " pushed into stack" << endl;
        return true;
    }
}

int Stack::pop() {
    if(top < 0) {
        cout << "Stack Underflow" << endl;
        return 0;
    } else {
        int x = a[top--];
        return x;
    }
}

int Stack::peek() {
    if(top < 0) {
        cout << "Stack is Empty" << endl;
        return 0;
    } else {
        int x = a[top];
        return x;
    }
}

bool Stack::isEmpty() {
    return (top < 0);
}

int main() {
    class Stack s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << s.pop() << " popped from stack" << endl;

    cout << "Elements present in stack: ";
    while(!s.isEmpty()) {
        cout << s.peek() << " ";
        s.pop();
    }

    return 0;
}

Output:

2. Write a program to check for balanced parentheses using a stack.

Code:

// Write a program to check for balanced parentheses using a stack.

#include<iostream>
#include<stack>
#include<string>
using namespace std;

bool areParanthesesBalanced(string expr) {
    stack<char> s;
    char x;
    for(int i = 0; i < expr.length(); i++) {
        if(expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
            s.push(expr[i]);
            continue;
        }
        if(s.empty()) return false;
        switch(expr[i]) {
            case ')':
                x = s.top();
                s.pop();
                if(x == '{' || x == '[') return false;
                break;
            case '}':
                x = s.top();
                s.pop();
                if(x == '(' || x == '[') return false;
                break;
            case ']':
                x = s.top();
                s.pop();
                if(x == '(' || x == '{') return false;
                break;
        }
    }
    return (s.empty());
}

int main() {
    string expr = "{()}[]";
    if(areParanthesesBalanced(expr)) cout << "Balanced" << endl;
    else cout << "Not Balanced" << endl;
    return 0;
}

Output:

3. Solve the "next greater element" problem using a stack.

Code:

// Solve the "next greater element" problem using a stack.

#include<iostream>
#include<stack>
#include<vector>
using namespace std;

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> result(nums.size());
    stack<int> s;
    for(int i = nums.size() - 1; i >= 0; i--) {
        while(!s.empty() && s.top() <= nums[i]) s.pop();
        result[i] = s.empty() ? -1 : s.top();
        s.push(nums[i]);
    }
    return result;
}

int main() {
    vector<int> nums = {4, 5, 2, 10, 8};
    vector<int> result = nextGreaterElement(nums);
    for(int i = 0; i < result.size(); i++) {
        cout << nums[i] << " -> " << result[i] << endl;
    }
    return 0;
}

Output:

4. Write a program to reverse a string using a stack.

Code:

// Write a program to reverse a string using a stack.

#include<iostream>
#include<stack>
#include<string>
using namespace std;

string reverseString(string str) {
    stack<char> s;
    for(int i = 0; i < str.length(); i++) {
        s.push(str[i]);
    }
    for(int i = 0; i < str.length(); i++) {
        str[i] = s.top();
        s.pop();
    }
    return str;
}

int main() {
    string str = "Hello, World!";
    cout << "Original: " << str << endl;
    cout << "Reversed: " << reverseString(str) << endl;
    return 0;
}

Output:

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

Code:

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

#include<iostream>
#include<stack>
using namespace std;

class Stack {
    stack<int> s;
    int minEle;
    public:
    void getMin();
    void peek();
    void pop();
    void push(int x);
};

void Stack::getMin() {
    if(s.empty()) cout << "Stack is empty" << endl;
    else cout << "Minimum element in the stack is: " << minEle << endl;
}

void Stack::peek() {
    if(s.empty()) {
        cout << "Stack is empty" << endl;
        return;
    }
    int t = s.top();
    cout << "Top Most Element is: ";
    (t < minEle) ? cout << minEle : cout << t;
    cout << endl;
}

void Stack::pop() {
    if(s.empty()) {
        cout << "Stack is empty" << endl;
        return;
    }
    cout << "Top Most Element Removed: ";
    int t = s.top();
    s.pop();
    if(t < minEle) {
        cout << minEle << endl;
        minEle = 2*minEle - t;
    } else {
        cout << t << endl;
    }
}

void Stack::push(int x) {
    if(s.empty()) {
        minEle = x;
        s.push(x);
        cout << "Number Inserted: " << x << endl;
        return;
    }
    if(x < minEle) {
        s.push(2*x - minEle);
        minEle = x;
    } else {
        s.push(x);
    }
    cout << "Number Inserted: " << x << endl;
}

int main() {
    Stack s;
    s.push(3);
    s.push(5);
    s.getMin();
    s.push(2);
    s.push(1);
    s.getMin();
    s.pop();
    s.getMin();
    s.pop();
    s.peek();
    return 0;
}

Output:

That’s all for today! Happy Coding! 🍀✨

StacksDSAdsainc++